3790 - subsets - Revision history

Csula Beatrice at 14:43, 30 April 2023

2023-04-30T14:43:41Z

← Older revision		Revision as of 14:43, 30 April 2023
Line 95:		Line 95:

	==Explicaţie cod==		==Explicaţie cod==

			Funcția '''verifica_suma_egala''' primește o listă de submulțimi și verifică dacă suma elementelor din fiecare submulțime este aceeași. Pentru a face acest lucru, se calculează suma elementelor din fiecare submulțime, aceste sume fiind stocate într-o listă. Dacă această listă conține un singur element, înseamnă că suma elementelor din toate cele trei submulțimi este egală.

			Funcția '''backtracking''' primește un index și o listă de submulțimi și generează toate tripleturile posibile de submulțimi care îndeplinesc criteriile impuse. Algoritmul de '''backtracking''' adaugă elemente în submulțimi în mod recursiv, începând cu primul element din '''vector''', și verifică dacă suma elementelor din fiecare submulțime este egală. Dacă această condiție este îndeplinită pentru toate cele trei submulțimi, se incrementează numărul de tripleturi găsite.

			Funcția '''numara_tripleturi''' inițializează o listă vidă pentru fiecare submulțime și apelează funcția '''backtracking''' pentru a genera toate tripleturile de submulțimi. Numărul de tripleturi găsite este returnat împărțit la 2 pentru a elimina duplicatele, deoarece un triplet de submulțimi poate fi reprezentat într-un mod diferit (fiecare submulțime poate fi permutată).

			Funcția '''conform_restrictiilor''' verifică dacă datele de intrare sunt conforme cu restricțiile impuse și returnează True dacă acest lucru este adevărat. Datele de intrare trebuie să aibă o dimensiune cuprinsă între 3 și 10, inclusiv, iar fiecare element din vector trebuie să fie mai mic sau egal cu 100 și diferit de 0.

Csula Beatrice at 18:45, 19 April 2023

2023-04-19T18:45:45Z

← Older revision		Revision as of 18:45, 19 April 2023
Line 46:		Line 46:
	== Rezolvare ==		== Rezolvare ==
	<syntaxhighlight lang="python" line>		<syntaxhighlight lang="python" line>
			#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)

Csula Beatrice: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3790/subsets - 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}'''. S...

2023-04-15T18:22:50Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/3790/subsets - 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}'''. S...

New page

Sursa: [https://www.pbinfo.ro/probleme/3790/subsets - 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.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>

</syntaxhighlight>

==Explicaţie cod==