URI Online Judge | 2915

# Mount Marathon

Por Inés Kereki Uruguay

Timelimit: 1

Mount Marathon is a solitaire game that is played using a regular deck of 52 cards. To start the game the player shuffles the deck and lays N cards face up on the table, forming a straight line of N piles, each pile having a single card. No other cards are used during the rest of the play. Then the player repeatedly moves a pile on top of another pile until no more movements are available. The goal of the game is to end up with the minimum number of piles. When moving a pile p on top of another pile q, the following conditions must hold:

• Pile p must be a single-card pile.

• The value of the only card in pile p must be greater than or equal the value of the card that is on top of pile q.

• Pile q must be the next pile remaining immediately on the right of pile p.

Figure (a) below shows a configuration with six cards at the beginning of the game. The player may move the fifth pile on top of the sixth pile, and then the second pile on top of the third pile; since no more movements are available, this would conclude the game with four piles remaining, as it can be seen in figure (b). However, in this case it is possible to end up the game with just the three piles that appear in figure (c).

Given the initial piles, you must determine the minimum number of piles that it is possible to obtain at the end of the game.