0318 - Cerc

Cerinţa

Se dau n numere naturale. Determinaţi o aranjare a acestor numere pe un cerc, astfel încât suma produselor de câte două numere vecine să fie maximă.

Date de intrare

Fişierul de intrare cerc.in conţine pe prima linie numărul n, iar pe a doua linie cele n numere naturale, separate prin spaţii.

Date de ieşire

Fişierul de ieşire cerc.out va conţine pe prima linie cele n numere, în ordinea determinată, separate prin exact un spaţiu.

Restricţii şi precizări

• 1 ≤ n ≤ 10
• cele n numere vor avea cel mult 2 cifre
• dacă există mai multe modalităţi de aranjare a numerelor astfel încât să se obţină aceeaşi sumă maximă, se va determina cea lexicografic minimă

Exemplu 1

cerc.in

5

1 2 3 4 5

cerc.out

1 2 4 5 3

Explicație

1*2 + 2*4 + 4*5 + 5*3 + 3*1 = 48, şi este suma maximă care se poate obţine.

Exemplu 2

cerc.in

6

1 2 3 4 5 6

cerc.out

1 2 4 6 5 3

Explicație

1*2 + 2*4 + 4*6 + 6*5 + 5*3 + 3*1 = 82, şi este suma maximă care se poate obţine.

Rezolvare

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

1. 0318 Cerc

from itertools import permutations

def suma_produselor(perm):

   return sum(perm[i] * perm[(i + 1) % len(perm)] for i in range(len(perm)))

def aranjeaza_pe_cerc(n, numere):

   permutari = list(permutations(numere))
   permutari.sort(key=lambda perm: (-suma_produselor(perm), perm))

   return permutari[0]

def validate_input(n, numere):

   if not isinstance(n, int) or n <= 0:
       return False, "Numărul n trebuie să fie un număr întreg pozitiv."

   if len(numere) != n or len(set(numere)) != n:
       return False, f"Trebuie să introduceți exact {n} numere distincte."

   return True, None

def main():

   try:
       with open("cerc.in", "r") as file:
           n = int(file.readline().strip())
           numere = list(map(int, file.readline().split()))
   except (ValueError, FileNotFoundError):
       print("Date de intrare invalide sau fișierul nu există.")
       return

   is_valid, error_message = validate_input(n, numere)

   if not is_valid:
       print("Date de intrare invalide:", error_message)
       return

   rezultat = aranjeaza_pe_cerc(n, numere)

   with open("cerc.out", "w") as file_out:
       file_out.write(" ".join(map(str, rezultat)))

if __name__ == "__main__":

   main()

</syntaxhighlight>