Hide

Problem G
Colorville

A simple matching game for children uses a board that is a sequence of colored squares. Each player has a game piece. Players alternate turns, drawing cards that contain either:

One colored square, or
Two colored squares of the same color.

Players move their pieces forward on the board:

to the next square that matches the single color on the card,
to the second matching square if the card has two of the same color,
or to the last square of the board if no appropriate match is found.

A player wins if their piece lands exactly on the last square. It is possible for all cards to be drawn and still have no winner.

Each square on the board is represented by a capital letter from A to Z. Below is a diagram of a sample board:

$\includegraphics[width=0.7\textwidth ]{color.png}$

A sample deck of cards might be:

R, B, GG, Y, P, B, P, RR

Example Game (3 Players)

Player 1 draws R,  moves to 1st square
Player 2 draws B,  moves to 5th square
Player 3 draws GG, moves to 8th square
Player 1 draws Y,  moves to 2nd square
Player 2 draws P,  moves to 11th square
Player 3 draws B,  moves to 9th square
Player 1 draws P,  moves to 4th square
Player 2 draws RR, Wins! (no Rs in front of piece so it goes to last square)

Using the same board and card sequence:

With 2 players, Player 1 wins after 7 cards.
With 4 players, no one wins after all 8 cards are drawn.

Input

The input consists of one or more games.

Each game starts with a line containing three integers:

<number_of_players> <number_of_squares> <number_of_cards>

Where:

number_of_players is between 1 and 4,
number_of_squares is between 1 and 79,
number_of_cards is between 1 and 200.

This is followed by:

One line representing the board layout (a string of capital letters, one per square).
Then number_of_cards lines, each representing a card (either one or two of the same capital letter).

The input ends when a line begins with 0 for the number of players. The other two values in that line are irrelevant and should be ignored.

Output

For each game, print one line:

If someone wins: Player X won after Y cards.
If no one wins: No player won after Z cards.

Always use the plural form “cards”.

Sample Input 1	Sample Output 1
2 13 8 RYGPBRYGBRPOP R B GG Y P B P RR 0 6 0	Player 1 won after 7 cards.

Sample Input 2	Sample Output 2
2 6 5 RYGRYB R YY G G B 0 6 0	Player 2 won after 4 cards.

Sample Input 3	Sample Output 3
3 9 6 QQQQQQQQQ Q QQ Q Q QQ Q 0 6 0	No player won after 6 cards.

Problem GColorville

Example Game (3 Players)

Input

Output

Problem G
Colorville