#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.
ONI GIM 2014, Clasa a VIII-a
Problema | Solitar | Operații I/O |
![]() solitar.in /solitar.out
|
---|---|---|---|
Limita timp | 0.2 secunde | Limita memorie |
Total: 2 MB
/
Stivă 1 MB
|
Id soluție | #50635076 | Utilizator | |
Fișier | solitar.cpp | Dimensiune | 693 B |
Data încărcării | 17 Aprilie 2024, 22:12 | Scor / rezultat | 3 puncte |
solitar.cpp: In function 'int main()': solitar.cpp:12:36: warning: unused variable 'sus' [-Wunused-variable] long long int n, cnt=1, mut=0, sus=0, jos=0, ok=0, a, bck; ^ solitar.cpp:12:43: warning: unused variable 'jos' [-Wunused-variable] long long int n, cnt=1, mut=0, sus=0, jos=0, ok=0, a, bck; ^ solitar.cpp:12:56: warning: unused variable 'a' [-Wunused-variable] long long int n, cnt=1, mut=0, sus=0, jos=0, ok=0, a, bck; ^ solitar.cpp:18:21: warning: 'bck' may be used uninitialized in this function [-Wmaybe-uninitialized] if(v[i]!=bck-1) ^
Test | Timp | Mesaj evaluare | Scor posibil | Scor obținut | ||
---|---|---|---|---|---|---|
0 | 0 secunde | OK. | 3 | 3 | ||
1 | 0 secunde | Raspuns gresit. | 3 | 0 | ||
2 | 0 secunde | Raspuns gresit. | 3 | 0 | ||
3 | 0 secunde | Raspuns gresit. | 4 | 0 | ||
4 | 0 secunde | Raspuns gresit. | 4 | 0 | ||
5 | 0 secunde | Raspuns gresit. | 4 | 0 | ||
6 | 0 secunde | Raspuns gresit. | 7 | 0 | ||
7 | 0.004 secunde | Raspuns gresit. | 5 | 0 | ||
8 | 0.004 secunde | Raspuns gresit. | 5 | 0 | ||
9 | 0.016 secunde | Raspuns gresit. | 5 | 0 | ||
10 | Depășit | Limita de timp depășită | 5 | 0 | ||
11 | 0.096 secunde | Raspuns gresit. | 5 | 0 | ||
12 | 0.068 secunde | Raspuns gresit. | 5 | 0 | ||
13 | 0.036 secunde | Raspuns gresit. | 5 | 0 | ||
14 | Depășit | Limita de timp depășită | 6 | 0 | ||
15 | 0.016 secunde | Raspuns gresit. | 6 | 0 | ||
16 | Depășit | Limita de timp depășită | 6 | 0 | ||
17 | Depășit | Limita de timp depășită | 6 | 0 | ||
18 | Depășit | Limita de timp depășită | 6 | 0 | ||
19 | Depășit | Limita de timp depășită | 7 | 0 | ||
Punctaj total | 3 |
www.pbinfo.ro permite evaluarea a două tipuri de probleme:
Problema Solitar face parte din prima categorie. Soluția propusă de tine va fi evaluată astfel:
Suma punctajelor acordate pe testele utilizate pentru verificare este 100. Astfel, soluția ta poate obține cel mult 100 de puncte, caz în care se poate considera corectă.