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:
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).
Cerinţă
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.
Date de intrare
Fişierul stiva1.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.
Date de ieşire
Fişierul stiva1.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.
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ă.
Exemple
stiva1.in
stiva1.out
Explicaţii
3
1 3 4
2 1 3
3 1 2
1 2 4
1 4 2
1
1
0
1
0
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).
