== include(page="template/taskheader" task_id="stiva3") ==
Olivius d’Info a primit de ziua lui o stivă şi s-a bucurat foarte tare. S-a tot gândit ce să facă cu ea
şi a inventat un joc de logică pentru colegii lui de clasă.
În prima fază el a scris mai multe bileţele, conţinând fiecare câte o permutare a primelor n
numere naturale nenule: 1, 2, 3, ... , n. Bileţelele scrise conţin permutări pentru diferite valori
ale lui n.
Olivius d’Info a primit de ziua lui o stivă şi s-a bucurat foarte tare. S-a tot gândit ce să facă cu ea şi a inventat un joc de logică pentru colegii lui de clasă.
În prima fază el a scris mai multe bileţele, conţinând fiecare câte o permutare a primelor n numere naturale nenule: 1, 2, 3, ... , n. Bileţelele scrise conţin permutări pentru diferite valori ale lui n.
A clasificat aceste permutări în permutări stivuite şi permutări nestivuite.
O permutare este stivuită dacă se poate obţine pe parcursul introducerii în stivă a numerelor 1,
2, 3, ...,n în această ordine, prin extragerea elementelor, în ordinea indicată în permutare.
O permutare este stivuită dacă se poate obţine pe parcursul introducerii în stivă a numerelor 1, 2, 3, ...,n în această ordine, prin extragerea elementelor, în ordinea indicată în permutare.
O permutare nestivuită este o permutare care NU se poate obţine prin procedeul de mai sus.
Respectând procedeul lui Olivius, pentru n=4, permutarea stivuită (2,1,3,4) se obţine astfel:
!problema/stiva3?x1.jpg!
Succesiunile (3,1,2,4)şi (4,2,1,3) sunt permutări nestivuite.
În faza a doua, unele bileţele au fost scurtate din stânga şi/sau din dreapta. Astfel, din permutarea stivuită (2,1,3,4) se pot obţine succesiuni de lungime mai mică: (1,3,4), (2,1,3), (1,3),(3) etc.
Orice succesiune care aparţine unei permutări stivuite, poate aparţine şi unei permutări nestivuite. De exemplu, succesiunea (2,1,3) aparţine atât permutării stivuite (2,1,3,4), cât şi permutării nestivuite (4,2,1,3).
h2. Cerinta
Dându-se mai multe succesiuni de numere naturale distincte, determinaţi, pentru fiecare dintre acestea, dacă aparţin cel puţin unei permutări stivuite.
h2. Date de intrare
Fişierul de intrare $stiva3.in$ ...
Fişierul stiva3.in conţine un set de cinci succesiuni de elemente, după cum urmează:
• pe prima linie un număr natural k, reprezentând numărul de elemente al fiecăreia dintre cele cinci succesiuni;
• pe fiecare dintre următoarele cinci linii câte k numere naturale nenule, separate prin câte un spaţiu, reprezentând elementele unei succesiuni.
h2. Date de ieşire
În fişierul de ieşire $stiva3.out$ ...
Fişierul stiva3.out va conţine 5 linii, pe fiecare linie câte un număr natural astfel:
1 – dacă succesiunea curentă aparţine unei permutări stivuite;
0 – dacă succesiunea curentă nu aparţine unei permutări stivuite.
Răspunsurile se scriu pe câte o linie, în ordinea apariţiilor succesiunilor în fişierul de intrare.
h2. Restricţii
* $... ≤ ... ≤ ...$
* 1 ≤ valoarea elementelor din succesiune ≤ 2 000 000 000
* Diferenţa dintre cel mai mare şi cel mai mic element al succesiunii nu depăşeşte 50 000
* Elementele dintr-o succesiune sunt distincte două câte două.
h2. Exemplu
table(example). |_. stiva3.in |_. stiva3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
1 3 4
2 1 3
3 1 2
1 2 4
1 4 2
| 1
1
0
1
0
|
h3. Explicaţie
...
n=3, avem cinci succesiuni de numere, fiecare de lungime 3.
- succesiunea (1,3,4) aparţine unei permutări stivuite (răspuns corect 1);
- succesiunea (2,1,3) aparţine unei permutări stivuite (răspuns corect 1);
- succesiunea (3,1,2) nu aparţine niciunei permutări stivuite (răspuns corect 0);
- succesiunea (1,2,4) aparţine unei permutări stivuite (răspuns corect 1);
- succesiunea (1,4,2) nu aparţine niciunei permutări stivuite (răspuns corect 0).
== include(page="template/taskfooter" task_id="stiva3") ==
