2646 - impartire

Cerința

Se dau n numere naturale, unde n este un număr par. Se grupează cele n numere în perechi şi pentru fiecare pereche de numere se află restul împărţirii unui număr din pereche la celălalt. Se cere să se afle valoarea minimă a sumei acestor resturi.

Date de intrare

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

Date de ieșire

Programul va afișa pe ecran suma minimă a resturilor. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricții și precizări

• 2 ≤ n ≤ 18
• cele n numere citite vor fi mai mici decât 1.000

Exemplul 1

Intrare

4
6 5 3 4

Ieșire

1

Exemplul 2

Intrare

20

consola

Numărul n nu corespunde restricțiilor.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, numbers):

   # Verifică dacă n este un număr par și se află în intervalul [2, 18]
   if n % 2 != 0 or n < 2 or n > 18:
       return False, "Numărul n nu corespunde restricțiilor."

   # Verifică restricțiile pentru numerele naturale
   for num in numbers:
       if num >= 1000:
           return False, "Numerele nu corespund restricțiilor."

   return True, ""

def calculeaza_suma_resturilor(permutare):

   return sum(permutare[i] % permutare[i+1] for i in range(0, len(permutare), 2))

def backtracking(permutare, vizitate, n, numbers, suma_minima):

   if len(permutare) == n:
       suma = calculeaza_suma_resturilor(permutare)
       suma_minima[0] = min(suma_minima[0], suma)
       return

   for i in range(n):
       if not vizitate[i]:
           permutare.append(numbers[i])
           vizitate[i] = True

           backtracking(permutare, vizitate, n, numbers, suma_minima)

           permutare.pop()
           vizitate[i] = False

def main():

   # Citire număr n de la tastatură
   n = int(input("Introduceți numărul n: "))

   # Verificare restricții
   valid, mesaj_eroare = verificare_restrictii(n, [])
   if not valid:
       print("Eroare:", mesaj_eroare)
       return

   # Citire cele n numere naturale de la tastatură
   numbers = list(map(int, input("Introduceți cele {} numere naturale separate prin spații: ".format(n)).split()))

   # Verificare restricții pentru numerele introduse
   valid, mesaj_eroare = verificare_restrictii(n, numbers)
   if not valid:
       print("Eroare:", mesaj_eroare)
       return

   permutare = []
   vizitate = [False] * n
   suma_minima = [float('inf')]

   backtracking(permutare, vizitate, n, numbers, suma_minima)

   print("Suma minimă a resturilor este:", suma_minima[0])

if __name__ == "__main__":

   main()

</syntaxhighlight>