GAME31 - The game of 31

The game of 31 was a favourite of con artists who rode the railroads in days of yore. The game is played with a deck of 24 cards: four labelled each of 1, 2, 3, 4, 5, 6. The cards in the deck are visible to both players, who alternately withdraw one card from the deck and place it on a pile. The object of the game is to be the last player to lay a card such that the sum of the cards in the pile does not exceed 31. Your task is to determine the eventual winner of a partially played game, assuming each player plays the remainder of the game using a perfect strategy.

For example, in the following game player B wins:

  • Player A plays 3
  • Player B plays 5
  • Player A plays 6
  • Player B plays 6
  • Player A plays 5
  • Player B plays 6

Input

The input will consist of several lines; each line consists of a sequence of zero or more digits representing a partially completed game. The first digit is player A's move; the second player B's move; and so on. You are to complete the game using a perfect strategy for both players and to determine who wins.

Output

For each game, print a line consisting of the input, followed by a space, followed by A or B to indicate the eventual winner of the game.

Example

Input:
356656
35665
3566
111126666
552525

Output:
356656 B
35665 B
3566 A
111126666 A
552525 A

Added by:Andres Tellez
Date:2011-08-22
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2022-08-11 11:00:53
Need some good resources for game theory
not being able to solve such questions like this one and GAME3-Yet another fancy game
;|
2015-05-26 21:29:19 Ankit Sultana
getline gave me a couple of wa :/
PS: My AC solution doesn't print anything for 'zero digits'
2014-12-26 10:44:16 gourav pathak
brute force solution passes in the given time limit
2013-02-07 16:38:11 strings
please explain i/o... is there blank line after every input?? Do we have to process a blank line?? Should we print a blank line after every case o/p ??
2012-12-21 09:11:19 Aditya Pande
nice problem. learnt a lot about game theory...:)
2012-08-15 05:19:59 AC Srinivas
@skmiiita case 3: (current sum: 20; to get 31-required 11 to finish) player A will play 4 making current sum 24, player B can only make sum of 25-30(with cards 1-6), so player A can make it 31 and finish.

Last edit: 2012-08-15 05:29:24
2011-11-26 19:26:02 skmiiita
can anyone explain case 3.
i mean it is similar to case 1 and case 2 but answer is different.
2011-11-14 14:13:46 Buda IM (retired)
Please clear out IO matters. Are there empty lines between every test case, and should we print the empty lines after each output.
2011-08-30 12:30:33 Ankur Brahmbhatt
should the output for zero digits be:" A"
and for input:1
output:"1 B"?
2011-08-26 22:18:07 Naman
shouldn't be output of 4th and 5th example be B wins??
4th-B picks 1 (sum 31) => A loses in next turn
5th-A picks anything(1,2,3,4,5,6) B picks counter(6,5,4,3,2,1) (sum 31) => A loses in next turn

Edit: Sorry I forgot "deck of 24 cards"

Last edit: 2011-08-27 21:13:44
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.