Internet Problem Solving Contest

• This problem has no input files.

Yvonne and Zara are playing a card game. The game is played with a standard 52-card deck. In this game we don’t care about specific ranks or suits, only about color (red or black). So it is enough to note that the deck contains exactly 26 red and 26 black cards.

Before the game Yvonne and Zara agree on a positive integer k. The game is then played as follows:

1. Yvonne takes the deck, removes any k cards and lays them out into a sequence in front of her.
2. Zara takes the remainder of the deck, removes any k cards and lays them out into a sequence in front of her. Zara is not allowed to choose the same sequence of red and black cards as Yvonne.
3. The girls shuffle the remainder of the deck.
4. The girls deal cards from the top of the deck into a sequence. If at any moment the colors of the last k cards dealt from the deck match Yvonne’s sequence, Yvonne wins. If the last k cards match Zara’s sequence, Zara wins.
5. If they run out of cards in the deck and neither girl has won the game, they decide the winner by flipping a fair coin.

Example of gameplay

• Yvonne chooses the sequence “red, red, black”.
• Zara chooses the sequence “black, black, black”.
• The remainder of the deck (24 red and 22 black cards) is shuffled.
• The girls start dealing cards off the top: red, black, black, red, red, red, black.
• At this moment the last three cards are “red, red, black”, which is precisely Yvonne’s sequence. The game is now over – Yvonne won.

Problem specification

You are given the value k. Assume that each girl wants to maximize her probability of winning and that they both play the game optimally.

In the easy subproblem L1 determine which girl is more likely to win the game.

In the hard subproblem L2 determine the probability of Yvonne winning the game.

Input specification

There is no input.

Output specification

Output exactly 26 lines, corresponding to k = 1, 2, …, 26.

In the easy subproblem L1 each line should contain the name of the girl who is more likely to win the game (either “Yvonne” or “Zara”). In case they are both equally likely to win, print the string “tie” instead.

In the hard subproblem L2 each line should contain the probability that Yvonne wins the game for that particular value k, assuming both girls play the game optimally. Output at least 10 decimal places. Solutions that differ from our answer by at most 10⁻⁹ will be accepted as correct.

Example

Both for k = 1 and for k = 2 the correct output for L1 is “tie” and the correct output for L2 is “0.5000000000”.

Even though the game seems advantageous for Yvonne, because she gets to choose her sequence first, there isn’t much she can do if the sequences are short. For k = 1 there is essentially only one possibility: Yvonne chooses one color, Zara chooses the other color, and the first card off the deck decides the game.

For k = 2 one optimal choice for Yvonne is the sequence “red, black”, and then an optimal choice for Zara is the sequence “black, red”. It should be obvious that the resulting game is symmetric, which means that each girl wins it with probability 0.5.