3688 - Fata Morgana

From Bitnami MediaWiki

Cerinţa

Teodor se trezește în deșert singur, lipsit de ajutor și speriat. Fata Morgana vine la el și îi arată doi pumni, punându-l pe Teodor să aleagă unul dintre ei. Teodor e norocos și a evitat moartea sigură, dar trebuie să rezolve următoarea problemă pentru Fata Morgana.

“Se dă un vector de n numere pozitive unde n este par. Poți rearanja numerele cum vrei. Care este valoarea maximă a produsului (v[1] - v[2]) * (v[3] - v[4]) * …. * (v[n-1] * v[n]) dintr-o aranjare optimă?”


Fiindcă Fata Morgana nu e naivă, Teodor trebuie să afișeze cel mai mic lexicografic vector cu proprietatea dată, dar fiind lipsit de vlagă, acesta vă cere ajutorul.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieşire

Programul va afișa pe ecran n numere, reprezentând aranjarea cerută de Fata Morgana.

Restricții și precizări

  • 1 ⩽ n ⩽ 300.000
  • 1 ⩽ v[i] ⩽ 2147483647

Exemplu 1

Intrare
4
3 2 1 1
Ieșire
Datele de intrare corespund restrictiilor impuse
1 2 1 3


Exemplu 2

4
3 2 ab 1
Ieșire
Datele de intrare nu corespund restrictiilor impuse


Explicație

(1-2) * (1-3) = 2, acesta fiind produsul maxim posibil.

Rezolvare

<syntaxhighlight lang="python" line> def validare(numar, arr): # functia de validare a datelor de intrare

   if len(arr) != numar:
       raise ValueError
   if numar > 300000:
       raise ValueError
   for numar in arr:
       if not isinstance(numar, int) or numar < 1 or numar > 2147483647:
           raise ValueError
   print("Datele de intrare corespund restrictiilor impuse")


def rearrange_array(arr): # functia de rezolvare

   # Sortăm vectorul în ordine crescătoare
   arr.sort()
   # Rearanjăm vectorul pentru a obține produsul maxim
   for i in range(1, n - 1, 2):
       arr[i], arr[i + 1] = arr[i + 1], arr[i]
   return arr


if __name__ == '__main__':

   # din cauza datelor de intrare pot aparea 2 tipuri de erori, valueError sau IndexError pe care le tratam
   try:
       n = int(input("Introduceți numărul numar: "))
       numbers = list(map(int, input("Introduceți cele {} numere separate prin spațiu: ".format(n)).split()))
       validare(n, numbers)  # apelul functiei de validare
       result = rearrange_array(numbers)  # apelul functiei de rezolvare
       print(" ".join(map(str, result)))
   except ValueError:
       print("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       print("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>