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.
Answers
Hey there!
Here's is your code.
#include <stdio.h>
#include <stdlib.h>
int maxn (int a, int b);
int exchangeBlock (int m);
void printPartinion (int ptn[], int n);
int exchangePartinion (int ptn[], int n);
void generatePartinion (int n, int ptn[], int crsum, int cridx, int *mx);
int generate (int n);
int
maxn (int a, int b)
{
return (a > b) ? a : b;
}
int
exchangeBlock (int m)
{
return m / 4 + m / 3 + m / 2;
}
void
printPartinion (int ptn[], int n)
{
int i;
for (i = 0; i < n; i++)
printf ("%d ", ptn[i]);
printf ("\n");
}
int
exchangePartinion (int ptn[], int n)
{
int mx = 0;
int i = 0;
for (i = 0; i < n; i++)
mx += exchangeBlock (ptn[i]);
return mx;
}
void
generatePartinion (int n, int ptn[], int crsum, int cridx, int *mx)
{
int num;
if (n == 0)
return;
/* If current sum is equal to n, then we found a partinion */
if (crsum == n)
{
printPartinion (ptn, cridx);
*mx = maxn (exchangePartinion (ptn, cridx), *mx);
printf ("__ %d\n", *mx);
}
/* Try placing all numbers from smallest to (n - current sum)
* at current index. The placed number must not be greater
* than previously placed numbers */
num = 1;
while (num <= n - crsum && (cridx == 0 || num <= ptn[cridx - 1]))
{
ptn[cridx] = num;
generatePartinion (n, ptn, crsum + num, cridx + 1, mx);
num++;
}
}
int
generate (int n)
{
int *ptn; /* array to store partinions */
int mx = 0; /* current largest currency */
ptn = (int *) malloc (n * sizeof (int));
generatePartinion (n, ptn, 0, 0, &mx);
return mx;
}
int
main ()
{
int grams = 0;
int exch = 0;
int bl = 0;
printf ("Input the value of the block in grams: ");
scanf ("%d", &grams);
if (grams > 1000000000 || grams < 2)
return 1;
/* Answer 1: */
printf ("\n");
exch = generate (grams);
printf ("\n%d - %d\n", grams, exch);
printf ("\nYou can get %d units of currency.\n", exch);
/* Answer 2: */
printf ("\n\n");
for (bl = 12; bl > 0; bl--)
{
exch = exchangeBlock (bl);
printf ("%d - %d\n", bl, exch);
}
for (bl = 24; bl > 12; bl--)
{
exch = exchangeBlock (bl);
printf ("%d - %d\n", bl, exch - 13);
}
exch = (grams / 12) * 13 + exchangeBlock ((grams + 12) % 12);
printf ("\nYou can get %d units of currency.\n", exch);
return 0;
}
______________________________
See the attachment for proper review.
______________________________
