/* Stamps The problem statement is a bit vague. We're supposed to compute the maximal coverage for each stamp denomination scheme, and output the coverage and the scheme with highest maximal coverage. The problem is ambiguous in the case when two schemes have the same coverage. The way this solution is written, whichever scheme has the least number of stamps is output. If both schemes have the same number of stamps, then output whichever was input first. */ #define S 10 /* max # of denominations per scheme */ #define N 10 /* max number of schemes */ #define MAX 100 /* max denomination */ int denom[N][S]; /* denom[i][k] is denomination of stamp k from scheme i */ int num[N]; /* num[i] is number of denominations in scheme i */ int cover[N]; /* cover[i] is maximum cover of scheme i */ void process(int i, int s) /* assigns to cover[i] the maximum cover of stamp scheme i */ { int size; /* maximum possible cover possible with stamps */ int j; /* index through coverable amounts */ int k; /* index through stamp denominations */ int array[S*MAX]; /* array[j] is # of stamps required to cover j cents */ size = denom[i][num[i]-1] * s + 1; /* maximum possible cover */ for (j = 0; j < size; j++) /* initialize to all uncovered denoms */ array[j] = 0; for (k = 0; k < num[i]; k++) /* can cover denoms that are stamps */ array[denom[i][k]] = 1; for (j = 1; j < size; j++) { if (array[j] == 0) break; for (k = 0; k < num[i]; k++) if (j+denom[i][k] < size) if (array[j] < s) if ((array[j+denom[i][k]] == 0) || (array[j+denom[i][k]] > array[j]+1)) array[j+denom[i][k]] = array[j] + 1; } /* j is index of first amount we can't cover */ cover[i] = j-1; } void main(void) { int s; /* maximum number of stamps on an envelope */ int n; /* number of schemes */ int i; /* scheme index */ int j; int m; /* index of scheme with max cover */ do { scanf("%d", &s); if (s == 0) break; scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &(num[i])); for (j = 0; j < num[i]; j++) scanf("%d", &(denom[i][j])); process(i, s); } m = 0; for (i = 1; i < n; i++) if ((cover[i] > cover[m]) || ((cover[i] == cover[m]) && (num[i] < num[m]))) m = i; printf("max coverage = %3d : ", cover[m]); for (j = 0; j < num[m]; j++) printf("%3d", denom[m][j]); printf("\n"); } while (1); }The test input was:
5 2 4 1 4 12 21 4 1 5 12 28 10 2 5 1 7 16 31 88 5 1 15 52 67 99 6 2 3 1 5 8 4 1 5 7 8 1 3 3 1 2 3 3 1 2 4 2 1 2 2 3 3 1 2 3 3 1 2 5 2 1 3 2 2 2 1 50 1 1 3 3 5 1 4 8 98 99 4 1 3 9 27 4 1 4 8 98 3 2 4 1 3 9 27 4 1 4 7 98 0The correct output was:
max coverage = 71 : 1 4 12 21 max coverage = 409 : 1 7 16 31 88 max coverage = 48 : 1 5 7 8 max coverage = 3 : 1 2 3 max coverage = 7 : 1 2 5 max coverage = 2 : 1 max coverage = 7 : 1 3 9 27 max coverage = 9 : 1 4 7 98
I am looking for a closed-form solution to this problem. If you know of one, please let me know.
My solution is:
/* Jonestown Treasury Problem */ #define N 100 /* max number of people */ int last(int n, int k) /* returns the last person to die, with n people, passing k times, assuming that the punch starts on person 1 (person 0, starting index at 0) NOTE: returns the index of the person STARTING AT 0 !!! */ { int person[N]; /* 1 means person is alive, 0 means dead */ int i; /* person who has punch */ int count; /* number of times punch passed to alive person */ int q; for (i = 0; i < n; i++) person[i] = 1; /* everyone starts alive */ i = 0; /* assume punch starts at person 0 */ person[i] = 0; /* person with punch dies */ for (q = 1; q < n; q++) { count = 0; while (count < k) /* pass punch k times */ { i = (i + 1) % n; /* pass punch */ if (person[i]) count ++; /* increment if alive person in circle */ } person[i] = 0; /* person with punch dies */ } /* person i was last to die */ return i; } void main(void) { int n, k, t, m; /* defined by problem */ int l; /* last person to die if start at 1 */ do { scanf("%d %d %d", &n, &k, &t); if (n == 0) break; l = last(n, k); m = (t-1 - l + n) % n + 1; /* rotate solution so person t is last to die */ /* need the -1 and +1 because of indexing at 0 */ printf("With %d people, passing %d times, keeping %d alive, start punch at person %d.\n", n, k, t, m); } while(1); }The test input was:
1 1 1 2 1 1 5 1 2 13 9 6 25 25 13 11 99 11 17 22 17 12 7 1 98 2 76 65 43 30 0 0 0The correct output was:
With 1 people, passing 1 times, keeping 1 alive, start punch at person 1. With 2 people, passing 1 times, keeping 1 alive, start punch at person 2. With 5 people, passing 1 times, keeping 2 alive, start punch at person 3. With 13 people, passing 9 times, keeping 6 alive, start punch at person 4. With 25 people, passing 25 times, keeping 13 alive, start punch at person 5. With 11 people, passing 99 times, keeping 11 alive, start punch at person 6. With 17 people, passing 22 times, keeping 17 alive, start punch at person 7. With 12 people, passing 7 times, keeping 1 alive, start punch at person 8. With 98 people, passing 2 times, keeping 76 alive, start punch at person 9. With 65 people, passing 43 times, keeping 30 alive, start punch at person 10.
/* Good But Not Perfect */ void factor(int n, int a[], int *num) /* returns the factors of a number */ { int i; for (i = 2; i < n; i++) if (n % i == 0) { a[0] = i; factor(n/i, a+1, num); *num = *num + 1; return; } /* n is prime */ a[0] = n; *num = 1; } int sum_digits(int n) /* sums the digits of a number */ { int sum = 0; while (n > 0) { sum += n % 10; n /= 10; } return sum; } int good(int n) /* returns 1 iff n is a good number */ { int num; /* number of factors of n */ int array[1000]; /* holds factors of n */ int i; int sum_fact; /* sum of digits of prime factors of n */ factor(n, array, &num); sum_fact = 0; for (i = 0; i < num; i++) sum_fact += sum_digits(array[i]); return sum_fact == sum_digits(n); } void main(void) { int n; do { scanf("%d", &n); if (n == 0) break; if (good(n)) printf("%d is a good number\n", n); else printf("%d is not a good number\n", n); } while (1); }The test input was:
22 4001 4049 4111 4191 4209 4253 4369 4373 4423 4457 4507 4513 4621 4637 4702 4733 4832 4855 4919 4999 6036 44 100 102 333 864 918 1001 2222 3984 4096 5436 9999 0The correct output was:
22 is a good number 4001 is a good number 4049 is a good number 4111 is a good number 4191 is a good number 4209 is a good number 4253 is a good number 4369 is a good number 4373 is a good number 4423 is a good number 4457 is a good number 4507 is a good number 4513 is a good number 4621 is a good number 4637 is a good number 4702 is a good number 4733 is a good number 4832 is a good number 4855 is a good number 4919 is a good number 4999 is a good number 6036 is a good number 44 is not a good number 100 is not a good number 102 is not a good number 333 is not a good number 864 is not a good number 918 is not a good number 1001 is not a good number 2222 is not a good number 3984 is not a good number 4096 is not a good number 5436 is not a good number 9999 is not a good number
/* Secret Agent Man */ void read_int(char *string, int *x, int *i) { sscanf(string+(*i), "%d", x); (*i) += abs(*x) / 10 + 2 + ((*x) < 0 ? 1 : 0); } int give(char *string, int rec, int *i) /* Based on the observation that it is not necessary to perform any kind of breadth-first search. The head of the organization can reach all of the spies, so you just have to find one spy that can reach the recipient spy. */ { int agent; int a2; for (agent = 0; 1; agent ++) { while (1) { read_int(string, &a2, i); if (a2 < 0) break; if (a2 == rec) return agent; } if (strlen(string+(*i)) < 2) break; } return -1; } void main(void) { char line[80]; int i; int rec; /* recipient of message */ int n; /* number of messages to process */ int who; /* who to give message to */ int m; gets(line); sscanf(line, "%d", &n); for (m = 1; m <= n; m ++) { gets(line); i = 0; read_int(line, &rec, &i); who = give(line, rec, &i); if (who == -1) printf("Message %d cannot be delivered. Agent #%d is unreachable.\n", m, rec); else printf("Message %d, destined for agent #%d, should be given to agent #%d.\n", m, rec, who); } }The test input was:
4 3 4 1 -1 2 -1 -4 0 1 -1 3 -1 2 3 1 -2 0 -1 3 0 -1 1 3 0 -6 0 1 -1 2 -1 3 -1 4 -1 5 -1 0 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1The correct output was:
Message 1, destined for agent #3, should be given to agent #4. Message 2 cannot be delivered. Agent #2 is unreachable. Message 3, destined for agent #0, should be given to agent #5. Message 4 cannot be delivered. Agent #0 is unreachable.