Editorial for COCI '08 Contest 2 #4 Svada


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Suppose that the output (how many seconds passed between the arrival of the first type and second types of monkeys) is S. Then we know that monkeys of the first type spent S seconds in the garden and monkeys of the second type spent T-S seconds.

We can calculate how many coconuts the first type can gather in S seconds. Let this amount be X(S).

Also, we can calculate how many coconuts the second type can open in T-S seconds (assuming that there is an infinite number on the ground). Let this amount be Y(S).

If X(S) > Y(S), this means that the actual output is less than S because monkeys of the second type do not have enough time to open all the coconuts.

If X(S) \le Y(S), this means that the output can be S or more because there is time to open all coconuts.

The correct output is the largest S for which X(S) \le Y(S). We can use binary search to find it.


Comments

There are no comments at the moment.