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

<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>