Editing 3281 - sminus

Sursa: [https://www.pbinfo.ro/probleme/3281/sminus 3281 - sminus]
----

Fie un șir a1, a2, …, aN de numere întregi. În acest șir se alege o pereche de indici (x, y), 1 ≤ x ≤ y ≤ N și se inversează semnul tuturor componentelor secvenței ax, ax+1, …, ay. De exemplu, pentru șirul 3, -5, 4, -1, 6, -8, -5, dacă se alege perechea (3, 5), atunci șirul va deveni 3, -5, -4, 1, -6, -8, -5.


== Cerinţa ==
Să se determine o pereche de indici x y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă.


== Date de intrare ==
Fișierul de intrare sminus.in conține pe prima linie numărul N. Pe a doua linie, separate prin câte un spațiu, se găsesc numerele întregi a1, a2, …, aN.


== Date de ieșire == 
Fișierul de ieșire sminus.out va conține două linii. Pe prima linie se vor găsi două numere naturale x și y separate printr-un spațiu reprezentând perechea de indici. Pe linia a doua se va găsi un singur număr natural reprezentând suma minimă obținută prin inversarea semnului componentelor din secvența ax, ax+1, …, ay.

== Restricţii şi precizări ==
* 2 ≤ N ≤ 100.000
* -1000 ≤ ai ≤ 1000 pentru orice i = 1..N
* Secvența ax, ax+1, …, ay trebuie să conțină cel puțin un element.
* Dacă există mai multe soluții pentru perechea (x, y), atunci se va alegea aceea care are indicele x minim, iar dacă sunt mai multe secvențe posibile care încep la poziția x, se va alege aceea care are valoarea y maximă.
* Pentru teste valorând 50 de puncte, N ≤ 2000.
== Exemplu ==
; Intrare
: 7
: 3 -5 4 -1 6 -8 -5
; Ieșire
: 3 5
: -24

== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 3281 - sminus

def read_input():
    n = int(input())
    a = list(map(int, input().split()))
    return n, a

def solve(n, a):
    best_sum = sum(a)
    best_x, best_y = 1, n
    cur_sum = 0
    cur_x = 1
    for i in range(n):
        cur_sum += a[i]
        if cur_sum < best_sum:
            best_sum = cur_sum
            best_x, best_y = cur_x, i+1
        if cur_sum > 0:
            cur_sum = 0
            cur_x = i+2
    return best_x, best_y, best_sum

def validate(n, a, x, y, s):
    assert 1 <= x <= y <= n
    for i in range(x-1, y):
        a[i] *= -1
    assert sum(a) == s

if __name__ == '__main__':
    n, a = read_input()
    x, y, s = solve(n, a)
    validate(n, a, x, y, s)
    print(x, y)
    print(s)


</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția read_input citește datele de intrare și le returnează sub formă de tuple (n, a).

Funcția solve primește n și a și determină o pereche de indici x și y astfel încât după inversarea semnului componentelor secvenței ax, ax+1, …, ay suma elementelor din vector să fie minimă. Pentru a face acest lucru, parcurgem șirul și ținem minte cea mai mică sumă și indicii corespunzători până la fiecare poziție. Dacă suma curentă depășește 0, înseamnă că trebuie să începem o nouă secvență de la următoarea poziție.

Funcția validate primește datele de intrare n și a, perechea de indici x și y și suma s și verifică că inversarea semnului componentelor din secvența ax, ax+1, …, ay duce la suma s.

În funcția main, apelăm funcțiile în ordinea corespunzătoare și afișăm rezultatele.