Guys, please answer this, it won't take much time for those who have already solved this.

http://codeforces.me/contest/552/problem/C

In this problem, if X ≤ w^k for where k is the largest possible, then we don't need to use all coins that have higher power than k + 1, i.e. coins w^k + 2, w^k + 3, ...wⁿ will not be used.

To start with the proof, I will take w^k + 2 first.

I need to prove that w^k + 2 is not used in all of the valid solutions which means, w^k + 2 doesn't occur either on the left or right side of the equation shown at the top. Now, if I could somehow prove that using w^k + 2 in left side or right side, I cannot arrive at a solution I would be complete with my proof. I will first put w^k + 2 in the left (along with X) and see. I have X + w^k + 2 on the left, I also know that X ≤ w^k. I can't work any further.

I am not able to prove how.