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

Intrare

4

3 2 1 1

Ieșire

1 2 1 3

Explicație

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

Rezolvare

<syntaxhighlight lang="python" line>def rearrange_array(n, arr):

   # 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__":

   n = int(input("Introduceți numărul n: "))
   numbers = list(map(int, input("Introduceți cele {} numere separate prin spațiu: ".format(n)).split()))

   result = rearrange_array(n, numbers)
   print(" ".join(map(str, result)))

</syntaxhighlight>