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 ⩽ S ⩽ 100.000
• Dacă există mai multe soluţii se cere doar una.

Exemplul 1

Intrare

sumaoni.in

12

Ieșire

Datele introduse corespund cerintelor.

sumaoni.out

7

1

7

Exemplul 2

Intrare

sumaoni.in

15

Ieșire

Datele introduse corespund cerintelor.

sumaoni.out

5

Rezolvare

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


def cauta_suma_minimala(s):
    start_interval = 1
    final_interval = 1000
    suma_minima_gasita = 0

    while start_interval <= final_interval:
        mijloc_interval = start_interval + (final_interval - start_interval) // 2
        suma = mijloc_interval * (mijloc_interval + 1) // 2
        if suma >= s:
            suma_minima_gasita = mijloc_interval
            final_interval = mijloc_interval - 1
        else:
            start_interval = mijloc_interval + 1

    diferenta = suma_minima_gasita * (suma_minima_gasita + 1) // 2 - s
    while diferenta & 1:
        suma_minima_gasita += 1
        diferenta = suma_minima_gasita * (suma_minima_gasita + 1) // 2 - s

    return suma_minima_gasita, diferenta


def afiseaza_rezultat(suma_minima_gasita, diferenta):
    fisier_iesire = open("sumaoni.out", "w")
    fisier_iesire.write(str(suma_minima_gasita) + '\n')
    if diferenta == 0:
        fisier_iesire.close()
        return

    if diferenta // 2 <= suma_minima_gasita:
        fisier_iesire.write(str(diferenta // 2))
        fisier_iesire.close()
        return

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

    fisier_iesire.close()


if __name__ == '__main__':
    fisier_intrare = open("sumaoni.in", "r")
    s = int(fisier_intrare.readline())
    fisier_intrare.close()

    verifica_date_intrare(s)

    suma_minima_gasita, diferenta = cauta_suma_minimala(s)

    if suma_minima_gasita is not None and diferenta is not None:
        print("Datele introduse corespund cerintelor.")
        afiseaza_rezultat(suma_minima_gasita, diferenta)

Explicatie rezolvare

Acest program are rolul de a găsi numărul minim de perechi de numere consecutive în șirul de numere naturale, astfel încât suma lor să fie egală cu numărul dat s din fișierul sumaoni.in.

Programul primește numărul s din fișierul sumaoni.in, validează dacă acesta respectă cerințele problemei (1 ≤ S ≤ 100.000) prin intermediul funcției validate_input(s), apoi utilizează o funcție de căutare binară pentru a găsi cel mai mic număr natural n pentru care suma primelor n numere naturale este mai mare sau egală cu s.

Dacă diferența dintre suma primelor n numere naturale și s este un număr impar, se adaugă o pereche suplimentară de numere consecutive astfel încât diferența să fie un număr par.

În final, programul afișează numărul minim de perechi de numere consecutive și perechile de numere (dacă există) în fișierul sumaoni.out. De asemenea, se afișează un mesaj în cazul în care datele de intrare sunt valide sau nu.