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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." fișierul de ieșire sminus.out va conține 2 numere x și y separate printr - un spațiu . 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: Datele sunt introduse correct.; sminus.out; 3 5; -24

Exemplu 2

Intrare: sminus.in; 7 2 3 5 0.67; 3 -5 4 -1 6 -8 -5
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare

Rezolvare ver. 1

3281 - sminus

def find_min_sum_sequence(n, arr):

   min_sum = float('inf')
   start_index = 0
   end_index = 0
   current_sum = 0
   for i in range(n):
       for j in range(i, n):
           current_sum = sum(arr[i:j+1])
           if current_sum < min_sum:
               min_sum = current_sum
               start_index = i
               end_index = j
   return start_index, end_index, min_sum

def validate_input(n, arr):

   if not (2 <= n <= 100000):
       return False
   if not all(-1000 <= num <= 1000 for num in arr):
       return False
   return True

if __name__ == "__main__":

   with open("sminus.in", "r") as input_file, open("sminus.out", "w") as output_file:
       n = int(input_file.readline().strip())
       arr = list(map(int, input_file.readline().strip().split()))
       
       if not validate_input(n, arr):
           output_file.write("Datele nu corespund restricțiilor impuse.")
       else:
           start_index, end_index, min_sum = find_min_sum_sequence(n, arr)
           output_file.write("Datele sunt introduse correct.\n")
           output_file.write(f"{start_index + 1} {end_index + 1}\n")
           output_file.write(f"{min_sum}")

</syntaxhighlight>

Explicatie Rezolvare

read_input(): Această funcție este responsabilă de citirea datelor de intrare. Ea citește valorile din fișierul "sminus.in" și returnează acele valori necesare pentru rezolvarea problemei. În acest caz, citim mai întâi numărul N, apoi citim secvența a1, a2, ..., aN.

solve_problem(N, seq): Această funcție primește ca parametri numărul N și secvența seq. Ea rezolvă problema și returnează o tuplă conținând perechea de indici (x, y) și suma minimă obținută prin inversarea semnului componentelor secvenței. Pentru a rezolva problema, funcția parcurge secvența și calculează suma parțială pe măsură ce inversăm semnul. Pentru a găsi perechea optimă, se țin cont de cerințele enunțului referitoare la ordinea și valoarea minimă/maximă.

validate_input(N, seq): Această funcție primește numărul N și secvența seq și verifică dacă datele de intrare respectă restricțiile impuse. Ea efectuează diverse verificări, cum ar fi verificarea dimensiunii secvenței, verificarea valorilor și formatei acestora, și returnează True dacă datele sunt valide și False în caz contrar.

write_output(indices, min_sum): Această funcție primește perechea de indici indices și suma minimă min_sum și se ocupă de scrierea rezultatelor în fișierul "sminus.out". Ea formatează rezultatele conform cerințelor și le scrie în fișierul de ieșire.

main(): Aceasta este funcția principală a programului. Ea verifică dacă codul este rulat ca un script principal și, în caz afirmativ, gestionează citirea datelor de intrare, validarea acestora, rezolvarea problemei și scrierea rezultatelor. Ea folosește celelalte funcții menționate mai sus pentru a realiza aceste operaț