Algorithm


Problem Name: 2 AD-HOC - beecrowd | 1327

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1327

Drop Out

 

By Ricardo Anido Brazil

Timelimit: 1

Drop Out is the name of a simple card game which is played with a normal deck of 52 cards. Cards are ordered by rank (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jockey, Queen, King), with Ace being the smallest and King the largest value. Card suits are disregarded. Players (at least two) sit around a table and a shuffled deck is put in the center of the table, card faces down. At the start of the game, all players are “active”. The game proceeds in rounds. In each round, active players are dealt one card from the deck, in clockwise direction regarding their sitting positions. The players who are dealt the smallest card in the round drop out of the game and become inactive. Notice that up to four players may drop out at each round. The game ends when there remains one only active player, which is the winner. If the entire deck is played out before a round finishes, the game is over and all active players at the beginning of this last round are winners.

Given the number of players, their names and a shuffled deck of cards, you must write a program to simulate the game and determine the winner or winners.

 

Input

 

The input contains several test cases. Each test case consists of six lines. The first line contains an integer N , indicating the number of players in the game (2 ≤ N ≤ 20). The second line contains a list of player names, separated by spaces. A player name is composed of at most 16 letters from the English alphabet (from 'A' through 'Z' and 'a' through 'z'). Cards are dealt to players in the order given by the list. The next four lines contain the description of the shuffled deck. Card ranks are represented by integers from one to thirteen (1, 11, 12 and 13 denote respectively Ace, Jockey, Queen and King cards). The deck is described in four lines of thirteen integers each, separated by a single space. The deck is listed from top to bottom, so the first card dealt is the first card listed. The end of input is indicated by N = 0.

The input must be read from standard input.

 

Output

 

For each test case in the input your program must produce one line of output, containing the name of the winner or winners. The list of winners must appear in same order given in the input, and each name must be followed by a space.

The output must be written to standard output.

 

 

 

Sample Input Sample Output

4
Sally Claire Mary Beatrice
1 2 3 4 5 6 7 8 8 10 11 12 13
1 2 3 4 5 6 7 9 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
6
Aline Barbie Helen Julia Mary Sally
10 5 9 7 6 10 2 13 1 8 11 12 11
7 11 4 13 4 9 6 8 13 11 2 1 5
9 6 5 3 9 4 1 12 12 13 6 1 10
3 2 7 7 2 4 8 10 5 3 8 3 12
0

Mary Beatrice
Helen

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <list>
#include <queue>
#include <vector>
#define FOR(i, a, b) for (int i = a; i  < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i  <  N; ++i)
#define REPIT(c, it) for (list::iterator it = c.begin(); it != c.end(); it++)
#define MAX 30
#define INF 0x3F3F3F3F
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long int64;
typedef pair < int, int> ii;
typedef vector<int> vi;

struct player {
    int card;
    char name[MAX];
};

int deck[52];

int main()
{
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n && n) {
        queue < player> jogadores;
        player jogador;
        int count = n, j = 0;
        REP(i, n)
        {
            cin >> jogador.name;
            jogadores.push(jogador);
        }
        REP(i, 52)
        cin >> deck[i];
        while (true) {
            int lower = 14;
            queue < player> queueAux, trash;
            if (jogadores.size() > 52 - j)
                break;
            while (!jogadores.empty()) {
                jogadores.front().card = deck[j];
                lower = min(deck[j++], lower);
                queueAux.push(jogadores.front());
                jogadores.pop();
            }
            while (!queueAux.empty()) {
                if (queueAux.front().card == lower)
                    trash.push(queueAux.front());
                else
                    jogadores.push(queueAux.front());
                queueAux.pop();
            }
            if (jogadores.empty()) {
                jogadores = trash;
                break;
            }
        }
        int r = 0;
        while (!jogadores.empty()) {
            cout << jogadores.front().name << " ";
            jogadores.pop();
        }
        cout << "\n";
    }
    return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
4
Sally Claire Mary Beatrice
1 2 3 4 5 6 7 8 8 10 11 12 13
1 2 3 4 5 6 7 9 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
1 2 3 4 5 6 7 8 9 10 11 12 13
6
Aline Barbie Helen Julia Mary Sally 10 5 9 7 6 10 2 13 1 8 11 12 11 7 11 4 13 4 9 6 8 13 11 2 1 5 9 6 5 3 9 4 1 12 12 13 6 1 10
3 2 7 7 2 4 8 10 5 3 8 3 12
0

Output

x
+
cmd
Mary Beatrice
Helen
Advertisements

Demonstration


Previous
#1321 Beecrowd Online Judge Solution 1321 Jollo Solution in C, C++, Java, Js and Python
Next
#1329 Beecrowd Online Judge Solution 1329 Head or Tail Solution in C, C++, Java, Js and Python