You are not logged in. Please login at www.codechef.com to post your questions!

×

# Need help in C and Java for a sample problem

 1 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 coder91 16●1●1●3 accept rate: 0% tojochacko ♦ 510●10●19●24 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. (27 Mar '12, 14:35) cyberax ♦♦

5 Answers:
 1 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 cyberax ♦♦ 3.4k●2●19●55 accept rate: 20%
 0 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!! import java.util.* ; class Platinum { public static void main(String args[ ]) { int m ; // m is no. of blocks of platinum Scanner ob=new Scanner(System.in); System.out.println("enter the no of blocks of platinum you want to exchange between 2 and 1000,000,000 included:"); m=ob.nextInt(); if(m<2 || m>1000000000 ) { System.out.println("You have entered a number out of the range specified! \n"); System.out.println("Please Enter number between 1 and 1000000000 included: \n"); } else if(m==2) { System.out.println("you can exchange "+m +" blocks of platinum for "+ m +" units of currency"); System.exit(0); } else { System.out.println("no of blocks of platinum you want to exchange:"+m); } int a=m/2; int b=m/3; int c=m/4; int d=a+b+c; System.out.println("you can exchange "+m +" blocks of platinum for "+ d +" units of currency"); } }  answered 27 Mar '12, 14:48 coder91 16●1●1●3 accept rate: 0% betlista ♦♦ 16.7k●49●114●223
 0 @cyberax hey can u check the code which i have already coded ...posted above which is successfully compiling or checkout this link text and let me know what can i do to improve it if u know java.. answered 28 Mar '12, 13:16 coder91 16●1●1●3 accept rate: 0%
 0 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 cyberax ♦♦ 3.4k●2●19●55 accept rate: 20%
 0 solved: import java.util.* ; class Factorial {  int fact(int m) { if(m<2) return 0; int result= Math.max(fact(m/2)+fact(m/3)+fact(m/4),m); System.out.println(result); return result; }  } class Recursion {  public static void main (String args[]) { Factorial f =new Factorial(); int m ; // m is no. of blocks of platinum Scanner ob=new Scanner(System.in); System.out.println("enter the no of blocks of platinum you want to exchange between 2 and 1000,000,000 included:"); m=ob.nextInt(); if(m<2 || m>1000000000 ) { System.out.println("You have entered a number out of the range specified! \n"); System.out.println("Please Enter number between 2 and 1000000000 included: \n"); } else if(m==2) { System.out.println("you can exchange "+m +" blocks of platinum for "+ m +" units of currency"); System.exit(0); } else { int result=f.fact(m); System.out.println("you can exchange "+m +" blocks of platinum for "+ result +" units of currency"); } }  } answered 27 Mar '13, 16:28 codes_lover3 1 accept rate: 0% save your java file as Recursion.java and paste the above code..it will work... (27 Mar '13, 16:29) codes_lover3
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Tags:

×1,175
×1,119
×698

Asked: 27 Mar '12, 13:00

Seen: 6,944 times

Last updated: 27 Mar '13, 16:29