0201 - SubmDiv

Cerinţa

Să se determine toate submulţimile cu m elemente ale mulţimii divizorilor unui număr natural x dat.

Date de intrare

Fişierul de intrare submdivIN.txt conţine pe prima linie numerele x şi m,cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire submdivOUT.txt va conţine pe fiecare linie câte o submulţime determinată. Aceste submulţimi for fi afişate în ordine lexicografică. Pentru fiecare submulţime se vor afişa elementele în ordine crescătoare, separate printr-un spaţiu. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

Restricţii şi precizări

• 1 ≤ m ≤ 6
• 1 ≤ x ≤ 1000
• dacă nu există soluţie, pe prima linie a fişierului submdivOUT.txt se va afişa mesajul fara solutie

Exemplul 1

submdivIN.txt

45 4

submdivOUT.txt

1 3 5 9 
1 3 5 15 
1 3 5 45 
1 3 9 15 
1 3 9 45 
1 3 15 45 
1 5 9 15 
1 5 9 45 
1 5 15 45 
1 9 15 45 
3 5 9 15 
3 5 9 45 
3 5 15 45 
3 9 15 45 
5 9 15 45 

Exemplul 2

submdivIN.txt

45 4

submdivOUT.txt

Nu corespunde restrictiilor

Rezolvare

def verificare_restricții(x, m):
    if 1 <= m <= 6 and 1 <= x <= 1000:
        return True
    return False

def genereaza_submultimi(arr, m, curent, index, rezultat):
    if m == 0:
        rezultat.append(curent.copy())
        return
    if index == len(arr):
        return
    curent.append(arr[index])
    genereaza_submultimi(arr, m - 1, curent, index + 1, rezultat)
    curent.pop()
    genereaza_submultimi(arr, m, curent, index + 1, rezultat)

def divizori_submultime(x, m):
    divizori = [i for i in range(1, x + 1) if x % i == 0]
    rezultat = []
    genereaza_submultimi(divizori, m, [], 0, rezultat)
    return sorted(rezultat)  # Sortează submulțimile în ordine lexicografică

def scrie_submultimi_in_fisier(submultimi, fisier_iesire):
    with open(fisier_iesire, 'w') as fisier:
        if not submultimi:
            fisier.write("fara solutie\n")
        else:
            for submultime in submultimi:
                fisier.write(" ".join(map(str, submultime)) + "\n")

if __name__ == "__main__":
    # Citirea datelor din fișierul de intrare
    with open("submdivIN.txt", 'r') as fisier_intrare:
        x, m = map(int, fisier_intrare.readline().split())

    # Verificare restricții
    if not verificare_restricții(x, m):
        with open("submdivOUT.txt", 'w') as fisier_iesire:
            fisier_iesire.write("Nu corespunde restrictiilor\n")
    else:
        # Generarea submulțimilor de divizori
        submultimi = divizori_submultime(x, m)

        # Scrierea rezultatelor în fișierul de ieșire
        scrie_submultimi_in_fisier(submultimi, "submdivOUT.txt")