Editing 4245 - Suma ONI

Sursa: [https://www.pbinfo.ro/probleme/4245/sumaoni]
== Cerinţa ==
Cunoscând N, M și câte benzi are fiecare piramidă, se cere să se afișeze:

a) câte triunghiuri de cea mai mică dimensiune are fiecare piramidă, după executarea procedeului de împărțire de M ori;

b) câte perechi de drepte paralele are fiecare piramidă, după executarea procedeului de împărțire de M ori.

== Date de intrare ==
Fişierul de intrare '''tripar.in''' conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Următoarea linie va conține numerele N și M separate printr-un un spațiu. Pe următoarea linie se vor afla N numere naturale, al i-lea număr reprezintă numărul de benzi pe care, inițial, piramida i le are.

== Date de ieșire == 
Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință. În acest caz, fişierul de ieşire '''tripar.out''' va conține N linii; pe linia i se va scrie un număr natural reprezentând, numărul de triunghiuri de cea mai mică dimensiune pe care piramida i le conține după executarea procedeului de M ori, iar în consolă se va afișa mesajul "Datele de intrare corespund cerintelor." 

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință. În acest caz, fişierul de ieşire '''tripar.out''' va conține N linii; pe linia i se va scrie un număr natural reprezentând, numărul de perechi de drepte paralele pe care piramida i le conține după executarea procedeului de M ori, ar în consolă se va afișa mesajul "Datele de intrare corespund cerintelor."

În cazul in care cerintele de mai sus nu sunt indeplinite programul va afișa în consolă mesajul "Datele introduse nu corespund cerințelor."

== Restricţii şi precizări ==
* 1 &les; '''N''' &les; 50000
* 0 &les; '''M''' &les; 10
* 1 &les; '''numărul inițial de benzi al fiecărei piramide''' &les; 50

== Exemplul 1 ==
; Intrare
: ''tripar.in''
: 1
: 3 0
: 1
: 2
: 3
; Ieșire
: Datele de intrare corespund cerintelor..
: ''tripar.out''
: 1
: 4
: 9
<br>

== Exemplul 2 ==
; Intrare
: ''tripar.in''
: 2
: 3 0
: 1
: 2
: 3
; Ieșire
: Datele de intrare corespund cerintelor.
: ''tripar.out''
: 0
: 3
: 9
<br>

== 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__':'''.