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

×

The old forum can be viewed here. Seek help.

Need help in C and Java for a sample problem

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's gravatar image

coder91
16113
accept rate: 0%

edited 29 Mar '12, 14:44

tojochacko's gravatar image

tojochacko ♦
35591724

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 ♦♦

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 :)

link

answered 27 Mar '12, 21:04

cyberax's gravatar image

cyberax ♦♦
3.3k21755
accept rate: 20%

edited 27 Mar '12, 21:05

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");
 }
}
link

answered 27 Mar '12, 14:48

coder91's gravatar image

coder91
16113
accept rate: 0%

edited 31 May '12, 01:55

betlista's gravatar image

betlista ♦♦
12.5k45102192

@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..

link

answered 28 Mar '12, 13:16

coder91's gravatar image

coder91
16113
accept rate: 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.

link

answered 29 Mar '12, 02:07

cyberax's gravatar image

cyberax ♦♦
3.3k21755
accept rate: 20%

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");
    }

 }

}

link

answered 27 Mar '13, 16:28

codes_lover3's gravatar image

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

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

Tags:

×459
×410
×307

Asked: 27 Mar '12, 13:00

Seen: 2,382 times

Last updated: 27 Mar '13, 16:29