Скорость оленей не ограничена, т.е. они могут хоть телепортироваться считай
Здесь факт лишь в том, что они должны пробежать за H часов K километров
По этому минимальное например при данных 30 11 2 будет равно 4
Объясняю: За 4 часа олени пробегут 22 км (ну, 11*2 просто) , и так как осталось 8 км, то они могут это расстояние просто перелететь (телепортнуться), ведь это меньше 11 км, поэтому им и время не нужно (они же не прошли 11, значит и 2 часа не нужно).
А с максимальным все очень просто, это просто время если бы олени двигались с постоянной скоростью, но могли немного перебежать нужное расстояние(главное чтобы оно было не больше к)
При 30 11 2 макс время будет 6 часов, тк только тогда олени достигнут своих 30км изначальных (ну немного больше пробегут - 33 км)
Надеюсь кому-то поможет в решение

Hello,
I am not that strong in DP but I have been trying hard to understand the problem. I tried coming up with a solution however got WA. I cannot completely understand the hints given before, PLEASE HELP !!!

Strange but when i use

printf("%s",s.c_str());

I get WA on test 11, but if change it to

cout<<s;

it's become AC.

Can somebody tell me why?

4 3 2 3
9 3 7 9
5 3 8 3
8 2 0 5
answer : 62

I pass this problem with Sieve of Eratosthenes, but i think solution with Pollard's rho algorithm is funnier, and wrote it too.

If you cant pass it with this algo just use all prime modules from 1'000'000'007 to 1'000'001'393.

Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number.

Use sort and find min and max after output each pair.
Quite slow, 0.14s :)

When I sorted all problem according to their set of topics for merging at output I forgot to make it stable, so that the order of grouped problems stays increasing.

#pragma GCC optimize("Ofast")
With this line of code I'm getting AC 0.468, without it I'm getting TL14

2^8 queries are given. Each query has an interval [L,R). (2^63<L,R<2^64) Find the number of primes in each interval.
P.S.
Warning:
you won't fit into a hundred lines of code!

2
0 1 2
1 1 1


-------
unknown unknown
unknown 1

or

1 1
1 1

Before first visit pub #1 is asking about drinks?

Test:
10
2 3 2 3 6
0 1 1
0 2 4 10
0 3 5 7 9
0 1 3
0 1 3
0 1 8
0 1 7
1 1 7
2 1 5

Answer:
unknown 2
2 2
2 2
2 2
2 2
2 2
unknown unknown
unknown unknown
2 1
2 2

My step-by-step barbell moving (though improved to add into under and out under the barbell only "right" worms without checking every worm) gives TLE on 8th test.

Is segment tree needed?

Hello, everyone.
Just wanted to summarize some info about this problem.
Ok, my code got AC with following things in it:
1. My pi was 3.1415926535897932384626433 (perhaps it is enough)
2. I used this formula from wikipedia
deltaArc=acos(sin(phiA)*sin(phiB)+cos(phiA)*cos(phiB)*cos(deltaL));
distance = deltaArc*3437.5;
(see the first formula from wikipedia http://en.wikipedia.org/wiki/Great-circle_distance)
3. I used the following condition:
if(100.00-distance>0.005) printf("DANGER!\n");
Hope it will help somebody.

Edited by author 07.03.2010 10:26

diameter of 6875 miles (/ 2 = 3437.5)???

the mean radius of earth is 6371.0 km (3958.8 miles)

You have to check all edges between centroids, not just arbitrary one. Although it leads to O(N^4) due to N^2 BFSes on cliques, early cutoff on max-dist from roots vs. current result makes it almost O(N^3). AC 0.046 sec

You may output edge nodes in any order (1 2) or (2 1) checker accepts that

We cannot imagine the test where our prog will give wrong answer!

I try to output zeros in this case, but seems like I'm wrong
please show me some example
for example for this case
2
11
11

Edited by author 11.12.2007 21:50

Can someone give me a little hint, please ?