1208 - Solitar

Se consideră un joc de cărţi cu un număr nelimitat de coloane. Iniţial, pe prima coloană există, într‑o ordine oarecare, N cărţi cu numere distincte din mulţimea {1,2,…,N}, următoarele coloane fiind vide (fără cărţi). Numim secvenţă de la sfârşitul coloanei ultima sau ultimele două sau ultimele trei etc. cărţi din coloană care au scrise pe ele numere consecutive în ordine crescătoare, considerate de jos în sus. De exemplu, în figurile 1 şi 2 sunt reprezentate două astfel de coloane cu câte 6 cărţi având numere între 1 şi 6. În figura 1, secvenţa de la sfârşitul coloanei este formată doar din cartea 1. În figura 2, secvenţa de la sfârşitul coloanei este formată din cărţile 3, 4 şi 5. Se observă că în coloana din figura 1 mai există o secvenţă formată din cărţile 2, 3 şi 4, dar aceasta nu este la sfârşitul coloanei.

Operaţiile permise ale jocului sunt:

A. mutarea secvenţei de cărţi de la sfârşitul unei coloane pe o coloană nouă, dacă acea coloană este vidă (nu conţine nicio carte);

B. mutarea secvenţei de cărţi de la sfârşitul unei coloane la sfârşitul altei coloane cu cărţi, doar dacă secvenţa mutată formează o secvenţă de numere consecutive cu cele de pe cartea sau cărţile aflate la sfârşitul coloanei respective.

Se doreşte ca, printr-un număr minim de operaţii permise, să se obţină pe una dintre coloane toate numerele de la 1 la N, în ordine crescătoare, considerate de jos în sus.

De exemplu, de la configuraţia iniţială din figura 2 se va obţine, printr-o operaţie A, configuraţia 1 de mai jos. Apoi, printr-o operaţie B, se obţine configuraţia 2, printr-o nouă operaţie B se obţine configuraţia 3, apoi se mută secvenţa 2,3,4,5,6 pe o coloană vidă (operaţia A), apoi se mută secvenţa 1 peste secvenţa 2,3,4,5,6 (operaţia B) şi se obţine, pe coloana a doua, configuraţia finală cerută.

Configurația 1	Configurația 2	Configurația 3	Configurația 4	Configurația 5

Cerința

Cunoscând valoarea lui N, precum şi valorile cărţilor de pe prima coloană, să se determine numărul minim de operaţii prin care se poate obţine secvenţa 1, 2, …, N pe una dintre coloane.

Date de intrare

Fişierul solitar.in conţine pe prima linie numărul natural N şi pe linia următoare N numere naturale distincte din mulţimea {1,2,…,N}, separate prin câte un spaţiu, date în ordinea de pe coloană, de sus în jos.

Date de ieșire

Fişierul solitar.out va conţine o singură linie pe care va fi scris un număr natural M reprezentând numărul minim de operaţii prin care se poate obţine secvenţa cerută.

Restricții și precizări

• 2 ≤ n ≤ 100 000

Exemplu:

solitar.in

6
1 6 2 5 4 3

solitar.out

5

Explicație

Cele 5 mutări sunt descrise în enunţul problemei.

<syntaxhighlight lang="python" line="1"> from collections import deque

def min_operations_to_sort_cards(N, cards):

   # Initialize columns with the initial column
   columns = [deque(cards)]
   
   def find_sequences(column):
       sequences = []
       start = len(column) - 1
       while start >= 0:
           end = start
           while start > 0 and column[start] - 1 == column[start - 1]:
               start -= 1
           sequences.append((start, end))
           start -= 1
       return sequences
   
   def move_sequence(src, dst):
       if not columns[dst] or columns[dst][-1] + 1 == columns[src][sequences[0][0]]:
           for _ in range(sequences[0][1] - sequences[0][0] + 1):
               columns[dst].append(columns[src].popleft())
       else:
           for _ in range(sequences[0][1] - sequences[0][0] + 1):
               columns.append(deque())
               columns[-1].append(columns[src].popleft())
   
   operations = 0
   while len(columns) > 1 or len(columns[0]) != N:
       for idx, col in enumerate(columns):
           sequences = find_sequences(col)
           if sequences[0][0] == 0:
               if idx == 0 and len(sequences) == 1 and sequences[0][1] == N - 1:
                   return operations
               continue
           move_sequence(idx, (idx + 1) % len(columns))
           operations += 1
   
   return operations

1. Exemplu de utilizare

N = 6 cards = [5, 4, 3, 2, 1, 6] print("Numărul minim de operații:", min_operations_to_sort_cards(N, cards)) </syntaxhighlight>