3281 - sminus

Sursa: 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: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou 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., reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

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 1

Intrare

sminus.in

7

3 -5 4 -1 6 -8 -5

Ieșire

sminus.out

Datele sunt introduse correct.

3 5

-24

Exemplu 2

Intrare

sminus.in

7 2 3 5 0.67

3 -5 4 -1 6 -8 -5

Ieșire

sminus.out

Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

# 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)
    try:
        validate(n, a, x, y, s)
        print("Datele sunt introduse corect.")
        print(x, y)
        print(s)
    except AssertionError:
        print("Datele nu corespund restricțiilor impuse.")

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.