4245 - Suma ONI

Sursa: [1]

Cerinţa

Pentru un S dat, găsiţi valoarea minimă N şi asocierea de semne numerelor de la 1 la N pentru a obţine S în condiţiile problemei.

Date de intrare

Fișierul de intrare sumaoni.in conține pe prima linie un întreg pozitiv S reprezentând suma ce trebuie obţinută.

Date de ieșire

Fișierul de ieșire sumaoni.out va conține pe prima linie numărul minim N pentru care se poate obţine suma S, iar pe următoarele linii, până la sfârşitul fişierului, numerele care au semn negativ, câte unul pe linie, iar în consolă se va afișa mesajul "Datele introduse corespund cerințelor." În caz contrar programul va afișa in consolă mesajul "Datele introduse nu corespund cerințelor." Ordinea de afişare a numerelor nu are importanţă. Celelalte numere care nu apar în fişier se consideră pozitive.

Restricţii şi precizări

1 ⩽ N ⩽ 50000
0 ⩽ M ⩽ 10
1 ⩽ numărul inițial de benzi al fiecărei piramide ⩽ 50

Exemplul 1

Intrare: tripar.in; 1; 3 0; 1; 2; 3
Ieșire: Datele de intrare corespund cerintelor..; tripar.out; 1; 4; 9

Exemplul 2

Intrare: tripar.in; 2; 3 0; 1; 2; 3
Ieșire: Datele de intrare corespund cerintelor.; tripar.out; 0; 3; 9

Rezolvare

<syntaxhighlight lang="python" line> def validate_input(s):

   if s < 1 or s > 100000:
       print("Datele introduse nu corespund cerintelor.")
       exit()

def binary_search_sum(s):

   st = 1
   dr = 1000
   n = 0

   while st <= dr:
       mid = st + (dr - st) // 2
       sg = mid * (mid + 1) // 2
       if sg >= s:
           n = mid
           dr = mid - 1
       else:
           st = mid + 1

   diff = n * (n + 1) // 2 - s
   while diff & 1:
       n += 1
       diff = n * (n + 1) // 2 - s

   return n, diff

def print_result(n, diff):

   fout = open("sumaoni.out", "w")
   fout.write(str(n) + '\n')
   if diff == 0:
       fout.close()
       return

   if diff // 2 <= n:
       fout.write(str(diff // 2))
       fout.close()
       return

   diff //= 2
   for i in range(1, diff // 2 + 1):
       if diff - i <= n and diff - i != i:
           fout.write(str(i) + '\n' + str(diff - i))
           fout.close()
           return

   fout.close()

if __name__ == '__main__':

   fin = open("sumaoni.in", "r")
   s = int(fin.readline())
   fin.close()

   validate_input(s)

   n, diff = binary_search_sum(s)

   if n is not None and diff is not None:
       print("Datele introduse corespund cerintelor.")
       print_result(n, diff)

</syntaxhighlight>

Explicatie rezolvare

Acest program este o soluție pentru o problemă care primește intrare prin intermediul fișierelor tripar.in și tripar.out.

În fișierul tripar.in, prima linie conține un singur număr întreg p (1 sau 2), care indică tipul de operație care trebuie efectuată. A doua linie conține două numere întregi separate prin spațiu, n și m, reprezentând numărul de benzi ale fiecărei piramide și numărul de niveluri de perechi drepte-paralele de cuburi care trebuie construite. Ultimele n linii conțin un singur număr întreg pe fiecare linie, reprezentând numărul de benzi al fiecărei piramide.

Programul citește datele de intrare, apoi validează aceste date utilizând funcția validate_input. Dacă datele de intrare sunt valide, se afișează un mesaj corespunzător, iar programul trece la calcularea și scrierea rezultatelor în fișierul tripar.out. Dacă datele de intrare nu sunt valide, se afișează un mesaj de eroare corespunzător și programul se oprește.

Funcțiile nr_triunghiuri și nr_perechi_dr_paralele calculează numărul de triunghiuri sau perechi drepte-paralele de cuburi, în funcție de cerința problemei și de datele de intrare primite. Rezultatele sunt scrise în fișierul tripar.out în ordinea datelor de intrare.

La final, programul verifică dacă codul a fost rulat direct sau a fost importat într-un alt program prin intermediul liniei if __name__ == '__main__':.