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$ $m a_{i} \geq (n - m) b_{i}$ .

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

Comments

There are no comments at the moment.