My approach to yesterday's round Problem C.

Revision en3, by 444iq, 2019-10-14 16:49:40

Hello. I would be glad if this approach is helpful to anyone.

Solution: x = wins y = draw z = loss

First think that there is no z in the question and we have to satisfy x + y <= n and w*x + d*y = p. if(p % __gcd(w,d) != 0) answer is always -1. Else:

First calculate how much max wins we can achieve, i.e maxwins = p / w. Now calculate the remaining points that are left for us. It is p — maxwins*d, let's say it remaining_points. Now calculate how much max draws we can achieve with the remaining points. It will be remaining_points/d.

Now calculate total points = maxwins_point + draw_points. If this is equal to p, then here is our answer. We have to handle case x>=0 and y>=0 and z >=0.

Now if total_points < p. We calculate the difference between them. i.e difference = p — total_points. If there exists an answer then we must increase our draws and reduce our wins which we earlier calculated as max_wins and draws.

Suppose we increase draw by j more and decrease wins by k. Then this j and k must satisfy d*j — w*k = difference. Now we will iterate on j from 1 to say x. and for each j we check the condition whether there exists a useful k which satisfies our condition. If there is then we get the answer, else it will be -1.

Now what is x. X will depend on our max difference that will arise after dividing remaining_points(mentioned above) / d. since rp % d < d . hence max difference < d. so we iterate from 1 to 1e5. and check for every possible j and k.

Hope this is clear. (


  Rev. Lang. By When Δ Comment
en3 English 444iq 2019-10-14 16:49:40 72
en2 English 444iq 2019-10-14 16:49:19 2 Tiny change: 's clear.\n[](http://co' -> 's clear.\n(http://co'
en1 English 444iq 2019-10-14 16:48:48 1737 Initial revision (published)