1942 - Ciclu Hamiltonian

Cerința

Dându-se un număr natural N, aflaţi numărul de cicluri Hamiltoniene dintr-un graf complet cu N noduri.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran numărul cerut.

Restricții și precizări

• 3 ≤ N ≤ 100
• două cicluri diferă dacă au cel puțin o muchie diferită

Exemplul 1:

Intrare

3

Ieșire

1

Explicație

Un graf complet cu 3 noduri are un ciclu Hamiltonian.

Exemplul 2:

Intrare

2

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

def check_restrictions(n):
    if n < 3 or n >= 100:
        print("Datele nu corespund restrictiilor impuse")
        return False
    return True

def inmultire(x, k):
    t = 0
    for i in range(1, x[0] + 1):
        c = x[i] * k + t
        x[i] = c % 10
        t = c // 10
    while t:
        x[0] += 1
        x[x[0]] = t % 10
        t //= 10

def calculate_factorial(n):
    if not check_restrictions(n):
        return

    x = [0] * 1001
    x[0], x[1] = 1, 1

    for i in range(3, n):
        inmultire(x, i)

    for i in range(x[0], 0, -1):
        print(x[i], end='')

def main():
    n = int(input(""))
    calculate_factorial(n)

if __name__ == "__main__":
    main()