D. Lan and Conan’s Game
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/102400K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
As we all know, Shinichi is a very very busy High school student detective, unfortunately, one day he was forced to sink under the black people called "APTX-4869" the mysterious poison. Though body becomes small, mind but not change, is stiil the detective -- edo conan(*^ ^*). Of course Conan is also very very busy… However, today Conan has nothing to do but sit soundly on sofa , watching Lan puzzled about something, what is that? Oh, it’s that Lan wants to play an old Russian solitaire called "Accordion". But the game is not so easy as you think, even our intelligent Conan also feel trouble. So, it’s the best time to show your wisdom. Here comes the rules:
In this solitaire, the player must observe the following rules:
A deck of n cards is carefully shuffled, then all n cards are put on the table in a line from left to right;
Before each move the table has several piles of cards lying in a line (initially there are n piles, each pile has one card). Let's number the piles from left to right, from 1 to x. During one move, a player can take the whole pile with the maximum number x (that is the rightmost of remaining) and put it on the top of pile x-1 (if it exists) or on the top of pile x-3 (if it exists). The player can put one pile on top of another one only if the piles' top cards have the same suits or values. Please note that if pile x goes on top of pile y, then the top card of pile x becomes the top card of the resulting pile. Also note that each move decreases the total number of piles by 1;
The solitaire is considered completed if all cards are in the same pile.
Lan has already shuffled the cards and put them on the table, help them understand whether completing this solitaire is possible or not.
In this solitaire, the player must observe the following rules:
A deck of n cards is carefully shuffled, then all n cards are put on the table in a line from left to right;
Before each move the table has several piles of cards lying in a line (initially there are n piles, each pile has one card). Let's number the piles from left to right, from 1 to x. During one move, a player can take the whole pile with the maximum number x (that is the rightmost of remaining) and put it on the top of pile x-1 (if it exists) or on the top of pile x-3 (if it exists). The player can put one pile on top of another one only if the piles' top cards have the same suits or values. Please note that if pile x goes on top of pile y, then the top card of pile x becomes the top card of the resulting pile. Also note that each move decreases the total number of piles by 1;
The solitaire is considered completed if all cards are in the same pile.
Lan has already shuffled the cards and put them on the table, help them understand whether completing this solitaire is possible or not.
Input
Input contains multiple test cases.The first input line contains a single integer n (1≤n≤52) — the number of cards in Lan's deck. The next line contains n space-separated strings c1,c2,...,cn, where string ci describes the i-th card on the table. Each string ci consists of exactly two characters, the first one represents the card's value, the second one represents its suit. Cards on the table are numbered from left to right.
A card's value is specified by one of these characters: "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A". A card's suit is specified by one of these characters: "S", "D", "H", "C".
It is not guaranteed that the deck has all possible cards. Also, the cards in Lan's deck can repeat.
A card's value is specified by one of these characters: "2", "3", "4", "5", "6", "7", "8", "9", "T", "J", "Q", "K", "A". A card's suit is specified by one of these characters: "S", "D", "H", "C".
It is not guaranteed that the deck has all possible cards. Also, the cards in Lan's deck can repeat.
Output
On the first line, print “Tese # k:”, k is the k-th case. On the second line print the answer to the problem: string "YES" (without the quotes) if completing the solitaire is possible, string "NO" (without the quotes) otherwise.
HINT:In the first sample you can act like that:
put the 4-th pile on the 1-st one;
put the 3-rd pile on the 2-nd one;
put the 2-nd pile on the 1-st one.
HINT:In the first sample you can act like that:
put the 4-th pile on the 1-st one;
put the 3-rd pile on the 2-nd one;
put the 2-nd pile on the 1-st one.
Sample Input
4 2S 2S 2C 2C 2 3S 2C
Sample Output
Tese #1: YES Tese #2: NO
Author
Source
developing schools contest 5