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.")

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