Guys, please answer this, it won't take much time for those who have already solved this.↵
↵
http://mirror.codeforces.com/contest/552/problem/C↵
↵
In this problem, if $X \le 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^n$ 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 \le w^k$. I can't work any further.↵
↵
I am not able to prove how.↵
↵
↵
Ok, guys I got it!!!! (someone helped me). Here's a more easy proof.↵
↵
Lets think a different way. What are the coin changes that I can make using $w^{k+2}$. What is the smallest such change? The smallest change is equal to when we put $w^{k+2}$ on the left and all smaller weights on the right i.e.↵
↵
$w^{k+2}-w^{k+1}-w^k-....-w^0$↵
↵
$w^{k+2} - ($w^{k+2}$ — 1)/($w-1$) ↵
↵
But this amount is greater than $w^k$.↵
↵
Thus, if we use $w^{k+2}$, the change must be greater than $w^k$. But, $X \le w^k$. So, we can't make any such X. Proof is complete.
↵
http://mirror.codeforces.com/contest/552/problem/C↵
↵
In this problem, if $X \le 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^n$ 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 \le w^k$. I can't work any further.↵
↵
I am not able to prove how.↵
↵
↵
Ok, guys I got it!!!! (someone helped me). Here's a more easy proof.↵
↵
Lets think a different way. What are the coin changes that I can make using $w^{k+2}$. What is the smallest such change? The smallest change is equal to when we put $w^{k+2}$ on the left and all smaller weights on the right i.e.↵
↵
$w^{k+2}-w^{k+1}-w^k-....-w^0$↵
↵
$w^{k+2} - ($w^{k+2}$ — 1)/($w-1$) ↵
↵
But this amount is greater than $w^k$.↵
↵
Thus, if we use $w^{k+2}$, the change must be greater than $w^k$. But, $X \le w^k$. So, we can't make any such X. Proof is complete.
