Fişierul intrare/ieşire: | permutare4.in, permutare4.out | Sursă | OJI 2017, Clasele 11-12 |
Autor | Zoltan Szabo | Adăugată de | Vlad Dumitru-Popescu •depevlad |
Timp execuţie pe test | 0.75 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Permutare4
Definim o permutare dublă de ordin ca fiind un şir format din primele numere naturale nenule:
, ... , , ...
Această permutare dublă este de trei ori în creştere, dacă sunt adevărate următoarele trei proprietăţi:
- Secventa formata din primele elemente este crescatoare:
- Secvenţa formată din ultimele elemente este crescătoare:
- Perechile ordonate formate din elementele aflate pe pozitii identice ale celor doua secvente sunt, de asemenea, in ordine crescatoare:
, , ...
De exemplu, permutarea este o permutare dubla de ordin , de trei ori in crestere, intrucat secventele si formeaza siruri crescatoare, iar toate perechile formate din elementele de pe pozitii identice: , , formeaza, de asemenea, siruri crescatoare.
Urmatoarele permutari duble nu sunt de trei ori crescatoare:
- : Secventa nu este crescatoare.
- : Secventa nu este crescatoare.
- : Perechea nu este crescatoare.
Pentru simplitate, permutarea dubla de trei ori in crestere se va numi permutare.
Vom considera toate permutarile de ordin , ordonate lexicografic si numerotate incepand cu . Tabelul de mai jos contine datele pentru :
Pozitie | Permutare |
---|---|
1 | 1 2 3 4 5 6 |
2 | 1 2 4 3 5 6 |
3 | 1 2 5 3 4 6 |
4 | 1 3 4 2 5 6 |
5 | 1 3 5 2 4 6 |
Exista doua tipuri de intrebari:
- Ce permutare se afla pe o pozitie data?
- Codificata
- : Tipul intrebarii.
- : Ordinul permutarii.
- : Pozitia permutarii cerute.
- Codificata
- Pe ce pozitie se afla o permutare data?
- Codificata
- : Tipul intrebarii.
- : Ordinul permutarii.
- : Elementele permutarii.
- Codificata
Ca exemple:
- Intrebarea inseamna: Ce permutare de ordin se afla pe pozitia in ordine lexicografica? Raspunsul este .
- Intrebarea inseamna: Pe ce poziţie se află permutarea de ordin ? Raspunsul este .
Să se răspundă corect la un set de întrebări.
Input:
Fişierul de intrare permutare4.in contine pe fiecare linie o intrebare de orice tip.
Output:
Fisierul de iesire permutare4.out va conţine pe câte o linie câte un răspuns la fiecare întrebare din fişierul de intrare, în ordinea întrebărilor.
Restricţii si Precizari:
- .
- Indicele pentru intrebarile de tip 1 respecta: .
- Raspunsul pentru intrebarile de tip 2 respeca: .
- Fisierele de intrare vor contine cel mult de intrebari.
- Pentru teste in valoare de de puncte, numarul de intrebari va fi , iar numerele de ordine ce intervin in calcule vor fi mai mici decat .
- Pentru teste în valoare de de puncte, întrebările vor fi doar de tipul .
- Pentru teste în valoare de de puncte, întrebările vor fi dora de tipul .
- Pentru teste în valoare de de puncte, întrebările vor fi mixte.
- Conform regulamentului OJI, se vor acorda puncte din oficiu.
Exemplu
permutare4.in | permutare4.out |
---|---|
1 3 2 2 3 1 3 5 2 4 6 1 4 1 2 4 1 2 3 4 5 6 7 8 | 1 2 4 3 5 6 5 1 2 3 4 5 6 7 8 1 |
Explicaţie:
- A doua permutare de ordin .
- Permutarea are pozitia .
- Prima permutare de ordin .
- Permutarea are pozitia .