3790 - subsets

Sursa: - subsets

---

Cerinţa

Se dă șirul a1, a2, …, an de numere naturale nenule distincte. Vrem să alegem trei submulțimi X, Y și Z cu proprietățile:

• submulțimile sunt nevide
• orice element din șir aparține cel mult unei submulțimi
• cele trei submulțimi au suma elementelor identică

De exemplu, dacă a = (1,2,3,4,5,6), atunci putem alege submulțimile: X={1,4}, Y={2,3}, Z={5}. Se observă că au toate suma elementelor egală cu 5 și că 6 nu apare în niciuna din submulțimi. O altă alegere este X={1,6}, Y={2,5}, Z={3,4} și în acest caz toate submulțimile au suma 7 și toate elementele șirului aparțin uneia dintre submulțimi.

Reținem faptul că ordinea elementelor într-o submulțime nu contează, deci X={1,4} este totuna cu X={4,1}. De asemenea, ordinea celor trei submulțimi nu contează, adică de exemplu X={1,4}, Y={2,3}, Z={5} înseamnă același triplet cu X={2,3}, Y={1,4}, Z={5}.

Să se determine numărul tripletelor de submulțimi care îndeplinesc proprietățile.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n cele numere naturale a1, a2, …, an, separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi va afișa pe ecran numărul tripletelor de submulțimi. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 3 ≤ n ≤ 10
• cele n numere din șir vor fi nenule, distincte două câte două și mai mici decât 100

Exemple

Exemplul 1

Intrare

6

1 2 3 4 5 6

Ieșire

Datele sunt corecte.

3

Exemplul 2

Intrare

5

1 2 3 4 7

Ieșire

Datele sunt corecte.

0

Exemplul 3

Intrare

2

314515341535441 412351541241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 3790 - subsets

def numara_tripleturi(n, vector):

   def verifica_suma_egala(submultimi):
       sume = []
       for submultime in submultimi:
           sume.append(sum(submultime))
       return len(set(sume)) == 1
       
   def backtracking(index, submultimi):
       nonlocal numar
       if index == n:
           if len(submultimi[0]) > 0 and len(submultimi[1]) > 0 and len(submultimi[2]) > 0 and verifica_suma_egala(submultimi):
               numar += 1
           return
       for i in range(3):
           submultimi[i].append(vector[index])
           backtracking(index + 1, submultimi)
           submultimi[i].pop()

   numar = 0
   submultimi = [[], [], []]
   backtracking(0, submultimi)
   return numar // 2
   
   

def conform_restrictiilor(n,vector):

   if not 3 <= n <= 10:
       print("Datele nu sunt conform restricțiilor impuse.")
       return False
   for x in vector:
       if x > 100 or x == 0:
           print("Datele nu sunt conform restricțiilor impuse.")
           return False
   print("Datele sunt corecte.")
   return True
       

if __name__ == '__main__':

   n = int(input())
   vector = list(map(int, input().split()))
   if conform_restrictiilor(n,vector) is True:
      rezultat = numara_tripleturi(n,vector)
      print(rezultat)

</syntaxhighlight>