Problem permutare


Definim o permutare dublă de ordin n ca fiind un șir format din primele 2n numere naturale nenule:
\((a_1, a_2, ... , a_n, a_{n+1}, a_{n+2}, ... , a_{2n})\). Această permutare dublă este de trei ori în creștere, dacă sunt adevărate următoarele trei proprietăți:

  1. secvența formată din primele n elemente este crescătoare: \(a_1
  2. secvența formată din ultimele n elemente este crescătoare: \(a_{n+1}
  3. perechile ordonate formate din elementele aflate pe poziții identice ale celor două secvențe sunt de asemenea în ordine crescătoare: \(a_1.

De exemplu permutarea (1,3,4,2,5,6) este o permutare dublă de ordin 3, de trei ori în creștere, pentru că secvențele (1,3,4) și (2,5,6) formează șiruri crescătoare, iar toate perechile formate din elementele de pe poziții identice: (1,2), (3,5), (4,6) formează de asemenea șiruri crescătoare.
Următoarele permutări duble nu au proprietatea de trei ori în creștere:
(1,4,3,2,5,6) – secvența (1,4,3) nu este crescătoare,
(1,3,4,2,6,5) - secvența (2,6,5) nu este crescătoare,
(1,4,5,2,3,6) – perechea (4,3) nu este crescătoare.
Pentru simplificare în continuare permutarea dublă de trei ori în creștere se va numi permutare.
Vom considera toate permutările de ordin n ordonate lexicografic, numerotate începând cu 1. Tabelul de mai jos conține datele pentru n=3:
poziție permutare

poziție 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
Există două tipuri de întrebări:
  1. Ce permutare se află pe o poziție dată?
  2. Pe ce poziție se află o permutare dată?

Prima întrebare este codificată astfel: 1 n p și se compune din valorile
1 – tipul întrebării,
n – ordinul permutării,
p – poziția permutării cerute.
A doua întrebare este codificată astfel: \(2 n a_1 a_2 ... a_{2n}\) și se compune din valorile
2 – tipul întrebării,
n – ordinul permutării,
\(a_1 a_2 ... a_{2n}\) – elementele permutării.

Exemple

Întrebarea 1 3 2 înseamnă:
“Ce permutare de ordin 3 se află pe poziția 2 în ordine lexicografică?” și are răspunsul: 1 2 4 3 5 6.
Întrebarea 2 3 1 3 5 2 4 6 înseamnă:
“Pe ce poziție se află permutarea de ordin 3: 1 3 5 2 4 6?” și are răspunsul: 5.

Cerința

Să se răspundă corect la un set de întrebări.

Date de intrare

Fișierul permutare.in conține pe fiecare linie câte o întrebare de orice tip.

Date de ieșire

Fișierul permutare.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 și precizări

  • 2 < n < 1 000;
  • 0 < p <= 1 000 000 000 (în cazul întrebărilor de tip 1);
  • răspunsul la întrebările de tip 2 este <= 1 000 000 000;
  • fișierele de intrare vor conține cel mult 2000 de întrebări;
  • pentru teste în valoare de 20 de puncte numărul de întrebări va fi 1000 iar numerele de ordine ce intervin în calcule vor fi mai mici decât 5000;
  • pentru teste în valoare de 30 de puncte întrebările vor fi de tipul 1;
  • pentru teste în valoare de 30 de puncte întrebările vor fi de tipul 2;
  • pentru teste în valoare de 30 de puncte întrebările vor fi mixte.
  • problema va fi evaluată pe teste in valoare de 90 de puncte.
  • se vor acorda 10 puncte din oficiu.

General info

ID: 28

Upload: liviu

Input: permutare.in/permutare.out

Memory limit: 64MB/32MB

Time limit: 0.4s

Author: Szabo Zoltan

Source: OJI 2017 XI-XII: Problema 3

Points by default: 10p

Submissions

Special Submissions