## COINS - Bytelandian gold coins

In Byteland they have a very strange monetary system.

Each Bytelandian gold coin has an integer number written on it. A coin n can be exchanged in a bank into three coins: n/2, n/3 and n/4. But these numbers are all rounded down (the banks have to make a profit).

You can also sell Bytelandian coins for American dollars. The exchange rate is 1:1. But you can not buy Bytelandian coins.

You have one gold coin. What is the maximum amount of American dollars you can get for it?

### Input

The input will contain several test cases (not more than 10). Each testcase is a single line with a number n, 0 <= n <= 1 000 000 000. It is the number written on your coin.

### Output

For each test case output a single line, containing the maximum amount of American dollars you can make.

### Example

```Input:
12
2

Output:
13
2
```

You can change 12 into 6, 4 and 3, and then change these into \$6+\$4+\$3 = \$13. If you try changing the coin 2 into 3 smaller coins, you will get 1, 0 and 0, and later you can get no more than \$1 out of them. It is better just to change the 2 coin directly into \$2.

hide comments
 < Previous 1 2 3 4 5 6 7 8 9 10 11 Next > priyanshuofcl: 2017-07-23 15:52:12 i have solved this problem with simple recursions with a little modifications, i am now learning dp, can anyone share code for that in c++ r15habhgup11: 2017-07-22 08:46:24 solved in one go use simply recursion i_insist: 2017-07-20 12:30:59 bottom up approach using map gives TLE, big time, can't figure out why??? https://ideone.com/abBj9J ash_maurya: 2017-07-18 16:47:41 Very straightforward DP problem. The only thing you have to keep in your mind is that you cannot use DP with memoization for N as big as 10^9 . You can settle for some number in order of 10^5 and then do recursion for N bigger than that. That's AC in 0.00 . larunrahul: 2017-07-11 13:49:29 For Java people, to read input, create a BufferedReader object and do the following to read the input while((str = br.readLine()) != null){ } Last edit: 2017-07-12 09:19:45 pratique007: 2017-07-10 00:20:46 my first DP on spoj, learned to use map in c++ ogamiq: 2017-07-05 22:18:28 My solution on ideone and during my testing is working fine. But I get time limit exceeded. How to cope with that kind of input, where number of test cases isn't provided first (C#)? Does the program need to close after time limit or is it enough to provide right output in this time? Last edit: 2017-07-05 22:19:03 gboduljak: 2017-06-25 18:12:13 awesome introduction to DP, must do for beginners bsiddhartha: 2017-06-24 10:33:24 while(scanf("%lld",&n)!=EOF) use this @mayank_tyagi :) mayank_tyagi: 2017-06-23 21:54:23 can some one clear the input format, do i have to scan no. of test cases

 Added by: Tomek Czajka Date: 2005-05-03 Time limit: 9s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS PERL6 VB.NET Resource: Purdue Programming Contest Training