2016 - Vuli

Enunț

Vuli este un informatician foarte pasionat de triunghiuri și numere cu proprietăți interesante, aceste două pasiuni au dat naștere unui interes complet nou pentru el, triunghiurile de numere. În prezent, Vuli este interesat de triunghiul lui Pascal, mai exact, de numerele din triunghi de pe o anume linie k care sunt fabuloase (în concepția lui Vuli, un număr este fabulos dacă suma cifrelor numărului este un număr prim, sau este egală cu 1). Triunghiul lui Pascal ce generează astfel: P[0][0] = 1, P[i][j] = P[i - 1][j] + P[i - 1][j - 1]. Vuli este perfect capabil să elaboreze singur un algoritm pentru a determina șirul de numere fabuloase de pe linia k, dar acum este prins cu probleme mai complicate, așa că vă roagă pe voi să-l ajutați.

Cerința

Se cere să se afișeze în ordine crescătoare toate numerele fabuloase de pe linia k a triunghiului.

Date de intrare

Se citește din fișierul de intrare vuliin.txt un număr k ce reprezintă indicele liniei din triunghiului lui Pascal.

Date de ieșire

Se va afișa în fișierul vuliout.txt, pe prima linie, numerele fabuloase de pe linia k a triunghiului, în ordine crescătoare.

Restricții și precizări

• 1 ⩽ k ⩽ 40

Exemplu 1

vuliin.txt

5

vuliout.txt

1 5 10

Exemplu 2

vuliin.txt

0

vuliout.txt

Nu au fost respectate cerintele impuse

Rezolvare

#2016 - Vuli
def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def sum_of_digits(num):
    return sum(int(digit) for digit in str(num))

def generate_fabulous_numbers(k):
    if k <= 0:
        return None

    triangle = [[1]]
    fabulous_numbers = set()

    for i in range(1, k + 1):
        row = [1]
        for j in range(1, i):
            row.append(triangle[i - 1][j] + triangle[i - 1][j - 1])
        row.append(1)
        triangle.append(row)

    for num in triangle[k]:
        if is_prime(sum_of_digits(num)) or sum_of_digits(num) == 1:
            fabulous_numbers.add(num)

    return sorted(fabulous_numbers)

def main():
    with open("vuliin.txt", "r") as file_in, open("vuliout.txt", "w") as file_out:
        k = int(file_in.readline().strip())
        fabulous_numbers = generate_fabulous_numbers(k)

        if fabulous_numbers:
            file_out.write(" ".join(map(str, fabulous_numbers)))
        else:
            file_out.write("Nu au fost respectate cerintele impuse.")

if __name__ == "__main__":
    main()