Editorial for COCI '08 Contest 2 #4 Svada
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 . Then we know that monkeys of the first type spent seconds in the garden and monkeys of the second type spent seconds.
We can calculate how many coconuts the first type can gather in seconds. Let this amount be .
Also, we can calculate how many coconuts the second type can open in seconds (assuming that there is an infinite number on the ground). Let this amount be .
If , this means that the actual output is less than because monkeys of the second type do not have enough time to open all the coconuts.
If , this means that the output can be or more because there is time to open all coconuts.
The correct output is the largest for which . We can use binary search to find it.
Comments