Text from statement:

"For instance, if L < K1, then it may happen that the policeman reaches the first stop when the robber is still waiting for a tram there."

It means that you are right.

Hi!

There seem to be many *accepted* solutions here that do not really try all possible combinations. These do *NOT* solve this problem, as some have pointed out correctly, this is a knapsack type of problem and unless going through all 2^n combinations of n numbers, you cannot find the optimal answer. It is clear, that the test data are too weak indeed!!!

Input: n numbers

After 1st while cycle: i = n

doubleVector.at(i) - crash because size = n and only doubleVector[n-1] exists.

And you should print numbers with 4 digits after the decimal point.

NO

Two advices:
1) There's no need in Y-coordinates since points are sorted in input. Ignore them.
2) You should find a way to answer quickly on queries "how many numbers are lesser than given one".

P.S. I used Binary Indexed Tree (Fenwick's Tree) for this problem and got a code of the same length as your pseudocode. ;-)

And I'm interesting how to solve this in 0,015s.

Stupid title

Попробуй (**) YES

That simply means that you do NOT output 1 million chars!
I have the same problem, and I can't solve it. But if I decrease the
number of outputs then I get WA.

I used
putchar(buffer[j]);
instead of printf("%s",buffer)
and I got accepted.

I really don't know why.


> As you can see the task is to output the sequence consists of
1000000
> symbols. I output exactly 1000000 symbols one by one (...Write
> (sym)...Write(sym)...Write(sym)...), buf after 0.04 seconds I
> receive "Output Limit". What does it mean and how should I output
the
> sequence?
> Please, help me!

var
 i:longint;
begin
 randomize;
 for i:=1 to 1000000 do write(chr(ord('a')+random(26)));
end.

sorry, my mistake! the first number is actually the number of stones!

Consider the following example:
5
10 10 8 7 5

Your algo will give answer 4, while the correct one is 0. Use brute-force to solve the problem.

I think that the correct algorithm is using DP, like this:

If you figure out a way to find the sum of each possible subsets from {w0...wn}, and you know that w0+w1+..+wn = N... for some N, then the problem is reduced to find the set that gets closer to N/2.

IOW: Suppose you have a set and the sum of its elements is equal to N/2.. Then the sum of the other set is also N/2, so the difference is 0...
And the difference will always be minimal near N/2.. so if you can't get N/2, try finding the one closer to it.

the way I did it is:
...
  S := {w0,w1,...,wn}
  B := array(Bool, #(S), false)
  B[0] := true // you can always pic the empty set
  for i in S:
     for j in range(0, N):
        if B[j] = true:
           B[j+S[i]] := true
...
This gives you all possible sums of the possible subsets of S like this:

B[i] = true if there exist a set S' of S such that (sum(S') = i) holds.

Hope I wasn't very bad at my english.. :S

See ya
gaston770@gmail.com