minimum is  always -1, 1, or 2 ?
1) S = aaaa...aa   => -1        (S = [a]*n)
2) S = aaabaaa   on center different symbol ==> -1 (S = [a]*m + 'b' +[a]*m)
3) S = ababababa...ababa  ==> -1   (S = [ab]*m + 'a' there S is palindrome)
4) S - is not palindrome,  ==> 1
5) S - is palindrome, there at least two different symbols => 2
   Proof 5:
let a = S[1], b = S[i] , and all S[1] = S[2] = ..=S[i-1] = a,  There S is palindrome.
    S = aaaabxy....baaaa
   Take T1 = aaab  T2 = xy...baaaa
   T1 - is not palindrome

    5.1)  T2 also is not palindrome, minimum cut is 2.
    5.2) T2 also palindrome
         5.2.1) i > 2, there two or more 'a' in T1.
           T1 = aaabx   T2 = y....baaaa
          There T1 and T2 both are not palndrome, (think about it).
         5.2.2. i = 2.  T1 = ab  But T2 palindrome, so S = abababababa...aba, this can't be allowed, because S != [ab]*m + 'a'  already checked.

What may cause this judgement result?

import sys, math

numbers = []
empty_lines = 0

for line in sys.stdin:
    line = line.strip()

    if line == "":
        empty_lines += 1
        if empty_lines == 2:
            break
    else:
        empty_lines = 0
        numbers.extend(line.split())

for num in reversed(numbers):
    print(f"{math.sqrt(int(num)):.4f}")

Don't know why so many authors have posted 2*n-1.. That's obviously a wrong solution...

Just think about if the stone is in the odd and the man touches the odd, things will be done smoothly.

n=2

var
  i,n,l,j:longword; found:boolean;
begin
  readln(n);
  repeat
  found:=False;
  for j:=3 to n div 2 do
  begin
    if n mod j=0 then
    begin
      found:=True;
      break;
    end;
  end;
  if found then n:=j;
  until not found;
  writeln(n-1);
  readln;
end.

Please help me to optimize my code. It's 0.405 sec

Mine quite straightforward realization works about 1 sec. and uses almost 60 megabytes of memory. Please, give an idea how to solve it more quickly...

i have +27 submites on it just because i forgot tests like that:
1
808 6464("No solution")

Edited by author 10.10.2009 04:16

Скорость оленей не ограничена, т.е. они могут хоть телепортироваться считай
Здесь факт лишь в том, что они должны пробежать за 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?