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

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.