UVA Problem 10935 – Throwing cards away I Solution

UVA Problem 10935 – Throwing cards away I Solution:


Click here to go to this problem in uva Online Judge.

Solving Technique:

It is possible possible to solve this problem in many ways. Using STL queue is one way. But I try to avoid built-in functions just so I can make my base stronger and learn new things. Here I have written my own queue implementation.

The problem says we have a deck of card which is ordered 1 to n. n is the input. Ex, if 7 is input then we have 1,2,3,4,5,6,7 cards on deck.

Next, it says discard the top card, so card after him is now topmost. Then move the topmost card of the deck to the end of the deck. Keep continuing this until two card are left of deck. The process happens like this, if n = 5 is given,

1 2 3 4 5 /* Initial array enqueued 1 through 5 */

/* First Iteration */
2 3 4 5   /* 1 is discarded and printed */
3 4 5 2   /* 2 is moved to end of queue */

/* Next Iteration */
4 5 2    /* 3 discarded and printed */
5 2 4    /* 4 moved to end of queue */

/* Next Iteration */
2 4     /* 5 discarded and printed */
4 2     /* 4 is also discarded since we want to find the last card and so we print the last card reaming on deck which is 2 */

Notice even though we discard 1 card we move the other one to the end of the deck. So the deck size is decreasing by one ( don’t get confused here ).

Since one card is thrown away and another is moved to the end i thought hey its a queue. Why? queue has a function called dequeue which discards the topmost ( or actually the element in front ). Now another card is moved to end of the deck. Queue has a similar function called enqueue which adds an element to the end of the array or queue. Also since Queue is a FIFO ( FIRST IN FIRST OUT ) data structure. So what is on the front of deck is processed first and that is what we need.

Think of it like a game where each cards are aligned horizontally and each card is a person. Now we tell the player who is in front of the line to move away so the player that was after him is in front of the line. This time we tell the player to move to the end of line. We continue this discard and adding the next one to the end  until there are only two player left. So of these two player the last player is the remaining cards and the players that were moved from line are the discarded cards.

Our input terminates with 0 ( zero ). I have explained the code below with comments.

Important:  Be sure to add or print a new line after each output. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer.


Input:

7
19
10
6
0

Output:

Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4

Code:

/*
 * @author quickgrid ( Asif Ahmed )
 * @link   https://quickgrid.wordpress.com
 */

#include<stdio.h>
#define size 128

/*
 * unsigned since no item in our array is negative
 */
unsigned a[size], f = 0, r = 0;

void enqueue(unsigned k){
    /*
     * get a valid index in circular queue array
     */
    unsigned s = (r + 1) % (size + 1);

    /*
     * if true queue full, this check is for safety and can be deleted
     */
    if (f == s)
        return;

    /*
     * set the last element to given card
     */
    a[s] = k;
    /*
     * update the rear position marker
     */
    r = s;
}

unsigned dequeue(){
    /*
     * if true then queue empty, this check is for safety and can be deleted
     */
    if (f == r)
        return 0;

    /*
     * move the front marker one position in circular queue array
     */
    f = (f + 1) % (size + 1);
    /*
     * keep the value of last card for returning
     */
    unsigned k = a[f];
    a[f] = 0;
    return k;
}

int main(){
    register unsigned n, i;

    while (scanf("%u", &n) && n){
        /*
         * since there is one card there is no discarded card
         */
        if (n == 1){
            printf("Discarded cards:\n");
            printf("Remaining card: 1\n");
            continue;
        }

        f = 0, r = 0;
        for (i = 1; i <= n; ++i){
            /*
             * it says 1 to n cards on deck so i enqueue all cards serially
             */
            enqueue(i);
        }

        printf("Discarded cards: ");
        /*
         * stop when 2 cards on deck
         */
        while (f + 2 != r){
            printf("%u, ", dequeue());
            unsigned k = dequeue();
            enqueue(k);
        }

        /*
         * get position of last discardable card
         */
        f = (f + 1) % (size + 1);

        /*
         * print the last discardable card
         */
        printf("%u\n", a[f]);
        /*
         * now print the last remaining card on deck
         */
        printf("Remaining card: %u\n", a[r]);
    }
    return 0;
}
Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s