UVa 246 - 10-20-30

contents

1. 1. Problem
2. 2. Input
3. 3. Output
4. 4. Sample Input
5. 5. Sample Output
6. 6. Solution

Problem

A simple solitaire card game called 10-20-30 uses a standard deck of 52 playing cards in which suit is irrelevant. The value of a face card (king, queen, jack) is 10. The value of an ace is one. The value of each of the other cards is the face value of the card (2, 3, 4, etc.). Cards are dealt from the top of the deck. You begin by dealing out seven cards, left to right forming seven piles. After playing a card on the rightmost pile, the next pile upon which you play a card is the leftmost pile.

For each card placed on a pile, check that pile to see if one of the following three card combinations totals 10, 20, or 30.

1. the first two and last one,

2. the first one and the last two, or

3. the last three cards.

If so, pick up the three cards and place them on the bottom of the deck. For this problem, always check the pile in the order just described. Collect the cards in the order they appear on the pile and put them at the bottom of the deck. Picking up three cards may expose three more cards that can be picked up. If so, pick them up. Continue until no more sets of three can be picked up from the pile.

For example, suppose a pile contains 5 9 7 3 where the 5 is at the first card of the pile, and then a 6 is played. The first two cards plus the last card (5 + 9 + 6) sum to 20. The new contents of the pile after picking up those three cards becomes 7 3. Also, the bottommost card in the deck is now the 6, the card above it is the 9, and the one above the 9 is the 5.

If a queen were played instead of the six, 5 + 9 + 10 = 24, and 5 + 3 + 10 = 18, but 7 + 3 + 10 = 20, so the last three cards would be picked up, leaving the pile as 5 9.

If a pile contains only three cards when the three sum to 10, 20, or 30, then the pile “disappears” when the cards are picked up. That is, subsequent play skips over the position that the now-empty pile occupied. You win if all the piles disappear. You lose if you are unable to deal a card. It is also possible to have a draw if neither of the previous two conditions ever occurs.

Write a program that will play games of 10-20-30 given initial card decks as input.

Input

Each input set consists of a sequence of 52 integers separated by spaces and/or ends of line. The integers represent card values of the initial deck for that game. The first integer is the top card of the deck. Input is terminated by a single zero (0) following the last deck.

Output

For each input set, print whether the result of the game is a win, loss, or a draw, and print the number of times a card is dealt before the game results can be determined. (A draw occurs as soon as the state of the game is repeated.) Use the format shown in the ``Sample Output” section.

Sample Input

2 6 5 10 10 4 10 10 10 4 5 10 4 5 10 9 7 6 1 7 6 9 5 3 10 10 4 10 9 2 1
10 1 10 10 10 3 10 9 8 10 8 7 1 2 8 6 7 3 3 8 2
4 3 2 10 8 10 6 8 9 5 8 10 5 3 5 4 6 9 9 1 7 6 3 5 10 10 8 10 9 10 10 7
2 6 10 10 4 10 1 3 10 1 1 10 2 2 10 4 10 7 7 10
10 5 4 3 5 7 10 8 2 3 9 10 8 4 5 1 7 6 7 2 6 9 10 2 3 10 3 4 4 9 10 1 1
10   5 10 10 1 8 10 7 8 10 6 10 10 10 9 6 2 10 10
0

Sample Output

Win : 66
Loss: 82
Draw: 73

Solution

給一副牌，按照順序發成七疊
在發了一張牌後，若有
(1) 下面一張與最上面兩張
(2) 下面兩張與最上面一張
(3) 最上面連續三張加起來點數為
10、20 或 30，則把這三張牌收進手牌(J, Q, K, 10)
依 (1)(2)(3) 順序檢查

若某疊牌拿起三張後仍符合上述條件，則一直拿到不符合條件為止，若有某一疊牌被完全拿光，則以後不在往這疊發牌。

請輸出最後結果
(1) win 七疊牌都清空了
(2) lose 手牌空了
(3) draw 進入無窮迴圈

簡單地說，一開始盤面上有七疊牌組，一開始都有兩張牌，接著依序從左邊至右開始發牌，發的同時依序檢查是否可以將牌組的牌符合 10-20-30 的規則收回手牌 (發牌者手上) 中。

最麻煩的地方在於迴圈判斷，在這裡使用一個最簡單的 binary tree 方式。

#include <stdio.h> 
#include <string.h>
#include <deque>
#include <queue>
#include <set>
using namespace std;
struct state {
    int v[64];
    state() {
        memset(v, 0, sizeof(v));
    }
    bool operator<(const state &x) const {
        return memcmp(v, x.v, sizeof(state)) < 0;
    }
};
deque<int> pile[7];
queue<int> hand;
set<state> record;
void reduce(deque<int> &pile) {
    while(pile.size() >= 3) {
        int n = pile.size();
        if((pile[0] + pile[1] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[1]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_front();
            pile.pop_back();
        } else if((pile[0] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[0]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_front();
            pile.pop_back();
            pile.pop_back();
        } else if((pile[n-3] + pile[n-2] + pile[n-1])%10 == 0) {
            hand.push(pile[n-3]), hand.push(pile[n-2]), hand.push(pile[n-1]);
            pile.pop_back();
            pile.pop_back();
            pile.pop_back();
        } else {
            break;
        }
    }
}
int main() {
    int x;
    while(true) {
        while(!hand.empty())
            hand.pop();
        for(int i = 0; i < 7; i++) 
            pile[i].clear();
            
        for(int i = 0; i < 52; i++) {
            scanf("%d", &x);
            if(x == 0)	return 0;
            hand.push(x);
        }
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        for(int i = 0; i < 7; i++)
            pile[i].push_back(hand.front()), hand.pop();
        
        int end = 0, loop = 14;
        while(!end) {
            for(int i = 0; i < 7; i++) {
                if(pile[i].size() == 0)
                    continue;
                loop++;
                pile[i].push_back(hand.front()), hand.pop();
                reduce(pile[i]);
                if(hand.size() == 52) {
                    printf("Win : %d\n", loop);
                    end = 1;
                    break;
                }
                if(hand.size() == 0) {
                    printf("Loss: %d\n", loop);
                    end = 1;
                    break;
                }
                state s;
                int m = 0;
                for(int j = 0; j < 7; j++) {
                    for(int k = 0; k < pile[j].size(); k++)
                        s.v[m++] = pile[j][k];
                    s.v[m++] = 15;
                }
                queue<int> q = hand;
                while(!q.empty())
                    s.v[m++] = q.front(), q.pop();
                s.v[m++] = 15;
                if(record.find(s) != record.end()) {
                    printf("Draw: %d\n", loop);
                    end = 1;
                    break;
                }
                record.insert(s);
            }
        }
    }
    return 0;
}