SILVER  Cut the Silver Bar
A creditor wants a daily payment during n days from a poor miner in debt. Since the miner can not pay his daily obligation, he has negotiated with the creditor an alternative way, convenient for both parties, to pay his debt: the miner will give an equivalent of a 1µ (= 0.001mm) long piece of a silver bar as a guarantee towards the debt. The silver bar owned by the poor miner is initially nµ units long.
By the end of n days the miner would not have any more silver to give and the creditor would have received an amount of silver equivalent to that of the silver bar initially owned by the miner. By then, the miner expected to have enough money to pay the debt at the next day so that he would have back all his silver.
With this negotiation in mind, the miner has realized that it was not necessary to cut exactly 1µ silver piece from the bar everyday. For instance, at the third day he could give the creditor a 3µ silver piece, taking back the equivalent of a 2µ silver piece which the creditor should already have.
Since cutting the bar was rather laborious and time consuming, the miner wanted to minimize the number of cuts he needed to perform on his silver bar in order to make the daily silver deposits during the n days. Could you help him?
Input
Input consists of several cases, each one deﬁned by a line containing a positive integer number n (representing the length in micras of the silver bar and the number of days of the amortization period). You may assume that 0 < n < 20000. The end of the input is recognized by a line with 0.
Output
For each given case, output one line with a single number: the minimum number of cuts in which to cut a silver bar of length nµ to guarantee the debt during n days.
Example
Input: 1
5
3
0
Output: 0
2
1
hide comments
prafulla_1503:
20200531 16:10:09
good question...everyone should solve it. 

harry_shit:
20190604 14:45:55
advice:go easy on this,don't think too hard 

markaman:
20181231 15:06:18
Classroom riddle


csasi:
20180926 17:03:01
Smallest length of code in c++, after hello world or an addition problem. 

shashankpathak:
20180924 19:12:22
What is this question statement is not clear.Please if anyone can clarify it 

richardks3647:
20180721 07:03:17
AC in one go 

ameyanator:
20180123 20:26:12
Ohh lol. When I'd thought of the greedy i was like cmon that's too simple. Anyways coded it and submitted and viola! AC :') 

sinersnvrsleep:
20180108 01:59:50
Last edit: 20180130 08:53:56 

vijayrit:
20171218 15:30:58
just look out for the pattern. 

ab_hi_shek111:
20170909 11:44:52
My 100th :) 
Added by:  John Mario 
Date:  20110429 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  XXIV Colombian Programming Contest ACIS REDIS 2010  ACM ICPC 