Editorial for DMOPC '19 Contest 1 P1 - Test Scores


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.

Author: little_prince

One approach is to do some math. Suppose Veshy doesn't solve any of the problems. Therefore, his score would be -b_in_i. Then, for every problem he solves, Veshy effectively gains a_i+b_i marks. Therefore, Veshy needs to solve at least \frac{t_i+b_in_i}{a_i+b_i} problems. If the ceiling of this number is greater than n_i then Veshy cannot get t_i marks.

Another approach is to do binary search and continually guess the number of problems Veshy needs to answer, m such that ma_i\ge (n-m)b_i.

Time Complexity: \mathcal{O}(\sum_{i=1}^N \log n_i)


Comments

There are no comments at the moment.