All tests have published here passes.
Test 3 gives WA persistently. What is it like?

I fixed 4 digits after decimal point of a result (that is, for example: 3.0000)
Does it matter?

Edited by author 02.07.2016 02:19

Edited by author 02.07.2016 02:19

  Not very hard to prove, then the breakage-line must create EQUAL ANGLES with sides, connected by it. This idea immediately gives the O(N^3) algorithm. But it could be improved even to O(N). :)

test #4, if you sort the left nodes then before updating the DP[i], you should check whether their left nodes are coincide or not.
e.g:
4
1 2
1 3
1 4
1 5
test #6: this test has n == 1, you just need to print 1 and 1 in the output.

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package test;

import java.util.ArrayList;
import java.util.Scanner;

/**
 *
 * @author MMT
 */
public class P1197 {


    public static void main(String[] args){
    // declaration of variables
       Scanner in_number=new Scanner (System.in);
       Scanner in_string=new Scanner (System.in);

       int n=0;
       ArrayList res=new ArrayList();
       String s=" ";
       char c1=' ';
       int c2=0;
       int contr=0;
       n=in_number.nextInt();

       if(n>0 && n<101){
       for(int i=0;i<n;i++){

            s=in_string.next();

            c1=s.charAt(0);
            c2=Integer.parseInt(s.substring(1));

    if((((char)c1+1) <'i')  &&(((char)c1+1) >'`')   && ((c2+2)<=8)      && ((c2+2)>0)  )
     contr++;
    if((((char)c1-1) >'`')  &&(((char)c1-1) <'i')   && ( (c2+2)<=8)     && ((c2+2)>0))
      contr++;
    if( (((char)c1+1)<'i')  &&(((char)c1+1) >'`')   && ( (c2-2)>0)      && ( (c2-2)<=8)) // right
       contr++;
    if((((char)c1-1) >'`')  &&(((char)c1-1) <'i')   && ( (c2-2)>0)      && ( (c2-2)<=8) ) // right
       contr++;
    if((((char)c1+2) <'i')  &&(((char)c1+2) >'`')   && ( (c2+1)<=8)     && ((c2+1)>0))// not checked
       contr++;
    if((((char)c1-2) >'`')  &&(((char)c1-2) <'i')   && ( (c2+1)<=8)     && ((c2+1)>0))   // right
       contr++;
    if((((char)c1+2) <'i')  &&(((char)c1+2) >'`')   && ( (c2-1)>0)      && ( (c2-1)<=8))    // not checked
       contr++;
    if((((char)c1-2) >'`')  &&(((char)c1-2) <'i')   && ( (c2-1)>0)      && ( (c2-1)<=8))    //  right
        contr++;

res.add(contr);
contr=0;
c1=' ';
c2=0;
s=" ";
       }
       for(int j=0;j<res.size();j++){
       System.out.println(res.get(j));

       }
       }/*
        char x = 'a';
        x=(char) (x-1);
      System.out.println(x);
    */}
}

Edited by author 01.07.2016 10:11

Awesome English...

using System;

namespace Csharp_2023
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int num = 1;
            int sum = 0;

            for (int z = 1; z <= n; z++)
            {
                string str1 = Console.ReadLine();

                for (int f = 1; f <= n; f++)
                {
                    if (str1[0] == 'A' || str1[0] == 'P' || str1[0] == 'O' || str1[0] == 'R')
                    {
                        if (num == 1) sum += 0;
                        else if (num == 2) sum += 1;
                        else if (num == 3) sum += 2;
                        num = 1;
                        break;
                    }
                    else if (str1[0] == 'B' || str1[0] == 'M' || str1[0] == 'S')
                    {
                        if (num == 1) sum += 1;
                        else if (num == 2) sum += 0;
                        else if (num == 3) sum += 1;
                        num = 2;
                        break;
                    }
                    else if (str1[0] == 'D' || str1[0] == 'G' || str1[0] == 'J' || str1[0] == 'K' || str1[0] == 'T' || str1[0] == 'W')
                    {
                        if (num == 1) sum += 2;
                        else if (num == 2) sum += 1;
                        else if (num == 3) sum += 0;
                        num = 3;
                        break;
                    }
                }
            }
         Console.WriteLine(sum);
        }
    }
}

//i try to run the code passed, i seems it make the same answer as me
//i don't know what's wrong accur,plz help me.Does there is any wrong in way i solve this problem?
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
    public static void main(String[] args)
    {
        Scanner cin = new Scanner ( System.in );
        int a,temp;//count store time of test
        //find 1,1 is easy to find
        //1 is at (n+1)n/2 +1
        int count=cin.nextInt();
        for (int j=1; j<=count; j++) {
            a=cin.nextInt();
            temp=(int) Math.floor(Math.sqrt(2*(j-1)));
            if((temp*(temp+1)/2+1)==j){
                System.out.print("1 ");
            }else {
                System.out.print("0 ");
            }
        }
    }
}

So like, i spent a few days thinking of a possible way to do this, and one of the ideas that hit me was finding the closest parent of two vertices in O(log n) like it's done in tasks 1329 or 1471; in a case of this task, we can quickly find a parent of previous train and current train — a particular turnout that we need to switch, ignoring a potentially huge number of turnouts before this one. We switch it, make a step forward, and then repeat the algo in a subtree. Or so i thought this ideally would be.

I also use the array that has, for each vertex, the trainroute that was passing by through this vertex last time. More or less, because we can't mark them all anyway, because it won't differ from a brute force then and will lead to TL.

Anyways, i have found a countertest for my program:
6 6
X-L.X.X.X.X
..|.|.|.|.|
S-R-R-R-R-R
..|.|.|.|.|
X-R.X.X.X.F
..........|
X.X.X.X.X.F
|.|.|.|.|.|
L-L-L-L-L-R
|.|.|.|.|.|
X.X.X.X.X.X
5
1 1 4
2 6 3
3 6 5
4 1 3
5 4 3

For which, my bruteforce shows a correct answer
12
2 2 2 F
3 2 3 F
4 2 4 L
5 2 4 F
6 2 3 L
6 2 5 F
7 2 3 F
11 5 5 F
12 5 5 L
12 5 4 F
14 5 5 F
16 5 3 R
, but my "quick" algo doesn't have the 14 5 5 F row.

It'll take too much space explaining fully why this happens, but in short, on a certain subtree it sees the route that went through that spot a bit too much time ago, and falsely assumes that further turnouts are arranged for that route. Which is not fully true.
(here's a final "last visitor" map if it can potentially explain it)
00 00 00 00 00 00
03 04 03 33 33 33
00 00 00 00 00 33
00 00 00 00 00 33
00 00 33 33 35 33
00 00 00 00 00 00

So that makes me wonder, if my idea is right overall (it looked pretty to me at first...) but just my implementation is bad, or is the idea itself is a no-go and i should try something entirely different?
Though quite likely i'll just give up, i spent a bit too many days on this without good outcome...

Edited by author 01.07.2016 01:40

Edited by author 01.07.2016 01:40

The new time limit is 1.0 seconds (old - 0.5s). All submissions have been rejudged. The number of authors who has AC remain almost the same.

Edited by author 31.07.2017 12:48

Rustc compiler version 1.9.0 was added. For more details on how to solve problems using Rust read the help page http://acm.timus.ru/help.aspx?topic=rust

Used unsigned long long. At result got WA7. Just clear unsigned everywhere and i got AC. Strange behavior. There was no negative numbers, it's really strange.

Anybody else?

Use the generation of the subsets

Can someone tell me what's test case 8? With set, all testcases pass but with Trie, I am getting WA at testcase 8.

Короче,у нас проходит некий турнир.Правила таковы: мы выбираем любых двух джедаев из оставшихся ,они между собой сражаются,из них по условию ровно один побеждает,проигравший исчезает с турнира. И так далее: снова выбираем двух джедаев,один остается,и т.д. По условию либо Джедай А сильнее Джедая Б либо наоборот. Сильнее значит не менее чем по двум параметрам один джедай выигрывает у другого(т.е. соответствующие значения строго больше). Нам нужно найти всех возможных победителей,т.е. тех,кто останется последним. Мы можем как угодно формировать расписание турнира,т.е. выбирать кто с кем из оставшихся будет драться. Победитель может провести всего 1 бой,а может 2,а может 3,... .Расписание мы САМИ формируем!!!

У кого нет идей,советую узнать про алгоритм Тарьяна и граф конденсации.

Edited by author 31.08.2015 22:18

Input:
trams trolleybuses trambus
bus
Output:
Bus driver

Input:
tram tramtrolleybus bus
Output:
Tram driver

Input:
trams trolleybus
trolleybus tram! tram.
Output:
Bus driver

Input:
bus bus tratrolleybus
trolleybu tra.
Output:
Bus driver

I've been struggling hard to overcome WA4 and WA9...
In the problem statement, it says "Sentences in a message consist of words, spaces and punctuation marks".
Then I've made these test cases and got AC in one go... :)
Try these cases if u get WA...

Case 1:
WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?
Ans:
Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

Case 2:
 WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?
Ans:
 Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

(It looks same to case 1, but it has an initial space character in the first line and I think this was causing WA9 for me...)

Case 3:
AND BEING CARELESS, WE ARE DESTROYING THE EARTH.
?????
WHO ARE UUUUUUUUUUUUUUUUUUU
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU?
CANT U SEE IT ?

WHY DID U DO THIS?
UUUUUUUU
UUUUUUUU IDIOT.
BYE.

Ans:
And being careless, we are destroying the earth.
?????
Who are uuuuuuuuuuuuuuuuuuu
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu?
Cant u see it ?

why did u do this?
Uuuuuuuu
uuuuuuuu idiot.
Bye.

Case 4:
...ARE U THERE STILL?
PLEASE, ANSWER MEEEEEEEEE ,
ANSWER ME , ANSWER ME...
PLEASE
Ans:
...Are u there still?
Please, answer meeeeeeeee ,
answer me , answer me...
Please



Let me know if any1 finds any error...
Thanks.