//----------------------------------------------------------------------- // File: prob.cpp // Description: Solve the Rings game // Author: Dave Mount (mount@cs.umd.edu) // Date: Feb 2003 // // This program is given an instance (a,b,c) of the rings game, // played by two players, Bilbo and Frodo. It determines which // player has a winning strategy. Here are the rules: // // Bilbo and Frodo alternate moves, with Bilbo going first. // Initially the board consists of three piles of rings which we // denote (a,b,c), which means that there are a rings in the first // pile, b in the second pile, and c in the third. The board // always consist of three numbers that are greater than or equal // to 0. During a move a player can do any one of the following: // // (1) Remove 1 ring from pile 1. // (2) Remove either 1 or 2 rings from pile 2. // (3) Remove either 1 or 2 or 3 rings from pile 3. // (4) Remove one ring each from all of the nonempty piles. // // The first player who cannot make a move loses. That is, if it // is a players turn to move and the board is (0,0,0) then he // loses. // // The input consists of a sequence of triples of integers, // separated by whitespace. The program reads the triple and // outputs the winner. The program is terminated by end of file or // the triple "0 0 0". // //----------------------------------------------------------------------- #include // standard library #include // input/ouput #include // assertion checking // Uncomment the following lines if using APCS classes // #include "apvector.h" // #include "apmatrix.h" // #include "apstack.h" // #include "apqueue.h" // #include "apstring.cpp" //----------------------------------------------------------------------- // Rings //----------------------------------------------------------------------- const int MAX_A = 100; // max rings per pile const int MAX_B = 100; const int MAX_C = 100; //----------------------------------------------------------------------- // playRings // Plays the game and outputs the winner. //----------------------------------------------------------------------- void playRings(int a, int b, int c) { cout << a << " " << b << " " << c << " "; if (1) cout << "Bilbo wins" << endl; else cout << "Frodo wins" << endl; } //----------------------------------------------------------------------- // main // Reads inputs and calls playRings() to determine actual winner. // // THIS CAN BE PROVIDED TO THE CONTESTANTS. //----------------------------------------------------------------------- int main() { int a, b, c; while (true) { cin >> a >> b >> c; if (!cin || (a == 0 && b == 0 && c == 0)) exit(0); playRings(a, b, c); } return 0; }