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

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")