/* 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); }