Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Обход дерева игры, α-β процедура

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

12/12/2006 | Практическое занятие 13 (задачи NEERC 2006) (F) |

*Ограничения: время – 3s/6s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

A card game, often called "Fool’s Game", is quite popular in Russia. We will describe a game for two
players. A standard deck of 36 cards is used. One suit is declared to be a trump.

A game consists of rounds. Before the round each player has several cards, one of the players is starting,
the other one is covering. The starting player starts by laying one or several cards of the same rank down
on the table. The number of cards must not exceed the number of cards the covering player has. The
covering player must in turn cover all the cards with some of her cards, laying them on the table above
the uncovered cards. A card can cover another if one of the following is true:

- it has the same suit and higher rank (ranks are ordered as usually: 6, 7, 8, 9, 10, J, Q, K, A);

- it is a trump and the card to cover is not a trump (a trump can only be covered by a higher trump).

After the cards on the table are all covered, the starting player can toss some more cards to be covered.
The rank of each card tossed must be among the ranks of the cards already on the table at the moment.
Now the newly added cards must be covered by the covering player, after that the starting player can
toss more cards, and so on. The starting player cannot toss more cards than the covering player has at
the moment.

The round ends when either the covering player cannot or does not want to cover all uncovered cards on
the table, or when the starting player cannot or does not want to toss more cards.

In the first case, when the covering player declares that she does not want to cover all uncovered cards
on the table, the starting player is given a chance to toss in more cards. The ranks of the cards tossed
must be among the ranks of the cards already on the table. The number of uncovered cards on the table
cannot exceed the number of cards that the covering player has at the moment. After that, the covering
player loses the round and takes all the cards from the table, adding them to her cards. Starting player
keeps her starting role and moves again in the next round.

In the second case, when all cards on the table are covered and the starting player cannot or does not
want to toss more cards, the covering player wins the round and the cards on the table are removed from
the game. The players’ roles for the next round are swapped: the covering player becomes the starting
one and vice versa.

If, after the end of the round, one of the players has no cards, and the other one has one or more cards,
then the player with no cards wins the game. If both players have no cards, then the player who was
starting in the last round wins the game.

Given the trump suit and the cards the players initially have, find out who wins the game if both play
optimally. Both players have full information about cards in the game.

The first line of the input file contains `n_1` and `n_2` — the number of cards that each of the players has in
the beginning of the round `(1\ ≤\ n_1;\ n_2\ ≤\ 6)`, and the trump suit (suit is specified using one letter: ‘S’ for
spades, ‘C’ for clubs, ‘D’ for diamonds, ‘H’ for hearts).

The second line contains `n_1` card descriptions — the cards of the first player. Each card is specified by
its rank (‘6’. . . ‘9’, ‘T’ for 10, ‘J’ for Jack, ‘Q’ for Queen, ‘K’ for King, ‘A’ for Ace) followed by its suit.
The third line contains `n_2` card descriptions — the cards of the covering player. The first player is the
starting player in the first round.

All cards in players’ hands are different.

Output “`FIRST`” if the first player wins the game, or “`SECOND`” if the second player does.

Sample Input #1

2 2 S KC AD 6S 7S

Sample Output #1

SECOND

Sample Input #2

2 2 D KC AD 6S 7S

Sample Output #2

FIRST

Sample Input #3

4 5 C AS 6S 7S 8S 9S TS JS QS KS

Sample Output #3

SECOND

Sample Input #4

3 2 C 6H JS JD AD 6C

Sample Output #4

FIRST