You have a block of platinum that can be exchanged in your bank either for cash or for smaller blocks of platinum. If you exchange a block of m grams, you get three blocks of weight m/2, m/3 and m/4 grams each. You don't get any fractional part, as the division process rounds down the value. If you exchange the block of platinum for cash, you get m units of currency. You can do any number of exchanges for smaller blocks or currency. Given the value of a block in grams as input, write a program that would print the largest possible currency value that you can receive as the output. Assume that the maximum value of a block that can be given as an input is 1,000,000,000 grams and the minimum value is 2 grams. Sample input 1: 12 Sample output 1: 13 Explanation: You can change 12 into blocks of 12/2 = 6, 12/3 = 4 and 12/4 = 3, and then exchange these for 6 + 4 + 3 = 13 units of currency 4 Sample input 2: 2 Sample output 2: 2 Explanation: If you exchange 2 grams into smaller blocks, it gives 2/2 = 1, 2/3 = 0, 2/4 = 0, only 1 unit. Instead, you can directly exchange the block for 2 units of currency. asked 27 Mar '12, 13:00

you can do it by recursion for example. let's define a function f that tells how much money you can obtain from N amount of platinum. the problem is obviously to find the value of f(N). let's have a look. you can either split your amount of platinum in 3 parts (N/2, N/3, N/4) thus getting f(N/2) + f(N/3) + f(N/4) units of currency, or exchanging all the amount, getting N units of currency. thus, it seems that f(N) = max( f(N/2) + f(N/3) + f(N/4), N ). am i right ? it should now be pretty easy to solve, as you just got a direct formula. if you read the comment i posted above, it should become really clear for you. good luck :) answered 27 Mar '12, 21:04

here is the code which i tried in JAVA .how to make it more efficient ? in the below code i am only able to code it to exchange the blocks for cash & i am not getting how to exchange it for blocks of smaller platinums ?? plz help!!
answered 27 Mar '12, 14:48

did you see my previous answer ? it seems you missed it : i don't see any recursive/memoization/dp function in your code. moreover, all the debug strings you print on standard output are not mentionned in the problem statement, meaning you probably shouldn't print them. please try to implement the f function, and after that new step, i'll give you some other hints, and so on until your code works. good luck. answered 29 Mar '12, 02:07

solved: import java.util.* ; class Factorial {
} class Recursion {
} answered 27 Mar '13, 16:28

You should have a look at this problem : http://www.codechef.com/problems/COINS . It is quite similar. Maybe comments and posted solutions will give you a hint. good luck.