Vizualizare sursă pentru „0201 - SubmDiv”

= Cerinţa =
Să se determine toate submulţimile cu <code>m</code> elemente ale mulţimii divizorilor unui număr natural <code>x</code> dat.

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

= Date de ieşire =
Fişierul de ieşire <code>submdivOUT.txt</code> 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 =

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

= Exemplul 1 =
<code>submdivIN.txt</code>
 45 4
<code>submdivOUT.txt</code>
 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 =
<code>submdivIN.txt</code>
 45 4
<code>submdivOUT.txt</code>
 Nu corespunde restrictiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
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")

</syntaxhighlight>