Simina: /* Date de ieșire */

2023-12-27T14:56:26Z

Date de ieșire

← Older revision		Revision as of 14:56, 27 December 2023
Line 6:		Line 6:

	= Date de ieșire =		= Date de ieșire =
	Fișierul de ieșire <code>subarboriOUT.txt</code> va conține pe prima linie valoarea cerută.		Fișierul de ieșire <code>subarboriOUT.txt</code> va conține pe prima linie valoarea cerută.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

	= Restricții și precizări =		= Restricții și precizări =

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri. Determinați câte perechi de noduri neterminale distincte `p q` din arbore au proprietatea că subarborele cu rădăcina în `p` și cel cu rădăcina în `q` au același număr de noduri. = Date de intrare = Fișierul de intrare `subarboriIN.txt` conține pe prima linie numărul de noduri `n`. Pe linia următoare se află vect...

2023-12-26T23:21:46Z

Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați câte perechi de noduri neterminale distincte <code>p q</code> din arbore au proprietatea că subarborele cu rădăcina în <code>p</code> și cel cu rădăcina în <code>q</code> au același număr de noduri. = Date de intrare = Fișierul de intrare <code>subarboriIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vect...

New page

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați câte perechi de noduri neterminale distincte <code>p q</code> din arbore au proprietatea că subarborele cu rădăcina în <code>p</code> și cel cu rădăcina în <code>q</code> au același număr de noduri.

= Date de intrare =
Fișierul de intrare <code>subarboriIN.txt</code> conține pe prima linie numărul de noduri <code>n</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații.

= Date de ieșire =
Fișierul de ieșire <code>subarboriOUT.txt</code> va conține pe prima linie valoarea cerută.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>

= Exemplul 1: =
<code>subarboriIN.txt</code>
8
4 3 0 3 2 1 2 1
<code>subarboriOUT.txt</code>
1

= Explicație =
Singura pereche de noduri neterminale pentru care subarborii au același număr de noduri este <code>2 1</code>. Subarborii cu rădăcina în <code>2</code> și <code>1</code> au câte <code>3</code> noduri fiecare.

== Exemplul 2: ==
<code>subarboriIN.txt</code>
101
4 3 0 3 2 1 2 1
<code>subarboriOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
class NodArbore:
def __init__(self, valoare):
self.valoare = valoare
self.copii = []

def construieste_arbore(tati):
noduri = [NodArbore(i) for i in range(len(tati))]

for i, tata in enumerate(tati):
if tata != 0:
noduri[tata - 1].copii.append(noduri[i])

return noduri[0] # returnează rădăcina arborelui

def numara_subarbori_cu_acelasi_numar_de_noduri(nod):
if not nod.copii:
return 1, {1: 1} # tuplu: (număr de noduri, dicționar cu numărul de subarbori de acea dimensiune)

total_noduri = 1
dimensiuni_subarbori = {}

for copil in nod.copii:
dimensiune_copil, dimensiuni_subarbori_copil = numara_subarbori_cu_acelasi_numar_de_noduri(copil)
total_noduri += dimensiune_copil

for dimensiune, numar in dimensiuni_subarbori_copil.items():
dimensiuni_subarbori[dimensiune] = dimensiuni_subarbori.get(dimensiune, 0) + numar

dimensiuni_subarbori[total_noduri] = dimensiuni_subarbori.get(total_noduri, 0) + 1

return total_noduri, dimensiuni_subarbori

def verificare_restricții(n):
if not (1 <= n <= 100):
with open("subarboriOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
exit()

def main():
with open("subarboriIN.txt", "r") as fisier_intrare:
n = int(fisier_intrare.readline().strip())
verificare_restricții(n)
tati = list(map(int, fisier_intrare.readline().strip().split()))

radacina = construieste_arbore(tati)
_, dimensiuni_subarbori = numara_subarbori_cu_acelasi_numar_de_noduri(radacina)

rezultat = sum(numar * (numar - 1) // 2 for numar in dimensiuni_subarbori.values())

with open("subarboriOUT.txt", "w") as fisier_iesire:
fisier_iesire.write(str(rezultat))

if __name__ == "__main__":
main()

</syntaxhighlight>

0649 – Subarbori - Revision history

Simina: /* Date de ieșire */