Fişierul intrare/ieşire:order.in, order.outSursăONI 2017, clasele 11-12
AutorPanaete AdrianAdăugată deIsabela_comanComan Isabela Patricia Isabela_coman
Timp execuţie pe test1.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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].

Cerinţă

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 order.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 order.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 ≤ 1015 (mai precis se asigură ca pentru ambele tipuri de interogări poziţia asociată şirului considerat nu depăşeşte 1015)
  • 1 ≤ Q ≤ 105
  • 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

order.inorder.out
2
1 3 1 1 2
2 14
9
2 3 1

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici