== 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.
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 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.
Poveste şi cerinţă...
h2. Date de intrare
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.
Fişierul de intrare $stiva3.in$ ...
h2. Date de ieşire
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.
În fişierul de ieşire $stiva3.out$ ...
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 |
| 3
1 3 4
2 1 3
3 1 2
1 2 4
1 4 2
| 1
1
0
1
0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
