3688 - Fata Morgana

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>