157. Patience
time limit per test: 0.25
sec.
memory limit per test: 65536
KB
input: standard input
output: standard output
Sasha enjoys playing patiences. Last days he played one very interesting patience on a rectangular grid 14x4. The rules of this patience are very simple. He takes a standard 52card deck (without jokers), extracts all aces and lays them in the first column of the grid. Cell (1, 1) contains ace of diamonds, (1, 2)  ace of hearts, (1, 3)  ace of clubs and (1, 4) contains ace of spades. Then Sasha shuffles the rest of the deck and lays remaining cards to the grid row by row leaving column 2 empty, so all the columns from 3 to 14 are covered by cards.
After having laid all cards in such a manner, he is allowed to make moves. The move is determined by selection of an empty cell. This empty cell is to be covered by the card defined by the contents of the left adjacent cell. The covering card must have the same suit and the next higher value (order of values is: Ace 2 3 4 5 6 7 8 9 10 Jack Queen King). For example, if the cell (6, 3) contains the Queen of Spades, and the cell (7, 3) is empty, selecting cell (7, 3) will move the King of Spades to (7, 3) (and leave empty the cell where the King of Spades was before the move). If the left neighbour of the empty cell contains a King or is empty, the move selecting this empty cell is disabled.
The goal is to make each row ordered (i.e. columns from 1 to 13 must contain cards from Ace to King in the order described above, and the column 14 must be empty). If all empty cells follow Kings or empty cells, and the cards are not ordered, Sasha is declared a loser (in the classic version of this patience, the rest of the deck may be shuffled two times again leaving ordered cards on their positions, however Sasha is very experienced and often wins without additional shuffling).
Now Sasha wants to know some things about this patience. Imagine the position where three suits are already ordered, and the remaining suit is ordered partially. It is known that there are less than n highest cards that are not ordered. So only n rightmost columns may contain unordered cards. For example, if n = 3, columns from 1 to 11 are ordered, and columns from 12 to 14 contain Queen, King and empty cell in an arbitrary order. Sasha wants to determine how many of such positions for a given n have a winning strategy. For example, if n = 3, there is exactly one position that does not allow him to win: ... [King] [empty] [Queen]. All other positions have a winning strategy:
1. ... [Queen] [King] [empty] is already a goal position
2. ... [Queen] [empty] [King] allows to move King adjacent to the Queen.
3. ... [empty] [Queen] [King] becomes previous position after moving the Queen after the Jack.
4. ... [empty] [King] [Queen] becomes goal position by moving the Queen after the Jack.
5. ... [King] [Queen] [empty] becomes position 3 after moving the King to the empty cell.
So for n = 3 the answer is 5.
Write a program that will get the answer for an arbitrary n from 1 to 13.
Input
Input file consists of only one integer number n.
Output
Output the number of positions with less than n highest cards not ordered in the remaining suit that have a winning strategy.
Sample test(s)
Input
Sample input #1
3
Sample input #2
4
Output
Sample output #1
5
Sample output #2
14
Note
You can download pdf version of this task
here
Author:  Andrew Lopatin

Resource:  ACM ICPC 20022003 NEERC, Northern Subregion

Date:  November, 2002

Server time: 20171120 23:47:03  Online Contester Team © 2002  2016. All rights reserved. 

