Answer to Question #64882 in C for sai

Question

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

Answer 1

Answer:
#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;
}