Vasiliu Costel Andrei: Pagină nouă: == Enunț == Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţ...

2023-12-27T22:17:32Z

Pagină nouă: == Enunț == Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţ...

New page

== Enunț ==
Fetiţele din grupa mare de la grădiniţă culeg flori şi vor să împletească coroniţe pentru festivitatea de premiere. În grădină sunt mai multe tipuri de flori. Fiecare dintre cele n fetiţe culege un buchet având acelaşi număr de flori, însă nu neapărat de acelaşi tip. Pentru a împleti coroniţele fetiţele se împart în grupe. O fetiţă se poate ataşa unui grup numai dacă are cel puţin o floare de acelaşi tip cu cel puţin o altă fetiţă din grupul respectiv.

== Cerința ==
Fiind dat un număr natural n reprezentând numărul fetiţelor şi numărul natural m reprezentând numărul de flori dintr-un buchet, să se determine grupele care se formează.

== Date de intrare ==
Fişierul de intrare flori2in.txt conţine pe prima linie, separate printr-un spaţiu, numerele naturale n şi m, reprezentând numărul de fetiţe şi respectiv numărul de flori din fiecare buchet. Fiecare dintre următoarele n linii conţine, pentru fiecare fetiţă, câte m valori separate prin câte un spaţiu reprezentând tipurile de flori culese.

== Date de ieșire ==
Fişierul de ieşire flori2out.txt va conţine pe fiecare linie câte o grupă formată din numerele de ordine ale fetiţelor separate prin câte un spaţiu, în ordine crescătoare, ca în exemplu.

== Restricții și precizări ==
* 1 &les; '''n''' &les; 150
* 1 &les; '''m''' &les; 100
* Tipul unei flori este un număr întreg din intervalul [0,100].
* Într-o grupă numerele de ordine ale fetiţelor trebuie date în ordine strict crescătoare.
* În fişierul de ieşire grupele vor fi afişate în ordinea crescătoare a numărului de ordine al primei fetiţe din grupă.

== Exemplul 1 ==
; Intrare
; flori2in.txt
: 5 4
: 1 2 3 4
: 5 6 9 6
: 1 1 1 1
: 2 4 4 3
: 7 7 7 7
; Ieșire
: Datele de intrare corespund restricțiilor impuse
; flori2out.txt
: 1 3 4
: 2
: 5

=== Explicație ===
Fetiţele 1 şi 3 au cules amândouă flori de tipul 1, iar fetiţele 1 şi 4 au cules amândouă flori de tipurile 2, 3 şi 4, deci toate cele trei fetiţe (1, 3, 4) se vor afla în aceiaşi grupă. Fetiţele 2 şi 5 vor forma fiecare câte o grupă deoarece nu au cules flori de acelaşi tip cu nici una dintre celelalte fetiţe.

== Exemplul 2 ==
; Intrare
; flori2in.txt
: 151 4
: 1 2 3 4
: 5 6 9 6
: 1 1 1 1
: 2 4 4 3
: 7 7 7 7
; Ieșire
: Datele de intrare NU corespund restricțiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python" line>
#1378 - Flori2

def valideaza_input(n, m, flori_fete):
if not (1 <= n <= 150 and 1 <= m <= 100):
return False

for lista_flori in flori_fete:
if len(lista_flori) != m:
return False
for tip_floare in lista_flori:
if not (0 <= tip_floare <= 100):
return False

return True

def citeste_date_intrare():
with open("flori2in.txt", "r") as file:
n, m = map(int, file.readline().split())
flori_fete = [list(map(int, file.readline().split())) for _ in range(n)]
return n, m, flori_fete

def grupare_fete(n, flori_fete):
grupuri = []
vizitat = [False] * n

def dfs(nod, grup):
vizitat[nod] = True
grup.append(nod + 1)

for i in range(n):
if not vizitat[i] and any(flor in flori_fete[nod] for flor in flori_fete[i]):
dfs(i, grup)

for i in range(n):
if not vizitat[i]:
grup = []
dfs(i, grup)
grupuri.append(sorted(grup))

return grupuri

def scrie_date_iesire(grupuri):
with open("flori2out.txt", "w") as file:
for grup in grupuri:
file.write(" ".join(map(str, grup)) + "\n")

if __name__ == "__main__":
n, m, flori_fete = citeste_date_intrare()
if valideaza_input(n, m, flori_fete):
print("Datele de intrare corespund restricțiilor impuse")
rezultat = grupare_fete(n, flori_fete)
scrie_date_iesire(rezultat)
else:
print("Datele de intrare NU corespund restricțiilor impuse")

</syntaxhighlight>

1378 - Flori2 - Revision history