333iq's blog

By 333iq, history, 4 weeks ago, In English,

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. (http://codeforces.com/contest/1244/submission/62568232)

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it