3745 - Oposumi

Cerința

O familie de oposumi are o vizuină cu N niveluri și N * (N + 1) / 2 camere dispuse în formă de matrice triunghiulară cu N linii. În fiecare cameră poate locui un singur oposum. Vizuina a fost săpată în pământ de către oposumi, iar nivelul 1 (cel mai de sus) este cel mai apropiat de suprafața solului. Pe fiecare nivel I se află I camere. Dacă avem I < J, atunci nivelul I va fi poziționat mai sus decât nivelul J, adică nivelul I va fi mai aproape de suprafața solului decât nivelul J. În familia de oposumi se află exact N * (N + 1) / 2 membri cu vârste cuprinse între 1 și N * (N + 1) / 2, vârste distincte. Regula de bază în vizuina familiei de oposumi este următoarea: în camera de pe linia I și coloana J trebuie să locuiască un oposum mai tânăr decât în camerele de pe pozițiile (I + 1, J) respectiv (I + 1, J + 1). Un oposum de vârsta X se consideră mai tânăr decât un oposum de vârsta Y dacă X < Y. Fiecare oposum vrea să știe care e cel mai de sus nivel pe care se poate poziționa. Din păcate, ei nu au lăbuțele făcute să programeze, așa că membrii familiei de oposumi vă cer vouă ajutorul. Dându-se numărul natural N ei vă cer să răspundeți la două întrebări: 1. Pentru fiecare oposum să se afle nivelul cel mai de sus (cel mai aproapiat de suprafața solului) pe care se poate afla respectând regulile de vârstă. 2. Pentru un oposum dat de vârsta K să se afișeze matricea astfel încât oposumul să stea într-o cameră pe un nivel cât mai de sus respectând regulile de vârstă.

Date de intrare

Pe prima linie a fișierului de intrare oposumi.in se găsește numărul T ce poate avea valoarea 1 sau 2 astfel încât:

• Dacă T are valoarea 1, atunci se cere rezolvarea cerinței 1, iar în continuare se va regăsi numărul natural N reprezentând numărul de niveluri ale vizuinii.
• Daca T are valoarea 2, atunci se cere rezolvarea cerinței 2, iar în continuare se va regăsi numărul natural N reprezentând numărul de niveluri ale vizuinii, urmat de numărul natural K ce reprezintă vârsta oposumului ce se dorește poziționat pe un nivel cât mai de sus.

Date de ieșire

În fișierul de ieșire oposumi.out se cere să se tipărească:

• Pentru T = 1 se va afișa un șir de N * (N +1) / 2 numere, unde cel de al I-lea număr reprezintă cel mai de sus nivel pe care se poate afla oposumul de vârstă I.
• Pentru T = 2 se vor afișa N linii, reprezentând modul în care sunt așezați oposumii în vizuină în funcție de vârstă, astfel ca oposumul de vârsta K să fie poziționat pe un nivel cât mai de sus posibil. Pe linia I se vor afișa I numere separate prin câte un spațiu reprezentând vârstele oposumilor așezați pe nivelul I.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ K ≤ N * (N + 1) / 2
• Pentru cerința T = 2 soluția nu este unică. Se acceptă orice soluție corectă

Exemplu 1

Intrare

1 3

Iesire

1 2 2 3 3 3

Rezolvare

<syntaxhighlight lang="python" line> def read_input(file_name):

   with open(file_name, 'r') as file:
       T, N = map(int, file.readline().strip().split())
       if T == 2:
           K = int(file.readline().strip())
       else:
           K = None
   return T, N, K

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       for line in result:
           if isinstance(line, list):
               file.write(' '.join(map(str, line)) + '\n')
           else:
               file.write(str(line) + '\n')

def nivel_cel_mai_de_sus(N):

   poziții = []
   valoare = 1
   for i in range(N):
       nivel = []
       for j in range(i + 1):
           nivel.append(valoare)
           valoare += 1
       poziții.append(nivel)
   return poziții

def poziția_oposumului(N, poziții, K):

   poziții_rezultat = [['-' for _ in range(N)] for _ in range(N)]
   găsit = False
   for i in range(N):
       for j in range(i + 1):
           if poziții[i][j] == K:
               poziții_rezultat[i][j] = K
               găsit = True
               break
       if găsit:
           break
   return poziții_rezultat

def main():

   input_file = 'oposumi.in'
   output_file = 'oposumi.out'

   T, N, K = read_input(input_file)

   if not (1 <= N <= 1000):
       raise ValueError("N trebuie să fie între 1 și 1000")

   poziții = nivel_cel_mai_de_sus(N)

   if T == 1:
       result = []
       for i in range(1, N * (N + 1) // 2 + 1):
           găsit = False
           for nivel in range(N):
               if găsit:
                   break
               for j in range(len(poziții[nivel])):
                   if poziții[nivel][j] == i:
                       result.append(nivel + 1)
                       găsit = True
                       break
       result = [result]  # Wrap result in a list of lists
   elif T == 2:
       result = poziția_oposumului(N, poziții, K)

   write_output(output_file, result)

if __name__ == '__main__':

   main()

</syntaxhighlight>