4026 - Order

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ţa

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 şi precizări

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

Exemplul 1

order.in

 2
 1 3 1 1 2
 2 14

order.out

 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.

Rezolvare

<syntaxhighlight lang="python" line> def fibonacci(n):

   fib = [1, 1]
   while len(fib) < n:
       fib.append(fib[-1] + fib[-2])
   return fib

def find_position(sequence):

   n = len(sequence)
   fib = fibonacci(n + 2)
   prefix_sum = [0] * (n + 1)
   for i in range(1, n + 1):
       prefix_sum[i] = prefix_sum[i - 1] + fib[i]
   position = prefix_sum[n]
   for i in range(n):
       position += sequence[i] - 1
       for j in range(1, sequence[i]):
           position += fib[n - i - 1]
   return position

def find_sequence(position):

   fib = fibonacci(100)
   n = len(fib)
   sequence = []
   for i in range(n - 1, -1, -1):
       if position > fib[i]:
           sequence.append(i + 1)
           position -= fib[i]
   return sequence

def main():

   with open("order3.in", "r") as fin:
       Q = int(fin.readline())
       queries = [list(map(int, line.split())) for line in fin.readlines()]

   with open("order3.out", "w") as fout:
       for query in queries:
           if query[0] == 1:
               sequence = query[2:]
               position = find_position(sequence)
               fout.write(str(position) + "\n")
           elif query[0] == 2:
               position = query[1]
               sequence = find_sequence(position)
               fout.write(f"{len(sequence)} {' '.join(map(str, sequence))}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>