SPOJ.com - Problem COINS

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.

Submit solution!

hide comments

< Previous 27 28 29 30 31 32 33 34 35 36 37 Next >

	hackerman97: 2015-12-24 18:12:08 long long int cost me 3 WA's
	naveenarun: 2015-12-19 06:12:44 Troubleshooting for c++: - Did you use 'long long int' instead of 'long int'? - Did you either (a) make your map global or (b) pass your map by reference? - Did you memoize your coin values to save time? - Did you check to make sure the input is nonempty? It took me many, many tries to figure these out.
	pv: 2015-12-17 18:48:41 Okay, my approach for this question is as follows : * I have computed and stored the values for coins from 0 to 1000000 in an array using the logic max(i, arr[i/2] + arr[i/3] + arr[i/4]) * Am doing top down dp and for all values less than or equal to 1000000 , I use this array to obtain values. (The logic for all values greater than 1000000 is the same as the one used above.) But I still get WA. Can anyone please point out the mistake in my approach?
	Akanksha Thareja: 2015-12-16 19:39:42 Yeah thanks @AlphaDecay. I got that resolved. :)
	AlphaDecay: 2015-12-16 18:58:09 @akanksha The input can be very large (10^9) and if you are making an array with size of the input it would cause SIGSEV. Last edit: 2015-12-16 18:58:50
	Akanksha Thareja: 2015-12-16 15:17:17 Could anybody tell what could be the possible reasons for an SIGSEV error in the code for this problem?
	rjenni: 2015-12-09 10:44:18 Got finally an AC! Attention! Do not read how much test cases! Repeat for a max of 10 times! Costs me 5 hours to find that out ^^
	Sid: 2015-11-30 14:14:36 AC with memoization in one go. At first I thought you get 3 coins in return of 1 only a single time. The problem statement is misleading as they have not mentioned that it can be multiple times but you can guess as single time is just too simple to be on a competitive platform. Some people are recommending esoteric ways of using scanf() in this and that way. There is just no need If your program is not working the problem is somewhere else as for me `while(cin >> n)` works. It should as `>>` operator returns cin. When while evaluates cin it should get the last input state of cin. So at the end EOF will come out to be false. And this makes the loop to stop at the end of file. On a terminal when you are testing you will have to use Ctrl+D(*nix)/Ctrl+Z(windows) to send EOF.
	Timmy Jose: 2015-11-25 19:40:00 Damn... my Java solution got accepted but my C++ solution was causing problems due to the extra space at the end of the input file. My check while (!feof(stdin) { scanf("%lld", &n); ...} was causing the last space to trigger another run with the same value of n! I had to reset n to -1 and check that condition to exit the loop and it got AC. scanf is a PITA sometimes... anybody have any elegant solutions for this? Last edit: 2015-11-25 19:40:40
	pranavanurag: 2015-11-04 20:16:27 You may solve this problem using memoization, but since an array would be too big, try implementing a class with a key and a value with its members to store sub-problem answers along with the number itself. This way you can avoid using maps, which I found confusing. [C++]

Submit solution!

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