HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Recursion > problem:


50909 - Gold Coins

Guest
• Review clarifications (1)

Section problems

• 50723 - Tribonacci
• 50370 - Number of rectangles in a ...
• 50475 - Voice advertising
• 50909 - Gold Coins
• 50376 - Sequences
• 50725 - Fibonacci Series
• 50385 - The 3n + 1 problem
• 50911 - Symmetric Array
• 50381 - Sum of the numbers
• 50389 - Reverse an Array
• 50727 - Fibonacci Numbers
• 50415 - The Scientist

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Problem from codechef.

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. However, 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. However, you cannot 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 single line with a number N, 0 <= N <= 1 000 000 000. It is the number written on your coin.

Output:
The maximum amount of American dollars you can make.

Sample Input1:

Sample Input2:

Sample Input3:

12

2

120

Sample Output1:

Sample Output2:

Sample Output3:

13

2

144

 

Explanations:
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.

Для отправки решений необходимо выполнить вход.

www.contester.ru