Editorial for DMOPC '19 Contest 1 P1 - Test Scores - Olympiads Online Judge

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_i n_i$ ~-b_i n_i~. Then, for every problem he solves, Veshy effectively gains $a_i+b_i$ ~a_i+b_i~ marks. Therefore, Veshy needs to solve at least $\frac{t_i+b_i n_i}{a_i+b_i}$ ~\frac{t_i+b_i n_i}{a_i+b_i}~ problems. If the ceiling of this number is greater than $n_i$ ~n_i~ then Veshy cannot get $t_i$ ~t_i~ marks.

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

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

Comments

There are no comments at the moment.