Problem Statement |
| |
Sortitaire is a solitaire card game in which you try to arrange a sequence of cards in
non-decreasing order. You start by dealing a sequence of cards face up. This sequence is
called the tableau. The remaining cards are placed in a pile called the stock.
On each turn, you draw the top card from the stock. You can then either discard the card, or
play it face up over one of the cards in the tableau, completely covering the existing card. You
win when the cards showing in the tableau are arranged in non-decreasing order. For simplicity,
the cards will be represented as integers between 1 and 99, inclusive.
For example, suppose you began with the tableau
25 19 41 36 28 40
and the stock contained the cards 27, 36, 24, 39, and 30, in that order. You could win in five turns by
playing the 27 on the 19, playing the 36 on the 28, discarding the 24, discarding the 39,
and playing the 30 on the 41, yielding the tableau
25 27 30 36 36 40
Alternatively, you could win in four turns by playing the 27 on the 19, playing the 36 on
the 41, discarding the 24, and playing the 39 on the 28, yielding the tableau
25 27 36 36 39 40
Given the tableau and the stock, your task is to calculate and return the minimum number of turns needed
to win. If it is impossible to win, return -1.
|
| |
Definition |
| | | Class: | Sortitaire | | Method: | turns | | Parameters: | int[], int[] | | Returns: | int | | Method signature: | int turns(int[] tableau, int[] stock) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Non-decreasing order is the same as increasing order, except that adjacent cards are allowed to be equal. |
| |
Constraints |
| - | tableau contains between 2 and 50 elements, inclusive. |
| - | Each element of tableau is between 1 and 99, inclusive. |
| - | stock contains between 1 and 50 elements, inclusive. |
| - | Each element of stock is between 1 and 99, inclusive. |
| |
Examples |
| 0) | |
| | { 25, 19, 41, 36, 28, 40 } | { 27, 36, 24, 39, 30 } |
| Returns: 4 | |
|
| 1) | |
| | { 1, 1, 1, 1, 1 } | { 2, 3, 4 } |
| Returns: 0 | | The tableau is already in non-decreasing order. |
|
|
| 2) | |
| | { 5, 4, 3, 2, 1 } | { 20, 40 } |
| Returns: -1 | |
|
| 3) | |
| | { 40, 50, 60, 70, 1 } | { 7, 6, 5, 4, 3, 2 } |
| Returns: 5 | |
|
| 4) | |
| | { 19, 7, 23, 38, 23, 90, 81, 22, 71, 30, 87,
32, 99, 5, 80, 17, 19, 43, 67, 50, 88, 11 } | { 24, 89, 70, 35, 55, 43, 92, 10, 33, 18, 8,
40, 14, 22, 56, 4, 98, 57, 89, 31, 30, 14 } |
| Returns: 19 | |
|