Editing 2646 - impartire

= Cerința =
Se dau <code>n</code> numere naturale, unde <code>n</code> este un număr par. Se grupează cele <code>n</code> 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 <code>n</code>, iar apoi cele <code>n</code> 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 =

* <code>2 ≤ n ≤ 18</code>
* cele <code>n</code> numere citite vor fi mai mici decât <code>1.000</code>

= 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>