2923 - Min Pal

From Bitnami MediaWiki

Cerința

Se dă numărul natural n și un șir de n numere naturale. Determinați numărul minim de operații necesare pentru a face șirul palindromic. Singura operație admisă este înlocuirea a două elemente adiacente cu un element care conține suma lor.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul minim de operații pentru a transforma șirul dat într-un șir palindromic.

Restricții și precizări

  • 1 ≤ n ≤ 1000.000;
  • elementele șirului dat vor fi mai mici decât 10.000;
  • un șir este palindromic dacă se citește la fel în ambele sensuri;

Exemplul 1

Intrare
4
1 4 5 1
Ieșire
Datele de intrare corespund restricțiilor impuse.
1

Exemplul 2

Intrare
0
0
Ieșire
Datele de intrare nu corespund restricțiilor impuse.

Explicație

Se adună 4 cu 5, iar șirul devine 1 9 1

Rezolvare

<syntaxhighlight lang="python" line="1">

  1. 2923 - Min Pal
  1. definim funcția care primește un șir și returnează numărul minim de operații
  2. pentru a forma șirul palindromic

def min_op_palindrome(arr):

   n = len(arr) # lungimea șirului
   operations = 0 # inițializăm numărul de operații cu zero
   # iterăm prima jumătate a șirului
   for i in range(n//2):
       left = arr[i] # primul element, din perechea curentă
       right = arr[n-i-1] # al doilea element din perechea curentă
       # verificăm dacă unul dintre elemente este 0 și trecem la perechea următoare
       if left == 0 or right == 0:
           continue
       # verificăm dacă cele două elemente sunt egale și trecem la perechea următoare
       if left == right:
           continue
       # dacă primul element este mai mare decât al doilea, le interschimbăm
       if left > right:
           left, right = right, left
       # în timp ce primul element este mai mic decât al doilea, îl dublăm și creștem numărul de operații
       while left < right:
           left *= 2
           operations += 1
   return operations # returnăm numărul total de operații
  1. programul principal

if __name__ == '__main__':

   n = int(input("Introduceti numărul de elemente: ")) # citim lungimea șirului de la tastatură
   arr = list(map(int, input("Introduceti elementele sirului: ").split())) # citim elementele șirului de la
   # tastatură și le convertim într-o listă de numere întregi
   # verificarea restricțiilor
   if 1 <= n <= 1000000 and all(0 <= arr[i] < 10000 for i in range(n)):
       print("Datele de intrare corespund restricțiilor impuse.")
       print(min_op_palindrome(arr)) # afișăm numărul minim de operații necesare pentru a # transforma șirul într-un palindrom
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>