Editing 3643 - Regula

Sursa: [https://www.pbinfo.ro/probleme/3643/regula]
== Cerinţa ==
Dându-se o poziţie din şir se cere determinarea valorii care se află pe acea poziţie.

Dându-se o valoare, să se determine cea mai mică poziţie din şir pe care aceasta se află.

== Date de intrare ==
De la tastatură se citesc două numere C şi V. Dacă avem C = 1, trebuie determinată valoarea de pe poziția V din șir. Dacă avem C = 2 se cere să determinăm cea mai mică poziție din șir unde avem valoarea V.

== 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 &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
: ''sumaoni.in''
: 12
; Ieșire
: Datele introduse corespund cerintelor.
: ''sumaoni.out''
: 7
: 1
: 7
<br>

== Exemplul 2 ==
; Intrare
: ''sumaoni.in''
: 15
; Ieșire
: Datele de intrare corespund cerintelor.
: ''sumaoni.out''
: 5
<br>

== Rezolvare == 
<syntaxhighlight lang="python" line>
#3643
def is_valid(c, v):
    if c == 1:
        if v <= 100000:
            return True
        elif 100000 < v <= 1000000000:
            return True
    elif c == 2:
        if 1 < v <= 35000:
            return True

    return False


def calculate_s(c, v):
    if not is_valid(c, v):
        raise ValueError("Datele introduse nu corespund cerintelor..")

    s = 0

    if c == 1:
        g = 1
        while True:
            s += g + (g + 1) // 2

            if s >= v:
                break

            g += 1

        s -= g + (g + 1) // 2
        v -= s

        if v <= g:
            return v
        else:
            v -= g
            return 2 * v - 1
    else:
        for i in range(1, v):
            s += i + (i + 1) // 2

        return s + v


if __name__ == "__main__":
    c = int(input("Introduceti numar: "))
    v = int(input("Introduceti alt numar: "))

    if not is_valid(c, v):
        print("Datele introduse nu corespund cerintelor.")
    else:
        result = calculate_s(c, v)
        print("Datele introduse corespund cerintelor.")
        print(result)

</syntaxhighlight>

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