USACO DEC07 Problem 'cheat' Analysis

by Rob Kolstad

This problem is one of data structure manipulation. The explicit example in the directions shows everything one needs to solve the task:

• Read the parameters
• Set up a 'dummy' deck so you can see where the cards end up
• Deal out the cards according to the procedure (making special note when Betsy's cards go by)
• Sort Betsy's positions
• Output Betsy's positions

The simplest brute force approach is simple until it comes time to "put the top card on the bottom". One can implement this in a few ways:

• save the top card, move all the cards 'up' one slot in an array, set the bottom card to the saved top card
• a linked list: remove the head element and place it on the end
• an oversized array that is large enough to accommodate a large number of cards-moved-to-bottom; keep an index of the 'decktop' and 'deckbottom'. Moving a card to the bottom just increments decktop and deckbottom while copying the first card to the bottom.

#include <stdio.h>

int cmp (int *a, int *b) { return *a - *b; }

main () {
    FILE *fin = fopen ("cheat.in", "r");
    FILE *fout = fopen ("cheat.out", "w");
    int n, k, p, i, j;
    int deck[100000 * 11], decktop, deckbottom, betsy[100000], nbetsy;
    int player;
    fscanf (fin, "%d %d %d", &n, &k, &p);

    for (i = 0; i < k; i++) deck[i] = i;
    player = decktop = 0;
    deckbottom = k-1;
    for (i = 0; i < k; i++) {        /* k cards to be dealt */
        /*printf ("deal %d to player %d\n", deck[decktop]+1, player);*/
        if (player == n-1) betsy[nbetsy++] = deck[decktop]+1;
        player = (player + 1) % n;
        decktop++;              /* that card is gone */
        for (j = 0; j < p; j++)
            deck[++deckbottom] = deck[decktop++];   /* card to bottom */
    }
    qsort(betsy, k/n, sizeof (int), cmp);
    for (i = 0; i < k/n; i++) fprintf (fout, "%d\n", betsy[i]);
    exit (0);
}