### patelvaidik's blog

By patelvaidik, history, 4 weeks ago, , Hello, In Problem C, we have to find the value of x,y,z for given n,p,w,d value.

x+y+z=n             equation-1
x*w + y*d = p       equation-2

Let assume, if(x,y,z) is one solution, then x*w + y*d = p  where w>d already given.

->(x*w + w*d - w*d + y*d = p )  =====>( (x+d)*w + (y-w)*d = p  )
so if (x,y,z) is valid triplet then (x+d,y-w,z) is also valid triplet.
->we know that x>=0 ,y>=0 ,z>=0 is required,

->if we do above operation (x,y,z) ====> (x+d,y-w,z) ==> (x+(2*d),y-(2*w),z) ... ==> (x1-d,y1+w,z1) ==> (x1,y1,z1).
then finally we get y < w where 1<=w<=10 ^5.

->so we linearly check all value of y, for 0<=y<=w-1.
using y we find appropriate x and z value.

->if we do not find any triplet (x,y,z) then print -1.

Time complexity:- O(n).

[submission:62536673]

https://codeforces.com/contest/1244/submission/62536673

Thank you.

patelvaidik Comments (2)
 » Auto comment: topic has been updated by patelvaidik (previous revision, new revision, compare).
 » There is MathJax on site, rewrite your solution in well-formatted style.