OJ Board

In worst case its works N*N*logN

Who may check this input

3 3
1 2
2 3
3 1
10 11
1 2
2 3
3 1
3 7
4 5
5 6
6 4
7 9
6 3
9 8
7 8
3 2
1 2
2 3
3 0
6 4
1 2
1 3
1 4
5 6
1 0
0 0
7 6
1 2
1 3
2 4
2 5
3 6
3 7
20 20
1 3
3 5
5 7
7 9
9 11
11 13
13 15
15 17
17 19
19 20
20 2
2 4
4 6
6 8
8 10
10 12
12 14
14 16
16 18
18 1
10 12
1 2
2 3
3 4
4 2
1 5
5 ...

Dominik your algorithm is right (I got AC with same algorithm).
In this algorithm only one intersting place:

DFS(...){
int max1=0,max2=0,.....;
...... // cycle
t=DFS(.....);
if (t > max1){
max2=max1;
max1=t;
}
else if (t > max2) max2=t;
....... // end cycle
if (max1+max2 > max) max=max1 ...

Thank you very much Martin, i found my logical mistake (i think that length of path of ball is s*v, but i mistaken, length of path of ball is s*v/2) and got AC.

Please help me.
I have some questions about this problem.

1 Whats means this sentence "Before the first bounce, the ball increases its distance from the lower left corner of the table."
2 Initinally ball have coordinantes (a/2,b/2) (i think this coord of middle of table)?
3
(0,b) (a,b ...

Thank you very much mf.
I got AC.
If you have questions about this problems http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:50323 I help you

Thank you mf for answer.

But why?

1 16 2 13 10 11 12 17 9 3 4 6 14 5 7 15 8

lexicographically smaller than

1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8.

If this sentence "... which finds the desired shortest round trip" means, that the path must have the smallest number of junction?

I got WA many times.
Is my output for this test case is correct?


2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 ...

Try first to generate all primes < sqrt(2^31) and then instead "n mod i" use "n mod prime", where prime the next prime number

Your prime number generator very slow.
this my code to generate prime numbers:


int mas[100000],in;
char matr[1000001];


int prost(){
int i,j,t;
for (i=3;i<1000001;i+=2)
if (!matr[i]){
mas[in++]=i;
t=i+i;
for (j=i;j<1000001;j+=t)
matr[j]=1;
}
return 0;
}


this function generate all ...

Yes, you is right, but AC program must gives for this input right output.

Thank you Martin for reply. You is right, i find bug in my code, and got AC.

This output for tests above

west
west
south
south
east
east
south

west
west
north
north
east
east
east

west
west
west
east
east
east

east
east
west
south
south
east
east

south
south
west
west
south

west
south
west
west
south

south
west
south

east
west
west
west

north
south

north
west
west ...

Check this input:

20 19
1 11
1 20 3 3
20 2 78 34
2 19 78 3
19 3 78 3
3 18 78 5
18 4 1 23
4 17 1 23
17 5 1 1
5 16 1 1
16 6 2 23
6 15 34 3
15 7 35 3
7 14 2 23
14 8 78 3
8 13 24 2
13 9 3 34
9 12 2 1
12 10 34 3
10 11 3 34
20 19
1 20
1 2 3 53
2 3 35 35
3 4 23 3
4 5 7 7
5 6 34 2
6 7 11 6
7 8 24 1
8 ...

Hi all,
I use to slove this problem MST and get WA all time.
If there are some bad inputs for this problem or I mistake with choose algoritm???