Fişierul intrare/ieşire:permutare4.in, permutare4.outSursăOJI 2017, Clasele 11-12
AutorZoltan SzaboAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.75 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permutare4

Definim o permutare dublă de ordin N ca fiind un şir format din primele 2 * N numere naturale nenule:

 P_{1} ,  P_{2} ...  P_{N} ,  P_{N + 1} ,  P_{N + 2} ...  P_{2 * N}

Această permutare dublă este de trei ori în creştere, dacă sunt adevărate următoarele trei proprietăţi:

  1. Secventa formata din primele  N elemente este crescatoare:
     P_{1} < P_{2} < ... < P_{N}
  2. Secvenţa formată din ultimele  N elemente este crescătoare:
     P_{N + 1} < P_{N + 2} < ... < P_{2 * N}
  3. Perechile ordonate formate din elementele aflate pe pozitii identice ale celor doua secvente sunt, de asemenea, in ordine crescatoare:
     P_{1} < P_{N + 1} ,  P_{2} < P_{N + 2} , ...  P_{N} < P_{2 * N}

De exemplu, permutarea  (1, 3, 4, 2, 5, 6) este o permutare dubla de ordin  3 , de trei ori in crestere, intrucat secventele  (1, 3, 4) si  (2, 5, 6) formeaza siruri crescatoare, iar toate perechile formate din elementele de pe pozitii identice:  (1, 2) ,  (3, 5) ,  (4, 6) formeaza, de asemenea, siruri crescatoare.
Urmatoarele permutari duble nu sunt de trei ori crescatoare:

  •  (1, 4, 3, 2, 5, 6) : Secventa  (1, 4, 3) nu este crescatoare.
  •  (1, 3, 4, 2, 6, 5) : Secventa  (2, 6, 5) nu este crescatoare.
  •  (1, 4, 5, 2, 3, 6) : Perechea  (4, 3) nu este crescatoare.

Pentru simplitate, permutarea dubla de trei ori in crestere se va numi permutare.
Vom considera toate permutarile de ordin  N , ordonate lexicografic si numerotate incepand cu  1 . Tabelul de mai jos contine datele pentru  N = 3 :

PozitiePermutare
11 2 3 4 5 6
21 2 4 3 5 6
31 2 5 3 4 6
41 3 4 2 5 6
51 3 5 2 4 6

Exista doua tipuri de intrebari:

  1. Ce permutare se afla pe o pozitie data?
    • Codificata  1 \  N \  P
      •  1 : Tipul intrebarii.
      •  N : Ordinul permutarii.
      •  P : Pozitia permutarii cerute.
  2. Pe ce pozitie se afla o permutare data?
    • Codificata  2 \ N \ P_{1} \ P_{2} \ ... \ P_{2 * N}
      •  2 : Tipul intrebarii.
      •  N : Ordinul permutarii.
      •  P_{1} \ P_{2} \ ... \ P_{2 * N} : Elementele permutarii.

Ca exemple:

  • Intrebarea  (1 \ 3 \  2) inseamna: Ce permutare de ordin  3 se afla pe pozitia  2 in ordine lexicografica? Raspunsul este  (1 \  2 \  4 \  3 \  5 \  6) .
  • Intrebarea  (2 \ 3 \  1 \  3 \  5 \  2 \  4 \  6) inseamna: Pe ce poziţie se află permutarea de ordin  3: \ (1 \ 3  \ 5 \  2 \  4 \  6) ? Raspunsul este  5 .

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:

  •  2 < N < 1000 .
  • Indicele pentru intrebarile de tip 1 respecta:  \ 0 < P \leq 1.000.000.000 .
  • Raspunsul pentru intrebarile de tip 2 respeca:  \ 0 < P \leq 1.000.000.000 .
  • Fisierele de intrare vor contine cel mult  2.000 de intrebari.
  • Pentru teste in valoare de  20 de puncte, numarul de intrebari va fi  1.000 , iar numerele de ordine ce intervin in calcule vor fi mai mici decat  5.000 .
  • Pentru teste în valoare de  30 de puncte, întrebările vor fi doar de tipul  1 .
  • Pentru teste în valoare de  30 de puncte, întrebările vor fi dora de tipul  2 .
  • Pentru teste în valoare de  30 de puncte, întrebările vor fi mixte.
  • Conform regulamentului OJI, se vor acorda  10 puncte din oficiu.

Exemplu

permutare4.inpermutare4.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  3: \ (1, 2, 4, 3, 5, 6) .
  • Permutarea  (1, 3, 5, 2, 4, 6) are pozitia  5 .
  • Prima permutare de ordin  4: \ (1, 2, 3, 4, 5, 6, 7, 8) .
  • Permutarea  (1, 2, 3, 4, 5, 6, 7, 8) are pozitia  1 .
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?