Boring Card Game
Time limit1sMemory limit128 MB
Simulate a deterministic card dealing and collecting process to find which player first collects cards 1-5, or detect an infinite cycle, with game counts up to 2^63.
- Level
Medium7 of 10
- Topics
- Simulation, Math, Implementation
- Solved
- No attempts yet
Statement
Neal Stephenson's novel Cryptonomicon describes a cryptographic algorithm built on a deck of playing cards, and it stresses that proper shuffling is crucial to the cipher's security. To show why randomness matters, we study a card game that uses no shuffling at all and is therefore completely predictable.
The game is a stripped-down variant of poker: every card is visible to everyone, and the players have no influence on the course of play whatsoever. Rather boring, isn't it?
A session consists of one or more games and is played by players. The players sit in a row, numbered from left to right. The deck holds exactly cards numbered .
Each game begins by dealing the cards in three rounds:
- Round 1: two cards go to each player in left-to-right order. Player 1 takes the two top-most cards, player 2 the next two, and so on through player .
- Round 2: the same step repeats, so every player receives two more cards.
- Round 3: every player receives one final card.
Each player therefore holds five cards. The player who ends up holding all five of the smallest-numbered cards (, in any order) wins the whole session.
If nobody wins, the cards are collected and a new game starts. They are gathered player by player from right to left, and one player's cards are always picked up one at a time in the reverse of the order in which they were dealt. Each collected card is placed on top of the deck, then the next on top of it, and so on. As a result, the top of the rebuilt deck holds player 1's cards, and its six top-most cards are the ones that were at positions in the previous deck.
For example, with two players the initial deck holds ten cards . In the first round player 1 gets and , and player 2 gets and . Then and go to player 1 and and to player 2; finally goes to player 1 and to player 2. When collecting, player 2's cards come first in the order , followed by player 1's cards . Because each card is stacked on top of the previous one, after one game the deck reads from top to bottom.
Write a program that determines the outcome of a session, so that you can spoil the game for its players.
Input
The input contains several sessions. Each session is given on two lines. The first line holds the number with . The second line lists the card numbers from the top of the deck to the bottom, separated by single spaces; every number appears exactly once. The last session is followed by a line containing a single zero.
Output
For each session print exactly one line. If no player ever wins, print Neverending game.; otherwise print Player P wins game number G., where is the winning player and is the number of the first game that is won (games are numbered from 1). Note that may exceed , but it is always smaller than .