!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 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") ==
