While many card games involve some degree of luck depending on which cards you are dealt, it is often the decisions and choices of the players which steer the events of the game into a resulting win or loss. These games are often more entertaining to play and to watch, but the requirement of each player to develop a personal strategy is sometimes a barrier for younger players.
War is a card game well-suited to younger players who may have difficulty understanding rules and strategies, because it doesn't require the players to make any actual decisions! It is enjoyed by children all around the world, although it is known by different names in different places - for example, it is known as Battle in Britain, Tod und Leben in Germany and Пьяниц(P'yanitsa) in Russia.
The rules are as follows: a standard deck of 52 cards is shuffled and divided equally between the two players. Players take turns at the same time, revealing the top card of their decks. Whoever's revealed card shows the higher rank wins, and that player adds both of those cards to the bottom of their deck.
If both players flip cards of equal rank, then the players place the revealed cards aside into a
"winner's pot", then each reveal up to 3 more cards into that pot. However if a player has n=3 or less
cards remaining in their deck, then each player only adds n-1 cards to the pot. Play then resumes,
with the next winner also winning all of the cards in the pot. Turns continue until one player has no
more cards, at which point they lose.
You will simulate two people playing this card game, then determine who will win and how many turns it will take. To make sure everything is deterministic, let's be clear that when a player is adding "won" cards back into their deck, those cards are placed onto the bottom of the deck in the order in which they were revealed. For this purpose, let's say that Player 1 always reveals their card slightly before Player 2.
Let's walk through a short example to be clear about the order of events.
Cards are one of 13 possible ranks in ascending order 2, 3, 4, 5, 6, 7, 8, 9, T, J, Q, K, A,
and also 4 possible suits: Hearts (H), Diamonds (D), Clubs(C), and Spades (S).
For the sake of making the example short, let's pretend the players are playing with a 28-card deck,
starting with 14 cards each.
Turn │ Player 1 reveals │ Player 2 reveals │ Note
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
1 │ AH │ 9H │ Player 1 puts both cards on the bottom of their deck in order:
│ │ │ AH 9H
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
2 │ 9C │ TC │ Player 2 puts both cards on the bottom of their deck in order:
│ │ │ 9C TC
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
3 │ JH │ JS │ A tie!
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
│ QS │ AD │
- │ KD │ KS │ Each player reveals 3 cards
│ AS │ TD │
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
4 │ 8C │ 9S │ Player 2 puts all 10 cards on the bottom of their deck in order:
│ │ │ JH JS QS AD KD KS AS TD 8C 9S
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
5 │ 8H │ KC │ Player 2 puts both cards on the bottom of their deck in order:
│ │ │ 8H KC
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
6 │ 8S │ 8D │ A tie!
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
│ AC │ QC │
- │ TH │ 9D │ Each player reveals 3 cards
│ JC │ KH │
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
7 │ QH │ QD │ Another tie!
│ │ │ Player 1 only has 3 cards remaining at this point
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
- │ TS │ JD │ Each player reveals 2 cards
│ AH │ 9C │
──────┼──────────────────┼──────────────────┼──────────────────────────────────────────────────────────────────
8 │ 9H │ TC │ Player 2 puts all 16 cards on the bottom of their deck in order:
│ │ │ 8S 8D AC QC TH 9D JC KH QH QD TS JD AH 9C 9H TC
──────┴──────────────────┴──────────────────┴──────────────────────────────────────────────────────────────────
Player 1 has no more cards. Player 2 wins in 8 turns!
The deck needs to be shuffled before beginning. To simulate this we will use the
Linear Congruential Generator
(use A=445, C=700001 and M=2097151). We will begin with a sorted deck of cards, ascending by rank and grouped by
suit in the order "Hearts, Diamonds, Clubs, Spades". We will then use the LCG to generate 52 random values and calculate the
result of each modulo 52 to yield a list of 52 random numbers [r0, r1, r2, ... r50, r51]. Then go through each card starting from the0th position, and replace it with the card in therth position. For example, starting with the LCG
seed value ofx0 = 8756942` ...
LCG Value │ mod 52 │ Action
───────────┼────────┼────────────────────────────────────────────────────────────────────
8756942 │ - │ (Seed Value)
1032633 │ 17 │ Swap the card in position 0 (2H) with the card in position 17 (6D)
945617 │ 49 │ Swap the card in position 1 (3H) with the card in position 49 (QS)
2069366 │ 26 │ Swap the card in position 2 (4H) with the card in position 26 (2C)
918582 │ 2 │ Swap the card in position 3 (5H) with the card in position 2 (2C)
524546 │ 22 │ Swap the card in position 4 (6H) with the card in position 22 (JD)
After the entire deck has been shuffled, cards will be dealt to each player one-at-a-time, starting with Player 1.
Input Data
The first line will be Q, the quantity of testcases.
Q lines will then follow, each with a single seed integer x0.
Answer
Should be a string of Q pairs of space-separated integers W T, where W is the player who won, and T is the
quantity of turns completed before the game ended.
Example:
input data:
3
8756942
0
4775558
answer:
1 442 2 25 2 6923