Editorial for COCI '13 Contest 3 #4 Kolinje
Submitting an official solution before solving the problem yourself is a bannable offence.
People from to are going to get, respectively, kilos of ham, given an . We need to find such that the sequence is correct; from it, it is easy to calculate the total number of distributed kilos.
We want the following to be true: .
Let us analyze the first inequality; the rest are analyzed analogously. From follows .
We'd like to divide this inequality by so only is left on the left side. However, we need to be careful!
If , we cannot make the division, but the inequality turns into . In this case, if , we output -1
because this is a contradiction. Otherwise, the inequality is valid so we move on to the next one.
If , we can make the division, but dividing by a negative number changes the inequality signs so we either get or . In one case we got the lower, and in the other the upper bound for .
Repeating this operation for all inequalities, we gathered some lower and upper bounds for . Of all the lower bounds, we are interested in only the greatest (because it implies all the rest), and of all the upper bounds, we are interested in only the smallest (because it implies all the rest). If between those two bounds there is a number, that is, if the lower bound is smaller or equal to the upper, a solution exists: we can use the average of the lower and upper bound as . Otherwise, the solution does not exist.
The task is also solvable with binary search; we leave the details for the reader to practise.
Comments