0320 - Partitii Numar

Cerinţa

Se dă un număr natural n. Determinaţi, în ordine lexicografică, toate modalităţile de a-l scrie pe n ca sumă de numere naturale.

Date de intrare

Fişierul de intrare partitiinumarIN.txt conţine pe prima linie numărul n.

Date de ieşire

Fişierul de ieşire partitiinumarOUT.txt va conţine pe fiecare linie câte un şir de numere naturale ordonate crescător, separate prin câte un spaţiu. Suma numerelor din fiecare şir este n. Şirurile vor fi afişate în ordine lexicografică.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

Restricţii şi precizări

• 1 ≤ n ≤ 40

Exemplul 1:

partitiinumarIN.txt

5

partitiinumarOUT.txt

1 1 1 1 1 
1 1 1 2 
1 1 3 
1 2 2 
1 4 
2 3 
5 

Exemplul 2:

partitiinumarIN.txt

41

partitiinumarOUT.txt

"Datele nu corespund restrictiilor impuse"

Rezolvare:

def check_restrictions(n):
    return 1 <= n <= 40


def generate_partitions(n, current_partition, all_partitions):
    if n == 0:
        all_partitions.append(list(current_partition))
        return
    for i in range(1, n + 1):
        if not current_partition or i >= current_partition[-1]:
            current_partition.append(i)
            generate_partitions(n - i, current_partition, all_partitions)
            current_partition.pop()


def write_partitions_to_file(partitions, output_file):
    with open(output_file, 'w') as file:
        for partition in partitions:
            partition_str = ' '.join(map(str, partition))
            file.write(partition_str + '\n')


def process_input(input_file, output_file):
    with open(input_file, 'r') as file:
        n = int(file.readline().strip())

    if not check_restrictions(n):
        with open(output_file, 'w') as file:
            file.write("Datele nu corespund restrictiilor impuse\n")
    else:
        all_partitions = []
        generate_partitions(n, [], all_partitions)
        all_partitions.sort()
        write_partitions_to_file(all_partitions, output_file)


if __name__ == "__main__":
    input_file = "partitiinumarIN.txt"
    output_file = "partitiinumarOUT.txt"

    process_input(input_file, output_file)