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

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