CAMELOT - Camelot

no tags 

Camelot is a solitaire game that is played with a deck of French cards. The deck contains
52 cards, each of them having a suit and a face value. There are 4 possible suits and 13
possible face values. Since for this solitaire suits are not important, we consider that the
deck contains 4 repetitions of each possible face value. Face values are A, 2, 3, 4, 5, 6, 7,
8, 9, 10, J, Q and K.

The solitaire starts with the full deck placed, face down, on the table. There is also a
board containing 16 empty slots arranged in a 4 by 4 grid. The game repeatedly alternates
two phases: a dealing phase and a removal phase.
The first phase is a dealing phase. During this phase cards are dealt from the deck one
at a time. Each card is placed, face up, in an empty slot. However, certain cards can
only be placed in specific slots: Jacks (face value J) can only occupy the middle two slots
of first and last columns. Queens (face value Q) can only occupy the middle two slots of
first and last rows. Finally, Kings (face value K) can only occupy the corner slots. Cards
having other face values can be placed in any empty slot. The game is lost whenever a
card is dealt from the deck for which no valid empty slot exists. Each time the last empty
slot has just been occupied, or when the deck is empty, a removal phase starts.

During a removal phase, it is possible to remove from the board any card or pair of cards
that add up to 10. For this purpose, Aces (face value A) are considered as having value 1,
while Jacks, Queens and Kings cannot be removed. For instance, it is possible to remove
a 10 on its own, a pair formed by a 3 and a 7, a pair formed by an Ace and a 9, etcetera.
Cards removed from the board are not used anymore during the game. The removal
phase ends when no card can be removed from the board, or when the player decides not
to continue removing cards. Notice that it is not mandatory to remove from the board
every card that can be removed. However, since the player cannot decide the moment
in which a new removal phase will begin, leaving removable cards on the board must be
done carefully. Besides, note that if during a removal phase no card is removed, then the
game is lost. When the removal phase ends, a new dealing phase starts, unless the deck
is empty, in which case the game is over.

The game is won if the deck is empty and only Jacks, Queens and Kings are left on the
board.

Camelot is really nice to play, but is frustrating to discover at the end of a game that it
was impossible to win because of the initial arrangement of the deck. Even if the initial
deck allows the player to win, he may fail to do so because of bad decisions or bad luck
when placing or removing cards. Your job in this problem is to find out whether it is at
least possible to win the game, given the order in which the cards will be dealt from the
deck.

Input

Each test case is described using a single line. The line contains a single string of exactly
52 characters representing the initial arrangement of the deck. The first card dealt from
the deck is given by the first character of the string, and so on. Each card is represented
by its face value, with the exception of cards with face value 10 that are represented by
the digit “0”. You may assume that the string corresponds to a valid initial arrangement
of the deck, i.e., it contains exactly 4 repetitions of each possible face value. The end of
input is indicated with a line containing a single asterisk (“*”).

Output

For each test case, output a single line containing an uppercase “Y” if it is possible to win
the game with the given initial arrangement of the deck, or an uppercase “N” otherwise.

Example

Input: 
AAAA222233334444555566667777888899990000JJJJQQQQKKKK
JJJJQQQQKKKKA9A9A9A928282828373737374646464655550000
JJJJQQQQKKKKA9A9A9A928282828333377774646464655550000
28333377774646464655550000JJJJQQQQKKKKA9A9A9A9282828
* Output:
N
Y
N
Y

hide comments
nadstratosfer: 2017-11-02 01:36:40

I love this type of problems, they appear tedious but never give me a hard time. My AC solution was produced in 50mins without a single test, and turned out to have just 1 small bug when finished. Coding such stuff in Python comes as natural as writing an email.

Pablo Ariel Heiber: 2010-09-27 23:22:17

This solitaire is part of the Aisle Riot solitaire collection, in the Genome games package.


Added by:Pablo Ariel Heiber
Date:2010-09-26
Time limit:0.319s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010