DEPOSIT  Deposit
Banks offer deposit schemes of various kinds to attract customers. In an r year progressively reducing recurring deposit scheme (PRRDS) of a bank, a customer is required to deposit progressively reducing amounts every year for r years. Depending on the duration r of the scheme and the total amount T deposited in r years, the bank offers to return on maturity, i.e., after the expiry of r years, an amount R , which is equal to k times the amount deposited in the first year. The bank ensures that the return R looks attractive by making a suitable choice of k ; k being a natural number.
In a PRRDS, the amount to be deposited in each but the last two years is exactly equal to the sum of amounts to be deposited in the next two years. The amounts to be deposited in the last two years, say x in the last year and y in the last but one year, are progressively reducing (x, y > 0;y > x) and are determined so that the total amount deposited in r years is exactly equal to the specified amount T . Assume that all deposits are in whole number of Rupees.
Write a program for the bank, so that given r , k and T , the program computes x and y for which the return R is maximum. For example in a 4year scheme with r = 4 , k = 3 and T = 500 , the progressively reducing recurring deposits 248, 126, 122 and 4, ensures the maximum return R = 744 with x = 4 and y = 122 .
Input
The input may contain multiple test cases.
For each test case there is only one input line. The line gives values of r , k and T . Assume that r is not greater than 20.
A line containing a zero `0' as the first character follows the last case.
Output
For each test case there is only one output line. The line gives the computed values of x , y and R .
Example
Input 4 3 500 5 3 10000 6 4 8000 8 5 12000 0 Output 4 122 744 5 1425 12855 1 666 13332 1 363 23635
hide comments
holmesherlock:
20171223 09:00:21
good logical problem


arjun:
20140731 15:51:53
edit: Don't post answers Last edit: 20141208 17:39:38 

nitesh kumar:
20140511 21:39:33
wats the limit of T??


Momontho Mashak Monmoy:
20120808 09:25:09
After plenty of WA, in case of tie in R, I minimized x & then got AC, this requirement should've been stated in the problem statement . 

aman garg:
20120622 17:37:25
Can anyone please help me.I am getting wrong answer continuously.code id :7196103 

Romal Thoppilan:
20110823 21:41:21
What to do in cases where ,


Nathaniel Barshay:
20100810 04:51:58
Note that 64bit integers are necessary and sufficient 

Harsh:
20100615 08:31:09
What should be the output when no such x,y values are poosible for given T and r 

Seshadri R:
20100504 07:01:10
SPOJ server seems to have a clock that runs both forward and backward in time. This problem is posted on 20081209 but there are comments on 20090217, 20090704 and 20090707. Probably, these are from those who have the privilege to have a preview before the problem is released for all SPOJ registrants? 

Seshadri R:
20100504 06:41:23
@Ravi Kiran: r will be at least two since the output has to contain values of x and y. So, the case that r=1 will never arise 
Added by:  Duc 
Date:  20081209 
Time limit:  0.254s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  ACM Kanpur 2007 