Fișierul intrare/ieșire	order.in, order.out	Sursă	ONI 2017, clasele 11-12
Autor	Adrian Panaete	Adăugată de	Coman Isabela Patricia • Isabela_coman
Timp de execuție pe test	0.3 sec	Limită de memorie	65536 KB
Scorul tău	N/A	Dificultate	3.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Order (clasa 11/12)

Enunt

Se consideră toate șirurile finite de numere naturale nenule ordonate astfel:
[ 1 ]; [1,1]; [2]; [1,1,1]; [1,2]; [2,1]; [3]; [1,1,1,1]; [1,1,2]; [1,2,1]; [1,3]; ...
Ordonarea se face după următoarea regulă: dacă avem două șiruri cu sumele termenilor diferite, atunci șirul cu suma termenilor mai mică se găsește pe o poziție mai mică.
Dacă avem două șiruri cu sumele termenilor egale atunci se compară termen cu termen șirurile până când se găsește un termen diferit.
Șirul care are termenul mai mic se găsește pe poziție mai mică. Cu alte cuvinte, primul criteriu de ordonare este suma termenilor, iar în caz de egalitate, al doilea criteriu de sortare este ordinea lexicografică.
Oricărui șir i se asociază o poziție (număr natural nenul) și invers, oricărei poziții i se asociază un șir.

De exemplu:

• Șirului [1,1,2] i se asociază poziția 9.
• Poziției 14 i se asociază șirul [3,1].

Cerinta

Să se răspundă la un număr de interogări de tipul:
1. Cunoscând un șir de numere naturale nenule să se determine poziția asociată șirului.
2. Cunoscând un număr natural reprezentând o poziție asociată unui șir să se determine șirul corespunzător.

Date de intrare

Fișierul de intrare order3.in conține pe prima linie un număr natural Q reprezentând numărul de interogări.
Pe următoarele Q linii vor fi descrise interogările.
Dacă interogarea este de tip 1 linia va conține numărul 1, apoi un număr natural N reprezentând numărul de termeni ai șirului urmat de N numere naturale separate prin cűte un spațiu reprezentând termenii șirului.
Dacă interogarea este de tip 2 linia va conține numărul 2 urmat de un număr natural nenul P reprezentând poziția șirului solicitat.

Date de ieșire

Fișierul de ieșire order3.out va conține Q linii. Pe fiecare linie este descris răspunsul la interogarea corespunzătoare din fișierul de intrare.
Dacă interogarea este de tip 1, pe linia corespunzătoare se va afișa un singur număr P reprezentând poziția șirului descris în interogare.
Dacă interogarea este de tip 2, linia corespunzătoare va conține un număr natural N reprezentând numărul de termeni pentru șirul solicitat, urmat de N numere naturale nenule reprezentând termenii șirului. Numerele de pe aceste linii trebuie sa fie separate prin câte un spațiu.

Restricții

• 1 ≤ P ≤ _10¹⁵ (mai precis se asigură ca pentru ambele tipuri de interogări poziția asociată șirului considerat nu depășește _10¹⁵)
• 1 ≤ Q ≤ _10⁵
• Pentru 40 de puncte testele vor conține doar interogări de tip 1
• Pentru 40 de puncte testele vor conține doar interogări de tip 2
• Pentru 20 de puncte testele vor conține interogări de ambele tipuri

Exemplu

Explicație

Fișierul de intrare conține două interogări. Prima este de tip 1 și cere determinarea poziției șirului [1,1,2] care are lungimea 3. Acest șir este pe poziția a 9-a conform ordinii descrise în enunț. A doua interogare cere determinarea șirului aflat pe poziția 14. Acest șir este șirul [3,1] de lungime 2.