/***************************************************************************** * Speed * * Written by T. Yoshino *****************************************************************************/ #include #include #include #include #include #include using namespace std; /***************************************************************************** * Datatype Definitions *****************************************************************************/ typedef int Card; typedef list Deck; typedef pair Table; typedef vector Tableau; #define MAKE_CARD(s, r) Card((r) << 2 | (s)) #define SUIT_OF(c) ((c) & 3) #define RANK_OF(c) ((c) >> 2) #define VACANT (-1) #define TIME_PLACE_RIGHT 500 #define TIME_PLACE_LEFT 700 #define TIME_DRAW 300 #define TIME_CANCEL 500 /***************************************************************************** * Constants and Global Variables *****************************************************************************/ static const char* suit_order = "CDHS"; static const char* rank_order = "23456789XJQKA"; static vector suit_map(256, -1); static vector rank_map(256, -1); /***************************************************************************** * Card Support Functions *****************************************************************************/ static inline Card read_card(istream& in) { #define _(c) ((int)(c) & 0xFF) string s; in >> s; assert(s.size() == 2); assert(suit_map[_(s[0])] >= 0 && rank_map[_(s[1])] >= 0); return MAKE_CARD(suit_map[_(s[0])], rank_map[_(s[1])]); #undef _ } #ifdef _DEBUG static inline ostream& write_card(ostream& out, Card c) { if(c == VACANT) return out << "**"; else return out << suit_order[SUIT_OF(c)] << rank_order[RANK_OF(c)]; } #endif//_DEBUG static inline bool is_neighbor(const Card a, const Card b) { const int diff = (13 + RANK_OF(a) - RANK_OF(b)) % 13; return diff == 1 || diff == 12; } /***************************************************************************** * Main Routine *****************************************************************************/ enum EventType { PUT_TABLE, DRAW_CARD, FINISH, ERROR = -1 }; struct Event { /** Time of the event */ unsigned time; /** Player in action */ int player; /** Type of this event */ EventType type; /** Which table to place a card */ int table; /** Card to be placed */ Card card; /** Original place / Destination place */ int place; Event() : type(ERROR) { } Event(unsigned time, int player, EventType type) : time(time), player(player), type(type) { } }; #define PLACE_DECK (-1) #define PLACE_TABLEAU(index) (index) #ifdef _DEBUG ostream& operator << (ostream& out, const Event& e) { out << "Event @" << e.time << " player " << char('A' + e.player) << " "; switch(e.type) { case FINISH: out << "Finish"; break; case DRAW_CARD: write_card(out << "Draw card ", e.card) << " to tableau #" << e.place; break; case PUT_TABLE: write_card(out << "Put card ", e.card) << " to table " << char('A' + e.table) << " from "; if(e.place == PLACE_DECK) out << "deck"; else out << "tableau #" << e.place; break; default: assert(false); } return out; } #endif//_DEBUG enum PlayerId { PLAYER_A = 0, PLAYER_B = 1, NUM_PLAYERS }; #define OPPOSITE(id) ((int)(id) ^ 1) struct Player { /** Identifier */ PlayerId id; /** Deck */ Deck deck; /** Tableau */ Tableau tableau; /** Reference to the tables */ vector* tables; /** Flag indicating whether this player is active or not */ bool active; /** Current ongoing (or last) event */ Event event; public: Player(PlayerId id, const list& deck, vector
* tables) : id(id), deck(deck), tableau(4, VACANT), active(false), event(), tables(tables) { } private: bool empty() const { return deck.empty(); } Card draw() { Card card = deck.front(); deck.pop_front(); return card; } int vacant_tableau() const { for(int i = 0; i < tableau.size(); i++) if(tableau[i] == VACANT) return i; return -1; } int occupied_count() const { int count = 0; for(int i = 0; i < tableau.size(); i++) if(tableau[i] != VACANT) count++; return count; } void begin_move(const Event& e) { assert(!active); #ifdef _DEBUG cerr << "Next: " << e << endl; #endif//_DEBUG event = e; active = true; } int neighbor_minimum(const Card c) { int min_at = -1; for(int i = 0; i < tableau.size(); i++) { if(tableau[i] == VACANT) continue; if(is_neighbor(tableau[i], c)) min_at = min_at < 0 || tableau[i] < tableau[min_at] ? i : min_at; } return min_at; } public: /** * Set up for a game by filling the tableau */ void prepare() { for(int i = 0; i < tableau.size() && !empty(); i++) tableau[i] = draw(); } /** * Start moving */ void start(unsigned time) { Event e(time + TIME_PLACE_RIGHT, id, PUT_TABLE); if(!empty()) e.card = draw(), e.table = id, e.place = PLACE_DECK; else { int index = -1; for(int i = 0; i < tableau.size(); i++) if(tableau[i] != VACANT) { index = i; break; } assert(index >= 0); e.card = tableau[index], e.table = id, e.place = PLACE_TABLEAU(index); tableau[index] = VACANT; } begin_move(e); } /** * Complete one move */ const Event& end_move() { assert(active); switch(event.type) { case DRAW_CARD: assert(tableau[event.place] == VACANT); tableau[event.place] = event.card; break; case PUT_TABLE: (*tables)[event.table] = make_pair(id, event.card); break; case FINISH: break; default: assert(false); } active = false; return event; } /** * Begin the next move, seeing the current condition */ void next_move(unsigned time) { assert(!active); const int not_filled = vacant_tableau(), filled_count = occupied_count(); if(filled_count == 0 && empty()) { // Finish condition Event e(time + 0, id, FINISH); for(int t = 0; t < NUM_PLAYERS; t++) if((*tables)[t].first == id) e.table = t, e.card = (*tables)[t].second; begin_move(e); } else if(not_filled >= 0 && !empty()) { // Must fill the tableau Event e(time + TIME_DRAW, id, DRAW_CARD); e.place = not_filled, e.card = draw(); begin_move(e); } else { // Move a card to the table, if possible. int selected_place; #define TRY_TABLE(t, delay) \ if((*tables)[t].second != VACANT && \ (selected_place = neighbor_minimum((*tables)[t].second)) >= 0) { \ Event e(time + delay, id, PUT_TABLE); \ e.table = t, e.place = selected_place, e.card = tableau[selected_place]; \ tableau[selected_place] = VACANT; begin_move(e); goto end_try; \ } TRY_TABLE(id, TIME_PLACE_RIGHT); TRY_TABLE(OPPOSITE(id), TIME_PLACE_LEFT); #undef TRY_TABLE end_try: ; } } /** * Notify the player that a card is placed on the table. * This may cause interruption of the action. */ void notify_put(const Event& e) { if(active && event.type == PUT_TABLE && event.table == e.table) { #ifdef _DEBUG cerr << char('A' + id) << " interrupted by " << char('A' + e.player) << endl; #endif//_DEBUG event.time = e.time + TIME_CANCEL; event.type = DRAW_CARD; assert(event.place != PLACE_DECK); } } }; PlayerId solve(const Deck& deckA, const Deck& deckB) { vector
tables(2); Player playerA(PLAYER_A, deckA, &tables), playerB(PLAYER_B, deckB, &tables); Player* players[] = {&playerA, &playerB}; unsigned current_time = 0; playerA.prepare(); playerB.prepare(); while(1) { #ifdef _DEBUG cerr << "Start @" << current_time << endl; #endif//_DEBUG tables[0] = tables[1] = make_pair(VACANT, VACANT); playerA.start(current_time); playerB.start(current_time); while(1) { Event e; #ifdef _DEBUG #define PROCESS(player) \ do { \ e = (player).end_move(); current_time = e.time; cerr << e << endl; \ if(e.type == FINISH) return (player).id; \ } while(0) #else //!_DEBUG #define PROCESS(player) \ do { \ e = (player).end_move(); current_time = e.time; \ if(e.type == FINISH) return (player).id; \ } while(0) #endif//!_DEBUG if(!playerA.active && !playerB.active) // Dead end break; // Only one of two is active else if(playerA.active && !playerB.active) PROCESS(playerA); else if(!playerA.active && playerB.active) PROCESS(playerB); else { // Both players active if(playerA.event.time != playerB.event.time) { // Process the earlier event if(playerA.event.time < playerB.event.time) PROCESS(playerA); else PROCESS(playerB); } else { // The same time, may conflict if(playerA.event.type == FINISH && playerB.event.type == FINISH) { // Order by the last card strength if(playerA.event.card > playerB.event.card) return PLAYER_A; else return PLAYER_B; } else if(playerA.event.type == PUT_TABLE && playerB.event.type == PUT_TABLE && playerA.event.table == playerB.event.table) { // Try to put on the same table // -> interrupt right-player PROCESS(*players[OPPOSITE(playerA.event.table)]); } else { // FINISH/DRAW_CARD, FINISH/PUT_TABLE, DRAW_CARD/PUT_TABLE // -> no conflict, process in parallel PROCESS(playerA); PROCESS(playerB); } } } // If the processed event is PUT_TABLE, may cause interruption. if(e.type == PUT_TABLE) players[OPPOSITE(e.player)]->notify_put(e); // And set up for the next move if(!playerA.active) playerA.next_move(current_time); if(!playerB.active) playerB.next_move(current_time); } // Dead end, restart from drawing } assert(false); } /***************************************************************************** * Bootstrap *****************************************************************************/ static void init() { const char* p; int i; for(p = suit_order, i = 0; *p; p++) suit_map[*p] = i++; for(p = rank_order, i = 0; *p; p++) rank_map[*p] = i++; } int main() { init(); int NA, NB; while(cin >> NA, NA) { Deck deckA, deckB; while(NA-- > 0) deckA.push_back(read_card(cin)); cin >> NB; while(NB-- > 0) deckB.push_back(read_card(cin)); switch(solve(deckA, deckB)) { case PLAYER_A: cout << "A wins." << endl; break; case PLAYER_B: cout << "B wins." << endl; break; default: assert(false); } } }