Bitnami MediaWiki - User contributions [en]

3058 - vip

2024-03-22T19:08:30Z

Simina:

= Cerința =
Două personaje ale căror nume se vor da în datele de intrare (momentan îi numim Bossanip și Dicsi) își petrec nopțile prin discoteci. Toată lumea știe că Bossanip este membru V.I.P în toate discotecile din lume și Dicsi profită mereu de celebritatea prietenului său. Ajuns pe meleaguri străine, Dicsi s-a confruntat cu o problemă foarte mare. Cum intră la V.I.P când este pe cont propriu? Astfel, Dicsi s-a apucat de infracțiuni precum furtul de identitate. Dicsi dorește să permute literele din numele lui (să găsească o anagramă a propriului nume) astfel încât noul nume să difere prin exact <code>K</code> poziții de numele lui Bossanip. Mai mult, dorește ca această anagramă să fie minimă lexicografic. Dacă reușește, este posibil să se dea drept Bossanip și să intre și el ca membru V.I.P.

= Date de intrare =
În fișierul text <code>vipIN.txt</code> pe prima linie se află numărul natural <code>T</code>. Pe următoarele <code>3∙T</code> linii sunt descrise <code>T</code> seturi de date de intrare, fiecare set ocupă câte trei linii astfel: pe prima linie a unui set se află scrise două numere naturale <code>N</code> (lungimea numelor reale ale lui Bossanip și Dicsi) și <code>K</code>; pe a doua linie a unui set este scris numele lui Bossanip dat printr-un șir de caractere <code>s1</code>; pe a treia linie a unui set este scris numele lui Dicsi dat printr-un șir de caractere <code>s2</code>. Din fericire pentru Dicsi, cele două personaje au nume de aceeași lungime.

= Date de ieșire =
În fișierul text <code>vipOUT.txt</code> se vor scrie, pe fiecare din cele <code>T</code> linii câte un șir de caractere, pe a <code>j</code>-a linie este scrisă anagrama corespunzătoare testului <code>j</code> (noul nume al lui Dicsi) sau <code>-1</code> dacă nu există o astfel de anagramă. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

= Restricții și precizări =

* <code>1 ≤ N, K ≤ 100.000</code>
* Suma valorilor lui <code>N</code> din cadrul seturilor de test este mai mică sau egală cu <code>1.000.000</code>
* Toate literele sunt litere mici ale alfabetului englez
* Dacă nu există soluție pentru un test, atunci se va afișa valoarea <code>-1</code>
* Un șir <code>p1</code>, <code>p2</code>, …, <code>pN</code> este mai mic lexicografic decât un alt șir <code>q1</code>, <code>q2</code>, …, <code>qN</code>, dacă există o poziție <code>i</code> , <code>1 ≤ i ≤ N</code>, astfel încât <code>pi</code> <code>< qi</code> și <code>pj</code> <code>= qj</code>, pentru orice <code>j</code>, <code>1 ≤ j < i</code>.
* Pentru <code>25%</code> din punctaj se poate afișa orice soluție corectă care nu este neapărat minimă lexicografic

= Exemplul 1: =
<code>vipIN.txt</code>
2
8 6
corleone
vasilica
5 2
marko
ghita
<code>vipOUT.txt</code>
caaliisv
-1

=== Explicație: ===
În primul set cea mai mică anagramă a șirului <code>vasilica</code>, din punct de vedere lexicografic, care diferă de șirul <code>corleone</code> pe exact <code>6</code> poziții, este <code>caaliisv</code> În al doilea set nici una din anagramele șirului <code>ghita</code> nu poate să difere pe exact două poziții de șirul <code>marko</code>.

== Exemplul 2: ==
<code>vipIN.txt</code>
2
80000000000 6
corleone
vasilica
5 2
marko
ghita
<code>vipOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_intrare(nume_fisier):
with open(nume_fisier, 'r') as f:
t = int(f.readline().strip())
cazuri = []
for _ in range(t):
n, k = map(int, f.readline().strip().split())
s1 = f.readline().strip()
s2 = f.readline().strip()
cazuri.append((n, k, s1, s2))
return cazuri

def verifica_invariant(freq1, freq2, egali, diferiti, sigma=26):
nevoie_extra_op = 0
max_extra = 0
for i in range(1, sigma + 1):
extra_car = freq1[i] + freq2[i] - diferiti
extra_op = (extra_car + 1) // 2
if extra_op > min(freq1[i], freq2[i]):
return False
max_extra += min(freq1[i], freq2[i])
if extra_op > 0:
nevoie_extra_op += extra_op
return nevoie_extra_op <= egali and egali <= max_extra

def rezolva_caz(n, k, s1, s2):
freq1 = [0] * 27
freq2 = [0] * 27
answer = [''] * (n + 1)

for char in s1:
freq1[ord(char) - ord('a') + 1] += 1
for char in s2:
freq2[ord(char) - ord('a') + 1] += 1

egali = n - k
diferiti = k

if not verifica_invariant(freq1, freq2, egali, diferiti):
return "-1"

for i in range(1, n + 1):
freq1[ord(s1[i-1]) - ord('a') + 1] -= 1
for j in range(1, 27):
if freq2[j] == 0:
continue
freq2[j] -= 1
if ord(s1[i-1]) - ord('a') + 1 == j:
egali -= 1
else:
diferiti -= 1

if verifica_invariant(freq1, freq2, egali, diferiti):
answer[i] = chr(j + ord('a') - 1)
break

if ord(s1[i-1]) - ord('a') + 1 == j:
egali += 1
else:
diferiti += 1

freq2[j] += 1

return ''.join(answer[1:])

def scrie_iesire(nume_fisier, rezultate):
with open(nume_fisier, 'w') as f:
for rez in rezultate:
f.write(f"{rez}\n")

def verifica_restricții(cazuri, nume_fisier_iesire):
suma_n = sum(caz[0] for caz in cazuri) # Suma tuturor valorilor lui N
if not all(1 <= caz[0] <= 100000 and 1 <= caz[1] <= 100000 for caz in cazuri) or suma_n > 1000000:
with open(nume_fisier_iesire, 'w') as f:
f.write("Datele nu corespund restrictiilor impuse\n")
return False
return True

def main():
cazuri = citeste_intrare("vipIN.txt")
if not verifica_restricții(cazuri, "vipOUT.txt"):
return # Oprește execuția dacă datele nu corespund restricțiilor

rezultate = []
for caz in cazuri:
rezultate.append(rezolva_caz(*caz))
scrie_iesire("vipOUT.txt", rezultate)

if __name__ == "__main__":
main()

</syntaxhighlight>

1651 - Graf

2024-01-07T13:07:58Z

Simina:

= Cerința =
Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

= Date de intrare =
Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</code>, reprezentând muchiile, date prin extremități și pondere.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* ponderile muchiilor sunt numere naturale nenule mai mici decât <code>1000</code>
* graful dat nu conține noduri izolate

= Exemplul 1: =
Intrare
5 6
1 2 10
2 3 2
2 5 2
3 5 12
3 4 1
4 5 5
Ieșire
4

=== Explicație ===
Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

* pentru vârful <code>1</code> media este <code>10</code>
* pentru vârful <code>2</code> media este <code>4.66667</code>
* pentru vârful <code>3</code> media este <code>5</code>
* pentru vârful <code>4</code> media este <code>3</code>
* pentru vârful <code>5</code> media este <code>6.33333</code>

Astfel media minimă este <code>3</code>, pentru vârful <code>4</code>

== Exemplul 2: ==
<code>Intrare</code>
<code>101</code>
<code>consola</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from typing import List, Tuple

def check_constraints(n, m, edges):
if not (1 <= n <= 100):
return False
for edge in edges:
i, j, p = edge
if not (1 <= i <= n) or not (1 <= j <= n) or not (1 <= p < 1000):
return False
return True

def main():
nMAX = 100
mat = [[] for _ in range(nMAX + 1)] # mat[i][0] = (j, p) (edge between i and j with weight p)

n, m = map(int, input().split())

if not (1 <= n <= 100):
print("Detele nu respecta restrictiile impuse")
return

edges = [tuple(map(int, input().split())) for _ in range(m)]

if not check_constraints(n, m, edges):
print("Detele nu respecta restrictiile impuse")
return

for i, j, p in edges:
mat[i].append((j, p))
mat[j].append((i, p))

vfmin = 0
medmin = float('inf')

for i in range(1, n + 1):
_sum = sum(weight for _, weight in mat[i])
if _sum / len(mat[i]) < medmin:
medmin = _sum / len(mat[i])
vfmin = i

print(vfmin)

if __name__ == "__main__":
main()

</syntaxhighlight>

0640 – NrFii

2024-01-07T13:03:23Z

Simina:

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

= Date de intrare =
Fișierul de intrare <code>nrfiiIN.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>nrfiiOUT.txt</code> va conține pe prima linie nodurile din arbore cu număr maxim de fii, î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 impuse".

= 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>nrfiiIN.txt</code>
7
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
7

= Explicație =
Nodul <code>7</code> are număr maxim de fii, <code>3</code>.

== Exemplul 2: ==
<code>nrfiiIN.txt</code>
101
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def citeste_arbore(file_path):
with open(file_path, 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().split()))
return n, tati

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("nrfiiOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False

def determina_noduri_max_fii(n, tati):
fii = [0] * (n + 1)
for tata in tati:
if tata != -1:
fii[tata] += 1

max_fii = max(fii)
noduri_max_fii = [i for i in range(1, n + 1) if fii[i] == max_fii]

return noduri_max_fii

def scrie_rezultat(file_path, noduri_max_fii):
with open(file_path, 'w') as file:
if noduri_max_fii:
file.write(' '.join(map(str, noduri_max_fii)))
else:
file.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
file_input = "nrfiiIN.txt"
file_output = "nrfiiOUT.txt"

n, tati = citeste_arbore(file_input)

if verificare_restrictii(n):
noduri_max_fii = determina_noduri_max_fii(n, tati)
scrie_rezultat(file_output, noduri_max_fii)

</syntaxhighlight>

0638 - Nivele

2024-01-07T13:02:20Z

Simina:

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.

= Date de intrare =
Fișierul de intrare <code>niveleIN.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. Linia a treia conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>niveleOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține nivelul pe care se află nodul <code>x[i]</code> în arborele dat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

= Restricții și precizări =

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

= Exemplul 1: =
<code>niveleIN.txt</code>
101
4 1 7 0 7 7 1
4
1 3 4 7
<code>niveleOUT.txt</code>
2
4
1
3

= Exemplul 2: =
<code>niveleIN.txt</code>
7
4 1 7 0 7 7 1
4
1 3 4 7
<code>niveleOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k, tati):
if not(1 <= k <= n <= 100) or tati.count(0) != 1:
with open("niveleOUT.txt", "w") as f_out:
f_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def determina_nivelul(n, tati, k, noduri):
# Verificare pentru restricții
if not verifica_restrictii(n, k, tati):
return

nivele = [0] * n # nivelele pentru fiecare nod
radacina = tati.index(0) + 1 # găsim poziția rădăcinii în vectorul de tați

def dfs(nod, nivel):
nivele[nod - 1] = nivel # nodurile sunt numerotate de la 1, așa că indexăm cu nod-1
for fiu in range(1, n + 1):
if tati[fiu - 1] == nod:
dfs(fiu, nivel + 1)

dfs(radacina, 1)

rezultate = [nivele[nod - 1] for nod in noduri]

# Scrierea rezultatelor în fișierul de ieșire
with open("niveleOUT.txt", "w") as f_out:
for rezultat in rezultate:
f_out.write(str(rezultat) + "\n")

# Citirea datelor de intrare
with open("niveleIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().split()))
k = int(f.readline().strip())
noduri = list(map(int, f.readline().split()))

# Determinarea nivelului pentru fiecare nod dat
determina_nivelul(n, tati, k, noduri)

</syntaxhighlight>

4167 – FlșiElimină

2024-01-07T13:01:15Z

Simina:

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:
struct Nod
{
int info;
Nod *leg;
};
în care câmpul <code>info</code> memorează un număr întreg, iar câmpul <code>leg</code> memorează adresa următorului element al listei.

= Cerinţa =
Să se scrie o funcție python cu următorul prototip:
def FLsiElimina(head): head = None
care, în lista pentru care primul element are adresa memorată în pointerul <code>head</code>, elimină toate nodurile cuprinse între cel mai din stânga nod care memorează un număr divizibil cu <code>3</code> și cel mai din dreapta nod care memorează un număr divizibil cu <code>3</code>, inclusiv acestea. Se garantează că lista va conține cel puțin două noduri care au informația divizibilă cu <code>3</code>. Dacă se elimină toate nodurile, atunci după apelul funcției trebuie ca <code>head = NULL</code>. De exemplu, dacă lista conține inițial informațiile <code>1,27,3,4,13,12,44,23</code>, atunci la final lista va fi: <code>1,44,23</code>.

= Important =
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

== Rezolvare ==
<syntaxhighlight lang="python3">
class Nod:
def __init__(self, info):
self.info = info
self.leg = None

def FLsiElimina(head):
# Cautăm primul nod cu informația divizibilă cu 3
primul_nod = None
nod_curent = head

while nod_curent is not None and nod_curent.info % 3 != 0:
primul_nod = nod_curent
nod_curent = nod_curent.leg

# Cautăm ultimul nod cu informația divizibilă cu 3
ultimul_nod = None
nod_curent = head
while nod_curent is not None:
if nod_curent.info % 3 == 0:
ultimul_nod = nod_curent
nod_curent = nod_curent.leg

# Eliminăm nodurile cuprinse între primul_nod și ultimul_nod, inclusiv acestea
nod_curent = head
while nod_curent is not None and nod_curent != primul_nod:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

if primul_nod is not None:
primul_nod.leg = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator
else:
# Dacă primul_nod este None, eliminăm toate nodurile de la început până la ultimul_nod
head = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

return head

# Funcție de afișare a listei
def afisare_lista(head):
while head is not None:
print(head.info, end=" ")
head = head.leg
print()

head = Nod(1)
head.leg = Nod(27)
head.leg.leg = Nod(3)
head.leg.leg.leg = Nod(4)
head.leg.leg.leg.leg = Nod(13)
head.leg.leg.leg.leg.leg = Nod(12)
head.leg.leg.leg.leg.leg.leg = Nod(44)
head.leg.leg.leg.leg.leg.leg.leg = Nod(23)

print("Lista initiala:", end=" ")
afisare_lista(head)

head = FLsiElimina(head)

print("Lista finala:", end=" ")
afisare_lista(head)

</syntaxhighlight>

0963 - Bazine

2024-01-07T12:58:17Z

Simina:

== Enunț ==
La ştrandul Junior din oraşul nostru s-au construit <code>n</code> bazine pentru înot. Fiecare bazin a fost dotat cu câte un robinet pentru umplerea acestuia cu apă. Între <code>m</code> perechi distincte de bazine, a fost instalată câte o ţeavă prin care apa din cele două bazine din fiecare pereche să poată circula. Astfel, cele două bazine din pereche pot fi umplute prin deschiderea unui singur robinet.

Administratorul bazei a numerotat bazinele cu numerele distincte de la <code>1</code> la <code>n</code> şi a notat în registrul lui cele <code>m</code> perechi de numere <code>(x1,y1)</code>, <code>(x2,y2)</code>,…., <code>(xm,ym)</code> corespunzând perechilor de bazine între care a fost instalată câte o ţeavă. Pentru a umple toate bazinele cu apă, administratorul doreşte să deschidă un număr minim de robinete.

Cerinţă.

Scrieţi un program care să citească numerele naturale <code>n</code> şi <code>m</code>, şi cele <code>2*m</code> numere naturale <code>x1</code>, <code>y1</code>, <code>x2</code>, <code>y2</code>,…., <code>xm</code>, <code>ym</code>, cu semnificația din enunț, şi care să afişeze cel mai mic număr <code>k</code> de robinete pe care trebuie să le deschidă administratorul astfel încât să fie umplute cu apă toate bazinele.

= Date de intrare =
Fișierul de intrare <code>bazineIN.txt</code> conține pe prima linie numerele <code>n m</code>, iar pe următoarele <code>m</code> linii căte o pereche de numere <code>x y</code>.

= Date de ieșire =
Fișierul de ieșire <code>bazineOUT.txt</code> va conține pe prima linie numărul <code>k</code> determinat.

= Restricții și precizări =

* <code>10 ≤ n ≤ 100</code>
* <code>8 ≤ m ≤ 400</code>
* nu există două perechi de numere <code>(x,y)</code>, <code>(x’,y’)</code> astfel încât <code>x=x’</code> şi <code>y=y’</code> sau <code>x=y’</code> şi <code>y=x’</code> printre cele <code>m</code> perechi citite din fişier
* <code>1 ≤ xi ≤ n</code> , <code>1 ≤ yi ≤ n</code> , <code>xi ≠ yi</code>
* fiecare bazin poate fi cuplat la unul sau mai multe bazine prin câte o ţeavă, sau la nici un bazin

= Exemplul 1 =
<code>bazineIN.txt</code>
10 8
1 6
4 5
8 6
3 7
9 4
1 8
10 6
1 10
<code>bazineOUT.txt</code>
4

= Explicație =
Apa din bazinele <code>1</code>, <code>6</code>, <code>8</code> şi <code>10</code> comunică doar între acestea, fiind instalate ţevi. Astfel pentru aceste patru bazine este necesar să se deschidă un singur robinet pentru umplerea lor.

Apa din bazinele <code>4</code>, <code>5</code> şi <code>9</code> comunică, deoarece între acestea sunt ţevi. Astfel pentru aceste bazine este necesar să se deschidă un singur robinet.

Pentru bazinele <code>3</code> şi <code>7</code> între care există teavă, se deschide un singur robinet, cele două bazine nefiind legate prin ţevi de celelalte bazine

Bazinul <code>2</code> nu este cuplat cu niciun alt bazin, fiind necesar să se deschidă robinetul acestuia.

În total se deschid doar <code>4</code> robinete pentru a alimenta toate bazinele

== Exemplul 2 ==
<code>bazineIN.txt</code>
5 5
<code>bazineOUT.txt</code>
Datele nu corespund restrictiilor impuse
Rezolvare<syntaxhighlight lang="python3" line="1">
class Graf:
def __init__(self, varfuri):
self.varfuri = varfuri
self.lista_adiacenta = {i: [] for i in range(1, varfuri + 1)}

def adauga_muchie(self, u, v):
self.lista_adiacenta[u].append(v)
self.lista_adiacenta[v].append(u)

def numar_minim_robinete(self):
vizitate = set()
robinete = 0

for varf in range(1, self.varfuri + 1):
if varf not in vizitate:
robinete += 1
self.dfs(varf, vizitate)

return robinete

def dfs(self, varf, vizitate):
vizitate.add(varf)
for vecin in self.lista_adiacenta[varf]:
if vecin not in vizitate:
self.dfs(vecin, vizitate)

def verifica_restrictii(n, m, perechi):
if not(10 <= n <= 100) or not(8 <= m <= 400):
return False

for i in range(m):
x, y = perechi[i]
if not(1 <= x <= n) or not(1 <= y <= n) or x == y:
return False

for i in range(m):
for j in range(i + 1, m):
if set(perechi[i]) == set(perechi[j]):
return False

return True

if __name__ == "__main__":
with open("bazineIN.txt", "r") as fisier_intrare:
n, m = map(int, fisier_intrare.readline().split())
perechi = [tuple(map(int, fisier_intrare.readline().split())) for _ in range(m)]

if not verifica_restrictii(n, m, perechi):
with open("bazineOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
else:
graf = Graf(n)

for x, y in perechi:
graf.adauga_muchie(x, y)

with open("bazineOUT.txt", "w") as fisier_iesire:
k = graf.numar_minim_robinete()
fisier_iesire.write(str(k))

</syntaxhighlight>

3556 - xorsum

2024-01-07T12:54:00Z

Simina: /* Exemplul 1 */

= Cerința =
Se dau numerele naturale <code>n</code>, <code>x</code>, <code>y</code>, <code>z</code>, <code>t</code>. Se generează vectorul <code>a</code> astfel: <code>a[i] = (a[i-1] * x + y) % z</code>, pentru <code>1 ≤ i ≤ n</code> si <code>a[i] = 0</code> pentru <code>i = 0</code>. Determinați <code>∑(a[i] XOR a[j])</code>, unde <code>1 ≤ i < j ≤ n</code>, modulo <code>t</code>.

= Date de intrare =
Programul citește de la tastatură numerele <code>n</code>, <code>x</code>, <code>y</code>, <code>z</code>, <code>t</code>.

= Date de ieșire =
Programul va afișa pe ecran numărul cerut.

= Restricții și precizări =

* <code>1 ≤ n ≤ 250.000</code>
* <code>1 ≤ x, y, z, t < 2^62</code>

= Exemplul 1 =
Intrare
250001 1 1 4 7
Ieșire
6

=== Explicație ===
<code>a = {0, 1, 2, 3}</code>

<code>S = ((1 XOR 2) + (1 XOR 3) + (2 XOR 3)) MOD 7 = (3 + 2 + 1) MOD 7 = 6</code>

== Exemplul 2 ==
<code>Intrare</code>
<code>3 1 1 4 7</code>
<code>consola</code>
<code>Datele introduse nu respectă restricțiile.</code>

== Rezolvare ==
<syntaxhighlight lang="python3">
def check_restrictions(n, x, y, z, t):
if not (1 <= n <= 250000):
print("Eroare: n trebuie să fie între 1 și 250,000.")
return False
if not (1 <= x < 2**62 and 1 <= y < 2**62 and 1 <= z < 2**62 and 1 <= t < 2**62):
print("Eroare: x, y, z, și t trebuie să fie între 1 și 2^62.")
return False
return True

def calculate_xor_sum(n, x, y, z, t):
if not check_restrictions(n, x, y, z, t):
print("Datele introduse nu respectă restricțiile.")
return None

a = [0] * (n + 1)
xor_sum = 0

for i in range(1, n + 1):
a[i] = (a[i - 1] * x + y) % z

for i in range(1, n + 1):
for j in range(i + 1, n + 1):
xor_sum = (xor_sum + (a[i] ^ a[j])) % t

return xor_sum

# Citirea datelor de intrare cu mesaje și verificare restricții
input_values = input("Introduceți valorile separate prin spațiu (n x y z t): ").split()

# Verificare dacă numărul de valori introduse este corect
if len(input_values) != 5:
print("Eroare: Trebuie să introduceți exact 5 valori.")
else:
n, x, y, z, t = map(int, input_values)
# Calcularea și afișarea rezultatului
result = calculate_xor_sum(n, x, y, z, t)
if result is not None:
print("Rezultatul este:", result)

</syntaxhighlight>

1887 - Dijkstra2

2023-12-27T18:08:37Z

Simina: /* Date de ieșire */

= Cerința =
Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt <code>n</code> case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa <code>p</code>, casa lui Vlad, și casele vecinilor. În cazul în care nu există drum până la unul dintre vecini, se va afișa <code>-1</code>.

= Date de intrare =
Programul citește din fișier numărul <code>n</code>, numărul de case din comunitate, <code>m</code>, numărul de drumuri dintre case, <code>p</code>, numărul casei lui Vlad, iar pe următoarele <code>m</code> linii se vor afla <code>x</code>, <code>y</code> și <code>d</code> cu semnificația că există drum între casele <code>x</code> și <code>y</code> de lungime <code>d</code>.

= Date de ieșire =
Programul va afișa <code>n</code> numere separate printr-un spațiu, al <code>i</code>-lea număr reprezentând distanța minimă de la casa lui Vlad la casa <code>i</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ p ≤ n ≤ 100.000</code>
* <code>1 ≤ m ≤ 250.000</code>
* cele <code>m</code> distanțe citite vor fi mai mici decât <code>20.000</code>

= Exemplul 1: =
<code>dijkstra2IN.txt</code>
5 6 2
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
2 0 2 7 3

=== Explicație ===
Drumurile minime de la casa lui Vlad la celelalte case sunt <code>2 0 2 7 3</code>.

== Exemplul 2: ==
<code>dijkstra2IN.txt</code>
10000000 22 44
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(n, m, p, drumuri):
graf = {i: [] for i in range(1, n+1)}

for drum in drumuri:
x, y, d = drum
graf[x].append((y, d))
graf[y].append((x, d))

distante = {i: float('inf') for i in range(1, n+1)}
distante[p] = 0
coada_prioritati = [(0, p)]

while coada_prioritati:
distanta_curenta, nod_curent = heapq.heappop(coada_prioritati)

if distanta_curenta > distante[nod_curent]:
continue

for vecin, cost_muchie in graf[nod_curent]:
distanta_noua = distante[nod_curent] + cost_muchie

if distanta_noua < distante[vecin]:
distante[vecin] = distanta_noua
heapq.heappush(coada_prioritati, (distanta_noua, vecin))

return distante

def verifica_restrictii(n, m, p, drumuri):
if not (1 <= p <= n <= 100000) or not (1 <= m <= 250000):
return False

for drum in drumuri:
if drum[2] >= 20000:
return False

return True

# Citire date de intrare din fișier
with open('dijkstra2IN.txt', 'r') as fisier_intrare:
n, m, p = map(int, fisier_intrare.readline().split())
drumuri = [list(map(int, fisier_intrare.readline().split())) for _ in range(m)]

# Verificare restricții
if not verifica_restrictii(n, m, p, drumuri):
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
else:
# Calculare distanțe minime
distante = dijkstra(n, m, p, drumuri)

# Afisare rezultat în fișier
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(' '.join(map(str, [distante[i] if distante[i] != float('inf') else -1 for i in range(1, n+1)])))

</syntaxhighlight>

0588 - Dijkstra

2023-12-27T18:08:15Z

Simina: /* Date de ieșire */

= Cerința =
Se dă un graf orientat ponderat cu <code>n</code> noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod <code>p</code>. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la <code>p</code> la fiecare nod al grafului.

= Date de intrare =
Fișierul de intrare <code>dijkstraIN.txt</code> conține pe prima linie numerele <code>n p</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există arcul <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>dijkstraOUT.txt</code> va conține pe prima linie <code>n</code> numere, separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând costul drumului minim de la <code>p</code> la <code>i</code>. Dacă nu există drum de la <code>p</code> la un anumit vârf, costul afișat va fi <code>-1</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* costul unui arc va fi mai mic decât <code>1000</code>
* costul unui drum este egal cu suma costurilor arcelor care îl compun

= Exemplul 1: =
<code>dijkstraIN.txt</code>
5 4
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
<code>dijkstraOUT.txt</code>
3 1 4 0 -1

= Exemplul 2: =
<code>dijkstraIN.txt</code>
1001 12
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
<code>dijkstraOUT.txt</code>
"Datele nu corespund restrictiilor impuse"

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(graph, start):
n = len(graph)
INF = float('inf')
distante = [INF] * n
distante[start] = 0
heap = [(0, start)]

while heap:
dist_curenta, nod_curent = heapq.heappop(heap)

if dist_curenta > distante[nod_curent]:
continue

for vecin, cost in graph[nod_curent]:
distanta_noua = dist_curenta + cost
if distanta_noua < distante[vecin]:
distante[vecin] = distanta_noua
heapq.heappush(heap, (distanta_noua, vecin))

return distante

def verificare_restrictii(n, graph):
# Verificarea restrictiilor
if not (1 <= n <= 100):
return False
for node_edges in graph:
for _, cost in node_edges:
if not (cost < 1000):
return False
return True

def citeste_intrare(file_path):
with open(file_path, 'r') as file:
n, p = map(int, file.readline().split())

# Verificare restrictii
if not (1 <= n <= 100):
return n, p, None

graf = [[] for _ in range(n)]

for _ in range(n):
i, j, c = map(int, file.readline().split())
graf[i-1].append((j-1, c))

return n, p, graf

def scrie_iesire(file_path, distante, restrictii_valide):
with open(file_path, 'w') as file:
if not restrictii_valide:
file.write("Datele nu corespund restrictiilor impuse")
else:
for dist in distante:
if dist == float('inf'):
file.write("-1 ")
else:
file.write(str(dist) + " ")

def main():
fisier_intrare = 'dijkstraIN.txt'
fisier_iesire = 'dijkstraOUT.txt'

n, p, graf = citeste_intrare(fisier_intrare)

# Verificare restricții
restrictii_valide = verificare_restrictii(n, graf)

if not restrictii_valide:
# Dacă restricțiile nu sunt respectate, scrie mesajul în fișierul de ieșire
scrie_iesire(fisier_iesire, [], restrictii_valide)
else:
# Altfel, aplică algoritmul lui Dijkstra și scrie rezultatele în fișierul de ieșire
distante = dijkstra(graf, p-1)
scrie_iesire(fisier_iesire, distante, restrictii_valide)

if __name__ == "__main__":
main()

</syntaxhighlight>

1887 - Dijkstra2

2023-12-27T18:07:11Z

Simina: Pagină nouă: = Cerința = Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt <code>n</code> case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa <code>p</code>, casa lui Vlad, și casele vecinilo...

= Cerința =
Dijkstra este un cetățean model al comunității în care trăiește. El își ajută fiecare vecin aflat în necaz. Astăzi, Vlad îi cere ajutorul și îl roagă să livreze câte un pachet fiecărui vecin de-al lor. Știind că sunt <code>n</code> case în aceasta comunitate, iar distanțele dintre ele variază, Dijkstra vă roagă să realizați un program care să afișeze costul drumului minim dintre casa <code>p</code>, casa lui Vlad, și casele vecinilor. În cazul în care nu există drum până la unul dintre vecini, se va afișa <code>-1</code>.

= Date de intrare =
Programul citește din fișier numărul <code>n</code>, numărul de case din comunitate, <code>m</code>, numărul de drumuri dintre case, <code>p</code>, numărul casei lui Vlad, iar pe următoarele <code>m</code> linii se vor afla <code>x</code>, <code>y</code> și <code>d</code> cu semnificația că există drum între casele <code>x</code> și <code>y</code> de lungime <code>d</code>.

= Date de ieșire =
Programul va afișa <code>n</code> numere separate printr-un spațiu, al <code>i</code>-lea număr reprezentând distanța minimă de la casa lui Vlad la casa <code>i</code>.

= Restricții și precizări =

* <code>1 ≤ p ≤ n ≤ 100.000</code>
* <code>1 ≤ m ≤ 250.000</code>
* cele <code>m</code> distanțe citite vor fi mai mici decât <code>20.000</code>

= Exemplul 1: =
<code>dijkstra2IN.txt</code>
5 6 2
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
2 0 2 7 3

=== Explicație ===
Drumurile minime de la casa lui Vlad la celelalte case sunt <code>2 0 2 7 3</code>.

== Exemplul 2: ==
<code>dijkstra2IN.txt</code>
10000000 22 44
3 5 1
5 4 9
4 3 5
1 2 2
3 2 2
1 3 8
<code>dijkstra2OUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(n, m, p, drumuri):
graf = {i: [] for i in range(1, n+1)}

for drum in drumuri:
x, y, d = drum
graf[x].append((y, d))
graf[y].append((x, d))

distante = {i: float('inf') for i in range(1, n+1)}
distante[p] = 0
coada_prioritati = [(0, p)]

while coada_prioritati:
distanta_curenta, nod_curent = heapq.heappop(coada_prioritati)

if distanta_curenta > distante[nod_curent]:
continue

for vecin, cost_muchie in graf[nod_curent]:
distanta_noua = distante[nod_curent] + cost_muchie

if distanta_noua < distante[vecin]:
distante[vecin] = distanta_noua
heapq.heappush(coada_prioritati, (distanta_noua, vecin))

return distante

def verifica_restrictii(n, m, p, drumuri):
if not (1 <= p <= n <= 100000) or not (1 <= m <= 250000):
return False

for drum in drumuri:
if drum[2] >= 20000:
return False

return True

# Citire date de intrare din fișier
with open('dijkstra2IN.txt', 'r') as fisier_intrare:
n, m, p = map(int, fisier_intrare.readline().split())
drumuri = [list(map(int, fisier_intrare.readline().split())) for _ in range(m)]

# Verificare restricții
if not verifica_restrictii(n, m, p, drumuri):
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
else:
# Calculare distanțe minime
distante = dijkstra(n, m, p, drumuri)

# Afisare rezultat în fișier
with open('dijkstra2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(' '.join(map(str, [distante[i] if distante[i] != float('inf') else -1 for i in range(1, n+1)])))

</syntaxhighlight>

0588 - Dijkstra

2023-12-27T18:01:54Z

Simina: Pagină nouă: = Cerința = Se dă un graf orientat ponderat cu <code>n</code> noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod <code>p</code>. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la <code>p</code> la fiecare nod al grafului. = Date de intrare = Fișierul de intrare <code>dijkstraIN.txt</code> conține pe prima linie numerele <code>n p</code>, iar următoarele linii câte un triplet <code>i j c</code>...

= Cerința =
Se dă un graf orientat ponderat cu <code>n</code> noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod <code>p</code>. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la <code>p</code> la fiecare nod al grafului.

= Date de intrare =
Fișierul de intrare <code>dijkstraIN.txt</code> conține pe prima linie numerele <code>n p</code>, iar următoarele linii câte un triplet <code>i j c</code>, cu semnificația: există arcul <code>(i j)</code> și are costul <code>c</code>.

= Date de ieșire =
Fișierul de ieșire <code>dijkstraOUT.txt</code> va conține pe prima linie <code>n</code> numere, separate prin exact un spațiu, al <code>i</code>-lea număr reprezentând costul drumului minim de la <code>p</code> la <code>i</code>. Dacă nu există drum de la <code>p</code> la un anumit vârf, costul afișat va fi <code>-1</code>.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* costul unui arc va fi mai mic decât <code>1000</code>
* costul unui drum este egal cu suma costurilor arcelor care îl compun

= Exemplul 1: =
<code>dijkstraIN.txt</code>
5 4
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
<code>dijkstraOUT.txt</code>
3 1 4 0 -1

= Exemplul 2: =
<code>dijkstraIN.txt</code>
1001 12
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2
<code>dijkstraOUT.txt</code>
"Datele nu corespund restrictiilor impuse"

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
import heapq

def dijkstra(graph, start):
n = len(graph)
INF = float('inf')
distante = [INF] * n
distante[start] = 0
heap = [(0, start)]

while heap:
dist_curenta, nod_curent = heapq.heappop(heap)

if dist_curenta > distante[nod_curent]:
continue

for vecin, cost in graph[nod_curent]:
distanta_noua = dist_curenta + cost
if distanta_noua < distante[vecin]:
distante[vecin] = distanta_noua
heapq.heappush(heap, (distanta_noua, vecin))

return distante

def verificare_restrictii(n, graph):
# Verificarea restrictiilor
if not (1 <= n <= 100):
return False
for node_edges in graph:
for _, cost in node_edges:
if not (cost < 1000):
return False
return True

def citeste_intrare(file_path):
with open(file_path, 'r') as file:
n, p = map(int, file.readline().split())

# Verificare restrictii
if not (1 <= n <= 100):
return n, p, None

graf = [[] for _ in range(n)]

for _ in range(n):
i, j, c = map(int, file.readline().split())
graf[i-1].append((j-1, c))

return n, p, graf

def scrie_iesire(file_path, distante, restrictii_valide):
with open(file_path, 'w') as file:
if not restrictii_valide:
file.write("Datele nu corespund restrictiilor impuse")
else:
for dist in distante:
if dist == float('inf'):
file.write("-1 ")
else:
file.write(str(dist) + " ")

def main():
fisier_intrare = 'dijkstraIN.txt'
fisier_iesire = 'dijkstraOUT.txt'

n, p, graf = citeste_intrare(fisier_intrare)

# Verificare restricții
restrictii_valide = verificare_restrictii(n, graf)

if not restrictii_valide:
# Dacă restricțiile nu sunt respectate, scrie mesajul în fișierul de ieșire
scrie_iesire(fisier_iesire, [], restrictii_valide)
else:
# Altfel, aplică algoritmul lui Dijkstra și scrie rezultatele în fișierul de ieșire
distante = dijkstra(graf, p-1)
scrie_iesire(fisier_iesire, distante, restrictii_valide)

if __name__ == "__main__":
main()

</syntaxhighlight>

0473 - Bipartit Complet

2023-12-27T14:57:07Z

Simina: /* Date de ieşire */

= Cerinţa =
Se consideră două mulţimi nevide <code>A</code> şi <code>B</code>, cu proprietatea că formează o partiție a mulțimii <code>{1,2,...,n}.</code> Să se construiască un graf bipartit complet cu <code>n</code> vârfuri, bipartit peste partiţia formată din mulțimile <code>A</code> și <code>B</code>.

= Date de intrare =
Fişierul de intrare <code>bipartitcompletIN.txt</code> conţine pe prima linie numărul <code>n</code>. Urmează un număr <code>k</code>, apoi <code>k</code> numere naturale distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând vârfurile din <code>A</code>. Mulțimea <code>B</code> conține toate numerele naturale cuprinse între <code>1</code> și <code>n</code> care nu sunt în <code>A</code>.

= Date de ieşire =
Fişierul de ieşire <code>bipartitcompletOUT.txt</code> va conţine matricea de adiacență a grafului construit, câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricţii şi precizări =

* <code>1 < k < n ≤ 100</code>

= Exemplul 1: =
<code>bipartitcompletIN.txt</code>
7
3
4 6 3
<code>bipartitcompletOUT.txt</code>
0 0 1 1 0 1 0
0 0 1 1 0 1 0
1 1 0 0 1 0 1
1 1 0 0 1 0 1
0 0 1 1 0 1 0
1 1 0 0 1 0 1
0 0 1 1 0 1 0

= Exemplul 2 : =
<code>bipartitcompletIN.txt</code>
1001
3
4 6 3
<code>bipartitcompletOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(k, n):
if not (1 < k < n <= 100):
with open("bipartitcompletOUT.txt", 'w') as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

def construieste_graf(n, A):
# Inițializăm matricea de adiacență cu zerouri
graf = [[0] * n for _ in range(n)]

# Marcam conexiunile dintre vârfurile din A și B
for i in A:
for j in range(1, n + 1):
if j not in A:
graf[i - 1][j - 1] = 1
graf[j - 1][i - 1] = 1 # Adăugăm și conexiunea inversă

return graf

def scrie_matrice_in_fisier(matrice, nume_fisier):
with open(nume_fisier, 'w') as f:
for linie in matrice:
f.write(' '.join(map(str, linie)) + '\n')

if __name__ == "__main__":
# Citim datele de intrare din fișier
with open("bipartitcompletIN.txt", 'r') as f:
n = int(f.readline().strip())
k = int(f.readline().strip())
A = list(map(int, f.readline().strip().split()))

# Verificăm restricțiile
if not verifica_restrictii(k, n):
exit()

# Construim graful bipartit
graf = construieste_graf(n, A)

# Scriem matricea de adiacență în fișierul de ieșire
scrie_matrice_in_fisier(graf, "bipartitcompletOUT.txt")

</syntaxhighlight>

1651 - Graf

2023-12-27T14:56:52Z

Simina:

= Cerința =
Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

= Date de intrare =
Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</code>, reprezentând muchiile, date prin extremități și pondere.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* ponderile muchiilor sunt numere naturale nenule mai mici decât <code>1000</code>
* graful dat nu conține noduri izolate

= Exemplul 1: =
Intrare
5 6
1 2 10
2 3 2
2 5 2
3 5 12
3 4 1
4 5 5
Ieșire
4

=== Explicație ===
Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

* pentru vârful <code>1</code> media este <code>10</code>
* pentru vârful <code>2</code> media este <code>4.66667</code>
* pentru vârful <code>3</code> media este <code>5</code>
* pentru vârful <code>4</code> media este <code>3</code>
* pentru vârful <code>5</code> media este <code>6.33333</code>

Astfel media minimă este <code>3</code>, pentru vârful <code>4</code>

== Exemplul 2: ==
<code>Intrare</code>
<code>101</code>
<code>consola</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, m, muchii):
# Verificăm restricțiile
if not (1 <= n <= 100) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii):
return False
return True

def gaseste_varf_minim_media_ponderilor(n, m, muchii):
# Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf
ponderi_vf = {i: [] for i in range(1, n + 1)}

# Citim și memorăm ponderile muchiilor în dicționar
for i in range(m):
vf1, vf2, pondera = muchii[i]
ponderi_vf[vf1].append(pondera)
ponderi_vf[vf2].append(pondera)

# Calculăm media aritmetică a ponderilor pentru fiecare vârf
medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()}

# Găsim vârful cu media minimă
vf_min_media = min(medii_ponderi, key=medii_ponderi.get)

return vf_min_media

# Citirea numărului de vârfuri
n = int(input("Introduceți numărul de vârfuri "))
if not (1 <= n <= 100):
print("Datele nu corespund restrictiilor impuse")
else:
# Citirea numărului de muchii
m = int(input("Introduceți numărul de muchii: "))

# Citirea muchiilor și ponderilor
print("Introduceți extremitățile și ponderea fiecărei muchii:")
muchii = [tuple(map(int, input().split())) for _ in range(m)]

# Apelarea funcției și afișarea rezultatului
rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii)
if rezultat is not None:
print(rezultat)

</syntaxhighlight>

3693 – Binary Tree

2023-12-27T14:56:42Z

Simina:

== Enunț ==
Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.

= Cerința =
Se dau un arbore binar complet infinit cu rădăcina în nodul <code>1</code> în care pentru orice nod <code>i</code> copiii săi sunt nodurile <code>2*i</code>, respectiv <code>2*i+1</code> și <code>Q</code> perechi de numere <code>u v</code>. Se cere să se afle pentru fiecare pereche lungimea cel mai scurt drum(ca număr de muchii) dintre nodurile <code>u</code> și <code>v</code> din arbore.

= Date de intrare =
Programul citește de la tastatură numărul <code>Q</code>, iar apoi <code>Q</code> perechi de numere naturale, fiecare pereche pe câte o linie.

= Date de ieșire =
Programul va afișa pe ecran pentru fiecare pereche <code>u v</code> distanța dintre nodurile <code>u</code> și <code>v</code> din arbore.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ Q ≤ 100.000</code>
* <code>1 ≤ u, v ≤ 2.000.000.000</code>

= Exemplul 1: =
Intrare
5
1 2
4 5
8 15
11 3
12 14
Ieșire
1
2
6
4
4

=== Explicație ===
Așa arată primele <code>4</code> nivele ale arborelui descris în enunț:

== Exemplul 2: ==
Intrare
100000000
Consola
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(Q, u, v):
if not (1 <= Q <= 100000) or not (1 <= u <= 2000000000) or not (1 <= v <= 2000000000) or u < 0 or v < 0:
print("Datele nu corespund restrictiilor impuse")
exit()

def gaseste_distanta(u, v):
# Funcție pentru a găsi distanța dintre două noduri în arborele binar complet
distanta = 0
while u != v:
# Asigurăm că u este întotdeauna mai mic sau egal decât v
if u > v:
u, v = v, u
v //= 2 # Urmează căutarea pe nivelul anterior pentru v
distanta += 1

return distanta

# Citim numărul de perechi
Q = int(input("Introdu numărul de perechi (Q): "))

# Verificăm restricțiile pentru Q
verificare_restrictii(Q, Q, Q)

valori_u = []
valori_v = []

# Citim și procesăm fiecare pereche
for _ in range(Q):
u, v = map(int, input("Introdu perechea u v: ").split())
valori_u.append(u)
valori_v.append(v)

# Verificăm restricțiile pentru u și v
verificare_restrictii(Q, max(valori_u), max(valori_v))

# Afișăm rezultatele la final
print("\nRezultate:")

for u, v in zip(valori_u, valori_v):
distanta = gaseste_distanta(u, v)
print(f"{distanta}")

</syntaxhighlight>

0647 – Subarbore2

2023-12-27T14:56:35Z

Simina:

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarbore2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe a doua linie se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe linia a treia se află, în ordine, valorile asociate nodurilor din arbore.

= Date de ieșire =
Fișierul de ieșire <code>subarbore2OUT.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 =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* valorile asociate nodurilor din arbore sunt numere întregi din intervalul <code>[-1000,1000]</code>

= Exemplul 1: =
<code>subarbore2IN.txt</code>
8 4
4 3 0 3 2 1 4 1
-3 -2 4 4 0 -3 3 2
<code>subarbore2OUT.txt</code>
3

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, k):
if not (1 <= n <= 100) or not (1 <= k <= n):
with open('subarbore2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, lista_adiacenta, valori):
suma_subarbore = valori[nod - 1] # Corectarea indexării pentru a evita IndexError
for copil in lista_adiacenta[nod]:
suma_subarbore += dfs(copil, lista_adiacenta, valori)
return suma_subarbore

def main():
# Citirea datelor de intrare
with open('subarbore2IN.txt', 'r') as fisier:
n, k = map(int, fisier.readline().split())

# Verificarea restricțiilor
if not verificare_restrictii(n, k):
return

# Citirea celorlalte date de intrare
with open('subarbore2IN.txt', 'r') as fisier:
fisier.readline() # Trecem peste linia cu n și k
parinti = list(map(int, fisier.readline().split()))
valori = list(map(int, fisier.readline().split()))

# Construirea listei de adiacență
lista_adiacenta = {i: [] for i in range(1, n + 1)}
for i in range(n):
if parinti[i] != 0:
lista_adiacenta[parinti[i]].append(i + 1)

# Calcularea sumei valorilor asociate nodurilor din subarborele cu rădăcina în k
rezultat = dfs(k, lista_adiacenta, valori)

# Scrierea rezultatului în fișierul de ieșire
with open('subarbore2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(str(rezultat))

if __name__ == "__main__":
main()

</syntaxhighlight>

0649 – Subarbori

2023-12-27T14:56:26Z

Simina: /* Date de ieșire */

= 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ă.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

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

0646 – Subarbore1

2023-12-27T14:56:15Z

Simina: /* Date de ieșire */

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, î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 impuse".

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarbore1IN.txt</code>
8 4
4 3 0 3 2 1 4 1
<code>subarbore1OUT.txt</code>
6 7 8

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def dfs(nod, lista_adiacenta, rezultat):
# Verificăm dacă nodul este terminal
if nod not in lista_adiacenta:
rezultat.append(nod)
return

# Parcurgem vecinii nodului și aplicăm DFS pe fiecare dintre ei
for vecin in lista_adiacenta[nod]:
dfs(vecin, lista_adiacenta, rezultat)

def verifica_restrictii(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarbore1OUT.txt", 'w') as fisier:
fisier.write("Datele nu corespund restrictiilor impuse")
exit()

def main(fisier_intrare, fisier_iesire):
with open(fisier_intrare, 'r') as fisier:
# Citim numărul de noduri și nodul k
n, k = map(int, fisier.readline().split())

# Verificăm dacă restricțiile sunt respectate
verifica_restrictii(n, k)

# Citim vectorul de tați al arborelui
tati = list(map(int, fisier.readline().split()))

# Construim o listă de adiacență bazată pe vectorul de tați
lista_adiacenta = {}
for i in range(n):
parinte = tati[i]
if parinte not in lista_adiacenta:
lista_adiacenta[parinte] = []
lista_adiacenta[parinte].append(i + 1) # Adăugăm nodul curent ca fiu al nodului părinte

# Aplicăm DFS pentru a identifica nodurile terminale din subarborele cu rădăcina în nodul k
rezultat = []
dfs(k, lista_adiacenta, rezultat)

# Scriem rezultatul în fișierul de ieșire
with open(fisier_iesire, 'w') as fisier:
if not rezultat:
fisier.write("Subarborele nu are noduri terminale")
else:
fisier.write(' '.join(map(str, sorted(rezultat))))

# Exemplu de utilizare
main("subarbore1IN.txt", "subarbore1OUT.txt")

</syntaxhighlight>

0648 – Subarbore Numărare

2023-12-27T14:56:03Z

Simina: /* Date de ieșire */

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați câte noduri conține subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarborenumarareIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarborenumarareOUT.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 =

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

= Exemplul 1: =
<code>subarborenumarareIN.txt</code>
8 4
4 3 0 3 2 1 4 1
<code>subarborenumarareOUT.txt</code>
5

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def numara_noduri_subarbore(n, k, vector_tati):
relatii = {}

for i in range(1, n + 1):
parinte = vector_tati[i - 1]
if parinte not in relatii:
relatii[parinte] = []
relatii[parinte].append(i)

def numara_noduri_recursiv(nod):
numar_noduri = 1
if nod in relatii:
for copil in relatii[nod]:
numar_noduri += numara_noduri_recursiv(copil)
return numar_noduri

rezultat = numara_noduri_recursiv(k)

return rezultat

def verificare_restricții(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarborenumarareOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

# Citire date de intrare
with open("subarborenumarareIN.txt", "r") as f:
n, k = map(int, f.readline().split())
vector_tati = list(map(int, f.readline().split()))

# Verificare restricții
if verificare_restricții(n, k):
# Calcul și scriere rezultat în fișierul de ieșire
rezultat = numara_noduri_subarbore(n, k, vector_tati)
with open("subarborenumarareOUT.txt", "w") as f:
f.write(str(rezultat))

</syntaxhighlight>

0641 – Subarbore

2023-12-27T14:55:51Z

Simina:

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarboreIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarboreOUT.txt</code> va conține pe prima linie nodurile din subarbore, î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 impuse".

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarboreIN.txt</code>
7 7
4 1 7 0 7 7 1
<code>subarboreOUT.txt</code>
3 5 6 7

= Exemplul 2: =
<code>subarboreIN.txt</code>
101 2
4 1 7 0 7 7 1
<code>subarboreOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarboreOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, lista_adiacenta, noduri_subarbore):
noduri_subarbore.append(nod)
for copil in lista_adiacenta[nod]:
dfs(copil, lista_adiacenta, noduri_subarbore)

def main():
# Citirea datelor de intrare
with open("subarboreIN.txt", "r") as infile:
n, k = map(int, infile.readline().split())
parinti = list(map(int, infile.readline().split()))

# Verificarea restricțiilor
if not verifica_restrictii(n, k):
return

# Construirea listei de adiacență bazată pe vectorul de tați
lista_adiacenta = {i: [] for i in range(1, n + 1)}
for i in range(1, n + 1):
if parinti[i - 1] != 0:
lista_adiacenta[parinti[i - 1]].append(i)

# Identificarea și colectarea nodurilor din subarbore
noduri_subarbore = []
dfs(k, lista_adiacenta, noduri_subarbore)

# Sortarea și scrierea rezultatelor în fișierul de ieșire
noduri_subarbore.sort()
with open("subarboreOUT.txt", "w") as outfile:
outfile.write(" ".join(map(str, noduri_subarbore)))

if __name__ == "__main__":
main()

</syntaxhighlight>

0640 – NrFii

2023-12-27T14:55:38Z

Simina:

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

= Date de intrare =
Fișierul de intrare <code>nrfiiIN.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>nrfiiOUT.txt</code> va conține pe prima linie nodurile din arbore cu număr maxim de fii, î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 impuse".

= 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: =
<syntaxhighlight lang="python3" line="1">
def citeste_arbore(file_path):
with open(file_path, 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().split()))
return n, tati

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("nrfiiOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False

def determina_noduri_max_fii(n, tati):
fii = [0] * (n + 1)
for tata in tati:
if tata != -1:
fii[tata] += 1

max_fii = max(fii)
noduri_max_fii = [i for i in range(1, n + 1) if fii[i] == max_fii]

return noduri_max_fii

def scrie_rezultat(file_path, noduri_max_fii):
with open(file_path, 'w') as file:
if noduri_max_fii:
file.write(' '.join(map(str, noduri_max_fii)))
else:
file.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
file_input = "nrfiiIN.txt"
file_output = "nrfiiOUT.txt"

n, tati = citeste_arbore(file_input)

if verificare_restrictii(n):
noduri_max_fii = determina_noduri_max_fii(n, tati)
scrie_rezultat(file_output, noduri_max_fii)

</syntaxhighlight><code>nrfiiIN.txt</code>
7
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
7

= Explicație =
Nodul <code>7</code> are număr maxim de fii, <code>3</code>.

== Exemplul 2: ==
<code>nrfiiIN.txt</code>
101
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

0650 – kNivel

2023-12-27T14:55:26Z

Simina:

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și o valoare <code>k</code>. Determinați nodurile situate pe nivelul <code>k</code> în arbore.

= Date de intrare =
Fișierul de intrare <code>knivelIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și valoarea <code>k</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>knivelOUT.txt</code> va conține pe prima linie, în ordine crescătoare, nodurile situate pe nivelul <code>k</code> în arbore.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* pe nivelul <code>k</code> va exista cel puțin un nod

= Exemplul 1: =
<code>knivelIN.txt</code>
8 3
4 3 0 3 2 1 2 1
<code>knivelOUT.txt</code>
1 5 7

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, k):
if 1 <= n <= 100:
return True
else:
return False

def gaseste_noduri_pe_nivel(tati, nivel):
noduri_pe_nivel = []
for i in range(len(tati)):
nivel_nod_curent = 1 # Nivelul rădăcinii
parinte_curent = tati[i]

while parinte_curent != 0:
parinte_curent = tati[parinte_curent - 1]
nivel_nod_curent += 1

if nivel_nod_curent == nivel:
noduri_pe_nivel.append(i + 1)

return noduri_pe_nivel

def main():
# Citirea datelor de intrare din fișier
with open("knivelIN.txt", "r") as fisier_intrare:
n, k = map(int, fisier_intrare.readline().split())
tati = list(map(int, fisier_intrare.readline().split()))

# Verificarea restricțiilor
if not verificare_restrictii(n, k):
with open("knivelOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return

# Găsirea nodurilor de pe nivelul k
noduri_pe_nivel_k = gaseste_noduri_pe_nivel(tati, k)

# Scrierea rezultatului în fișierul de ieșire
with open("knivelOUT.txt", "w") as fisier_iesire:
if noduri_pe_nivel_k:
fisier_iesire.write(" ".join(map(str, noduri_pe_nivel_k)))
else:
fisier_iesire.write("Nu există noduri pe nivelul specificat")

if __name__ == "__main__":
main()

</syntaxhighlight>

4159 – Nivele11

2023-12-27T14:55:14Z

Simina:

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat.

= Date de intrare =
Fișierul de intrare <code>nivele11IN.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>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= 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>nivele11IN.txt</code>
8
4 3 0 3 2 1 2 1
<code>nivele11OUT.txt</code>
3
2 4
1 5 7
6 8

= Explicație =
Pe nivelul 0 se află rădăcina, adică nodul 3. Pe nivelul 1 se află nodurile 2 și 4 (descentenții direcți ai rădăcinii). Pe nivelul 2 se află nodurile 1, 5 și 7. Pe ultimul nivel se află nodurile 6 și 8.

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict, deque

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open('nivele11OUT.txt', 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return False

def parcurgere_pe_nivele(n, tati):
if not verificare_restrictii(n):
return []

# Construim lista de adiacență pentru arbore
graf = defaultdict(list)
radacina = -1

for i in range(n):
parinte = tati[i]

if parinte == 0:
radacina = i + 1
else:
graf[parinte].append(i + 1)

# Folosim BFS pentru a parcurge nodurile pe nivele
nivele = []
vizitat = [False] * (n + 1)
queue = deque([(radacina, 0)]) # Rădăcina se află pe nivelul 0

while queue:
nod, nivel = queue.popleft()
if not vizitat[nod]:
vizitat[nod] = True

# Adăugăm nodul la lista corespunzătoare nivelului său
if len(nivele) <= nivel:
nivele.append([])
nivele[nivel].append(nod)

# Adăugăm fiii nodului în coadă cu nivelul actual + 1
for fiu in graf[nod]:
if not vizitat[fiu]:
queue.append((fiu, nivel + 1))

return nivele

# Citim datele din fișierul de intrare
with open('nivele11IN.txt', 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().strip().split()))

# Obținem rezultatul
rezultat = parcurgere_pe_nivele(n, tati)

# Dacă rezultatul nu este gol, scriem rezultatul în fișierul de ieșire
if rezultat:
with open('nivele11OUT.txt', 'w') as file:
for nivel in rezultat:
file.write(' '.join(map(str, nivel)) + '\n')

</syntaxhighlight>

4156 – Nivele Pare

2023-12-27T14:55:03Z

Simina: /* Date de ieșire */

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungimea lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodurile situate pe nivele pare.

= Date de intrare =
Fișierul de intrare <code>nivelepareIN.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>nivelepareOUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>2*(i-1)</code>.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= 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>nivelepareIN.txt</code>
8
4 3 0 3 2 1 2 1
<code>nivelepareOUT.txt</code>
3
1 5 7

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
return False

def citeste_arbore_din_fisier(file_path):
with open(file_path, 'r') as file:
n = int(file.readline())
if not verifica_restrictii(n):
return None, None, "Datele nu corespund restrictiilor impuse"
parinti = list(map(int, file.readline().split()))
return n, parinti, None

def scrie_noduri_pe_nivele_pare(file_path, nivele_pare):
with open(file_path, 'w') as file:
for nivel in nivele_pare:
file.write(' '.join(map(str, nivel)) + '\n')

def noduri_pe_nivele_pare(n, parinti):
nivele_pare = [[] for _ in range(n)]

for i in range(n):
parinte = parinti[i]
nivel = 0
while parinte != 0:
nivel += 1
parinte = parinti[parinte - 1]

if nivel % 2 == 0:
nivele_pare[nivel // 2].append(i + 1)

return nivele_pare

if __name__ == "__main__":
input_file = "nivelepareIN.txt"
output_file = "nivelepareOUT.txt"

n, parinti, restrictii_msg = citeste_arbore_din_fisier(input_file)

if restrictii_msg:
with open(output_file, 'w') as file:
file.write(restrictii_msg)
else:
nivele_pare = noduri_pe_nivele_pare(n, parinti)
scrie_noduri_pe_nivele_pare(output_file, nivele_pare)

</syntaxhighlight>

0639 – Înălțime

2023-12-27T14:54:52Z

Simina: /* Date de ieșire */

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați înălțimea arborelui.

= Date de intrare =
Fișierul de intrare <code>inaltimeIN.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>inaltimeOUT.txt</code> va conține pe prima linie numărul <code>H</code> , reprezentând înălțimea arborelui.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

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

= Exemplu 1: =
<code>inaltimeIN.txt</code>
7
4 1 7 0 7 7 1
<code>inaltimeOUT.txt</code>
4

= Exemplu 2: =
<code>inaltimeIN.txt</code>
101
4 1 7 0 7 7 1
<code>inaltimeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("inaltimeOUT.txt", "w") as file:
file.write("Datele nu corespund restrictiilor impuse")
return False

def calculeaza_inaltimea(n, tati):
if not verifica_restrictii(n):
return

inaltime = 0
nivele = [0] * n

for i in range(n):
nivel = 0
j = i
while tati[j] != 0:
nivel += 1
j = tati[j] - 1
if nivele[j] != 0:
nivel += nivele[j]
break

nivele[i] = nivel
inaltime = max(inaltime, nivel + 1)

with open("inaltimeOUT.txt", "w") as file:
file.write(str(inaltime))

def main():
# Citirea datelor de intrare
with open("inaltimeIN.txt", "r") as file:
n = int(file.readline())
if not verifica_restrictii(n):
return
tati = list(map(int, file.readline().split()))

# Calcularea inaltimii arborelui
calculeaza_inaltimea(n, tati)

if __name__ == "__main__":
main()

</syntaxhighlight>

2749 – Tată

2023-12-27T14:54:43Z

Simina: /* Date de ieșire */

= Cerința =
Se dă un vector <code>t=(t[1], t[2], ..., t[n])</code> care memorează numere naturale cuprinse între <code>0</code> și <code>n</code>. Să se verifice dacă <code>t</code> este sau nu vector de tați asociat unui arbore cu rădăcină.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran mesajul <code>DA</code>, dacă <code>t</code> este vector de tați, sau mesajul <code>NU</code> în caz contrar.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* <code>0 ≤ t[i] ≤ n</code>

= Exemplul 1: =
Intrare
5
0 1 1 3 3
Ieșire
DA

= Exemplul 2: =
Intrare
5
2 0 2 5 4
Ieșire
NU

=== Explicație ===
Nodul <code>4</code> are ca tată pe <code>5</code>, iar nodul <code>5</code> are ca tată pe <code>4</code>

== Exemplul 3: ==
Intrare
100001
Consola
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
def sunt_restrictii_incorecte(n, t):
# Verifică restricțiile pentru n
if not (1 <= n <= 100000):
return True

# Verifică restricțiile pentru t[i]
for i in range(n):
if not (0 <= t[i] <= n):
return True

return False

def este_vector_de_tati(t):
n = len(t)

# Verifică dacă restricțiile sunt respectate
if sunt_restrictii_incorecte(n, t):
return False

# Verifică dacă rădăcina arborelui este corectă
if t[0] != 0:
return False

# Verifică dacă fiecare element al vectorului este un index valid
for i in range(1, n):
if not (0 <= t[i] < n):
return False

return True

# Citeste numarul n
n = int(input("Introduceti numarul n: "))

# Ieși din program dacă restricțiile pentru n nu sunt respectate
if n < 1 or n > 100000:
print("Datele nu corespund restrictiilor impuse")
else:
# Citeste vectorul t
t = list(map(int, input("Introduceti vectorul t: ").split()))

# Verifica daca restrictiile sunt respectate si afiseaza mesajul corespunzator
if sunt_restrictii_incorecte(n, t):
print("Datele nu corespund restrictiilor impuse")
else:
# Verifica daca t este vector de tati si afiseaza rezultatul
if este_vector_de_tati(t):
print("DA")
else:
print("NU")

</syntaxhighlight>

0652 – Afișare Fii

2023-12-27T14:54:30Z

Simina: /* Date de ieșire */

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri distincte din arbore. Afișați fiii fiecăruia dintre cele <code>k</code> noduri.

= Date de intrare =
Fișierul de intrare <code>afisarefiiIN.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. Linia a trei conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>afisarefiiOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține numărul de fii ai lui <code>x[i]</code> urmat de un spațiu și de lista fiilor lui <code>x[i]</code>, separați și ei printr-un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* dacă un nod <code>x[i]</code> nu are fii, linia corespunzătoare din fișierul de ieșire va contine doar valoarea <code>0</code>

= Exemplul 1: =
<code>afisarefiiIN.txt</code>
8
4 3 0 3 2 1 2 1
4
3 4 7 1
<code>afisarefiiOUT.txt</code>
2 2 4
1 1
0
2 6 8

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

== Rezolvare ==
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k):
if not (1 <= k <= n <= 100):
return "Datele nu corespund restrictiilor impuse"
return None

def afisare_fii(n, tati, k, noduri_selectate):
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
return restrictii_mesaj

rezultat = []

for nod in noduri_selectate:
if not (1 <= nod <= n):
return "Datele nu corespund restrictiilor impuse"

fii = [i for i, parinte in enumerate(tati, 1) if parinte == nod]
rezultat.append((len(fii), fii))

return rezultat

# Citirea datelor de intrare
with open("afisarefiiIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().strip().split()))
k = int(f.readline().strip())
noduri_selectate = list(map(int, f.readline().strip().split()))

# Verificarea restricțiilor și obținerea rezultatului
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
with open("afisarefiiOUT.txt", "w") as f:
f.write(restrictii_mesaj)
else:
rezultat = afisare_fii(n, tati, k, noduri_selectate)
with open("afisarefiiOUT.txt", "w") as f:
if isinstance(rezultat, str):
f.write(rezultat)
else:
for nr_fii, fii in rezultat:
f.write(f"{nr_fii} {' '.join(map(str, fii))}\n")

</syntaxhighlight>

0636 – Arbore

2023-12-27T14:53:27Z

Simina:

= Cerința =
Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui.

= Date de ieșire =
Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-un spațiu.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor impuse".

= Restricții și precizări =

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

= Exemplul 1 : =
<code>arboreIN.txt</code>
7 4
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
4 1 7 0 7 7 1

= Exemplul 2 : =
<code>arboreIN.txt</code>
1000 1001
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k, muchii):
if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
# Verifică dacă nodurile din muchii sunt în intervalul corect
for muchie in muchii:
if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, parinte, graf, rezultat):
rezultat[nod] = parinte
for vecin in graf[nod]:
if vecin != parinte:
dfs(vecin, nod, graf, rezultat)

def main():
# Citirea datelor de intrare
with open("arboreIN.txt", "r") as file_in:
n, k = map(int, file_in.readline().split())
muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]

# Verificarea restricțiilor
if not verifica_restrictii(n, k, muchii):
return

# Construirea grafului
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])

# Inițializarea vectorului de tați cu 0
parinti = [0] * (n + 1)

# Apelarea algoritmului DFS
dfs(k, 0, graf, parinti)

# Scrierea rezultatului în fișierul de ieșire
with open("arboreOUT.txt", "w") as file_out:
file_out.write(" ".join(map(str, parinti[1:])))

if __name__ == "__main__":
main()

</syntaxhighlight>

0638 - Nivele

2023-12-27T14:52:48Z

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află. = Date de intrare = Fișierul de intrare <code>niveleIN.txt<...

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.

= Date de intrare =
Fișierul de intrare <code>niveleIN.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. Linia a treia conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>niveleOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține nivelul pe care se află nodul <code>x[i]</code> în arborele dat.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Nu corespunde restricțiilor".

= Restricții și precizări =

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

= Exemplul 1: =
<code>niveleIN.txt</code>
7
4 1 7 0 7 7 1
4
1 3 4 7
<code>niveleOUT.txt</code>
2
4
1
3

= Exemplul 2: =
<code>niveleIN.txt</code>
7
4 1 7 0 7 7 1
4
1 3 4 7
<code>niveleOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k, tati):
if not(1 <= k <= n <= 100) or tati.count(0) != 1:
with open("niveleOUT.txt", "w") as f_out:
f_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def determina_nivelul(n, tati, k, noduri):
# Verificare pentru restricții
if not verifica_restrictii(n, k, tati):
return

nivele = [0] * n # nivelele pentru fiecare nod
radacina = tati.index(0) + 1 # găsim poziția rădăcinii în vectorul de tați

def dfs(nod, nivel):
nivele[nod - 1] = nivel # nodurile sunt numerotate de la 1, așa că indexăm cu nod-1
for fiu in range(1, n + 1):
if tati[fiu - 1] == nod:
dfs(fiu, nivel + 1)

dfs(radacina, 1)

rezultate = [nivele[nod - 1] for nod in noduri]

# Scrierea rezultatelor în fișierul de ieșire
with open("niveleOUT.txt", "w") as f_out:
for rezultat in rezultate:
f_out.write(str(rezultat) + "\n")

# Citirea datelor de intrare
with open("niveleIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().split()))
k = int(f.readline().strip())
noduri = list(map(int, f.readline().split()))

# Determinarea nivelului pentru fiecare nod dat
determina_nivelul(n, tati, k, noduri)

</syntaxhighlight>

0473 - Bipartit Complet

2023-12-27T14:47:41Z

Simina: Pagină nouă: = Cerinţa = Se consideră două mulţimi nevide <code>A</code> şi <code>B</code>, cu proprietatea că formează o partiție a mulțimii <code>{1,2,...,n}.</code> Să se construiască un graf bipartit complet cu <code>n</code> vârfuri, bipartit peste partiţia formată din mulțimile <code>A</code> și <code>B</code>. = Date de intrare = Fişierul de intrare <code>bipartitcompletIN.txt</code> conţine pe prima linie numărul <code>n</code>. Urmează un număr <code>k</code...

= Cerinţa =
Se consideră două mulţimi nevide <code>A</code> şi <code>B</code>, cu proprietatea că formează o partiție a mulțimii <code>{1,2,...,n}.</code> Să se construiască un graf bipartit complet cu <code>n</code> vârfuri, bipartit peste partiţia formată din mulțimile <code>A</code> și <code>B</code>.

= Date de intrare =
Fişierul de intrare <code>bipartitcompletIN.txt</code> conţine pe prima linie numărul <code>n</code>. Urmează un număr <code>k</code>, apoi <code>k</code> numere naturale distincte cuprinse între <code>1</code> și <code>n</code>, reprezentând vârfurile din <code>A</code>. Mulțimea <code>B</code> conține toate numerele naturale cuprinse între <code>1</code> și <code>n</code> care nu sunt în <code>A</code>.

= Date de ieşire =
Fişierul de ieşire <code>bipartitcompletOUT.txt</code> va conţine matricea de adiacență a grafului construit, câte o linie a matricei pe o linie a fișierului, elementele de pe o linie fiind separate prin exact un spațiu.

= Restricţii şi precizări =

* <code>1 < k < n ≤ 100</code>

= Exemplul 1: =
<code>bipartitcompletIN.txt</code>
7
3
4 6 3
<code>bipartitcompletOUT.txt</code>
0 0 1 1 0 1 0
0 0 1 1 0 1 0
1 1 0 0 1 0 1
1 1 0 0 1 0 1
0 0 1 1 0 1 0
1 1 0 0 1 0 1
0 0 1 1 0 1 0

= Exemplul 2 : =
<code>bipartitcompletIN.txt</code>
1001
3
4 6 3
<code>bipartitcompletOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(k, n):
if not (1 < k < n <= 100):
with open("bipartitcompletOUT.txt", 'w') as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

def construieste_graf(n, A):
# Inițializăm matricea de adiacență cu zerouri
graf = [[0] * n for _ in range(n)]

# Marcam conexiunile dintre vârfurile din A și B
for i in A:
for j in range(1, n + 1):
if j not in A:
graf[i - 1][j - 1] = 1
graf[j - 1][i - 1] = 1 # Adăugăm și conexiunea inversă

return graf

def scrie_matrice_in_fisier(matrice, nume_fisier):
with open(nume_fisier, 'w') as f:
for linie in matrice:
f.write(' '.join(map(str, linie)) + '\n')

if __name__ == "__main__":
# Citim datele de intrare din fișier
with open("bipartitcompletIN.txt", 'r') as f:
n = int(f.readline().strip())
k = int(f.readline().strip())
A = list(map(int, f.readline().strip().split()))

# Verificăm restricțiile
if not verifica_restrictii(k, n):
exit()

# Construim graful bipartit
graf = construieste_graf(n, A)

# Scriem matricea de adiacență în fișierul de ieșire
scrie_matrice_in_fisier(graf, "bipartitcompletOUT.txt")

</syntaxhighlight>

4112 - Falkland

2023-12-27T14:36:03Z

Simina: Pagină nouă: = Cerința = Pe teritoriul insulelelor FalkLand exista <code>n</code> britanici notati de la <code>1</code> la <code>n</code> si <code>m</code> argentinieni notati de la <code>1</code> la <code>m</code>. Aceștia sunt în pragul războiului din pricina neînțelegerilor teritoriale. Pentru a restabili pacea prim-ministrul Marii Britanii Margaret Thatcher a venit cu o idee ingenioasă, care presupune renunțarea la acest teritoriu atât din partea Argentinei cât și a Marii...

= Cerința =
Pe teritoriul insulelelor FalkLand exista <code>n</code> britanici notati de la <code>1</code> la <code>n</code> si <code>m</code> argentinieni notati de la <code>1</code> la <code>m</code>.

Aceștia sunt în pragul războiului din pricina neînțelegerilor teritoriale. Pentru a restabili pacea prim-ministrul Marii Britanii Margaret Thatcher a venit cu o idee ingenioasă, care presupune renunțarea la acest teritoriu atât din partea Argentinei cât și a Marii Britanii, insulele Falkland urmând să devină un teritoriu autonom.

Deoarece în cazul unui război ambele părți au de pierdut, Leopoldo Galtieri(președintele Argentinei) a acceptat propunerea. Pentru a-și îndeplini planul, aceștia trebuie să detensioneze relațiile dintre argentinieni și britanici în scopul de a crea un teritoriu autonom prosper.

Fiecare britanic are diferite cunoștințe de naționalitate argentiniană pe insula. Deoarece aceștia se cunosc între ei, nu sunt dușmani de moarte, dar nici prieteni.

Se știe că fiecare britanic poate lega <code>o singură</code> relație de prietenie cu una dintre cunoștințele sale argentiniene și vice-versa. Pentru a detensiona relațiile, cele două naționalități sunt obligate să se cunoască și să lege cât mai multe relații de prietenie.

Având în vedere faptul că fiecare britanic poate lega o singură relație de prietenie cu un argentinian, iar relațiile de prietenie se știu deoarece acestea sunt evidente, Margaret Thatcher va solicită ajutorul în aflarea numărului maxim de relații noi de prietenie care se vor lega pe insula .

= Date de intrare =
Fișierul de intrare <code>falklandIN.txt</code> conține pe prima linie numerele <code>n</code>, <code>m</code> și <code>k</code>, reprezentând numărul de britanici, argentinieni și de relații de prietenie ce pot fi legate.

Pe următoarele <code>k</code> linii se află <code>k</code> perechii de numere <code>x</code> <code>y</code> cu semnificația : britanicul <code>x</code> poate lega o relație de prietenie cu argentinianul <code>y</code>.

= Date de ieșire =
Fișierul de ieșire <code>falklandOUT.txt</code> va conține pe prima linie numărul <code>r</code>, reprezentând numărul maxim de relații de prietenie ce pot fi legate pe insula .

= Restricții și precizări =

* <code>1 ≤ n, m ≤ 50.000</code>
* <code>1 ≤ k ≤ 150.000</code>
* <code>1 ≤ x ≤ n</code>
* <code>1 ≤ y ≤ m</code>

= Exemplul 1: =
<code>falklandIN.txt</code>
3 3 5
1 1
1 2
2 2
2 3
3 3
<code>falklandOUT.txt</code>
3

= Exemplul 2: =
<code>falklandIN.txt</code>
100000 100000 100000
1 1
1 2
2 2
2 3
3 3
<code>falklandOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict

def verifica_restrictiile(n, m, k):
if not (1 <= n <= 50000 and 1 <= m <= 50000 and 1 <= k <= 150000):
with open("falklandOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
exit()

def numar_maxim_prieteni(n, m, k, prietenii):
graf = defaultdict(list)

for prietenie in prietenii:
x, y = prietenie
graf[x].append(y)

def dfs(britanic, vizitat, potrivire):
for argentinian in graf[britanic]:
if not vizitat[argentinian]:
vizitat[argentinian] = True

if potrivire[argentinian] == -1 or dfs(potrivire[argentinian], vizitat, potrivire):
potrivire[argentinian] = britanic
return True

return False

def prietenii_maximi():
potrivire = [-1] * (m + 1)
rezultat = 0

for i in range(1, n + 1):
vizitat = [False] * (m + 1)
if dfs(i, vizitat, potrivire):
rezultat += 1

return rezultat

prieteni_maximi = prietenii_maximi()
return prieteni_maximi

# Citirea datelor de intrare
with open("falklandIN.txt", "r") as f:
n, m, k = map(int, f.readline().split())
verifica_restrictiile(n, m, k)
prietenii = [tuple(map(int, f.readline().split())) for _ in range(k)]

# Calcularea rezultatului
rezultat = numar_maxim_prieteni(n, m, k, prietenii)

# Scrierea rezultatului în fișierul de ieșire
with open("falklandOUT.txt", "w") as f:
f.write(str(rezultat))

</syntaxhighlight>

1651 - Graf

2023-12-27T07:28:38Z

Simina: Pagină nouă: = Cerința = Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică. = Date de intrare = Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</co...

= Cerința =
Se dă lista muchiilor unui graf neorientat ponderat. Să se determine vârful pentru care media aritmetică a ponderilor muchiilor incidente este minimă. Dacă există mai multe vârfuri cu aceeași medie minimă, se va afișa vârful numerotat cu o valoare mai mică.

= Date de intrare =
Programul citește de la tastatură numerele <code>n m</code>, reprezentând numărul de vârfuri și numărul de muchii din graf, apoi <code>m</code> triplete <code>i j p</code>, reprezentând muchiile, date prin extremități și pondere.

= Date de ieșire =
Programul va afișa pe ecran numărul <code>vf</code>, reprezentând vârful determinat.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* ponderile muchiilor sunt numere naturale nenule mai mici decât <code>1000</code>
* graful dat nu conține noduri izolate

= Exemplul 1: =
Intrare
5 6
1 2 10
2 3 2
2 5 2
3 5 12
3 4 1
4 5 5
Ieșire
4

=== Explicație ===
Mediile ponderilor muchiilor incidente cu vârfurile grafului sunt:

* pentru vârful <code>1</code> media este <code>10</code>
* pentru vârful <code>2</code> media este <code>4.66667</code>
* pentru vârful <code>3</code> media este <code>5</code>
* pentru vârful <code>4</code> media este <code>3</code>
* pentru vârful <code>5</code> media este <code>6.33333</code>

Astfel media minimă este <code>3</code>, pentru vârful <code>4</code>

== Exemplul 2: ==
<code>Intrare</code>
<code>101</code>
<code>consola</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restricții(n, m, muchii):
# Verificăm restricțiile
if not (1 <= n <= 100) or any(not (1 <= vf1 <= n and 1 <= vf2 <= n) for vf1, vf2, _ in muchii) or any(not (1 <= p < 1000) for _, _, p in muchii):
return False
return True

def gaseste_varf_minim_media_ponderilor(n, m, muchii):
# Initializăm un dicționar pentru a stoca ponderile muchiilor incidente pentru fiecare vârf
ponderi_vf = {i: [] for i in range(1, n + 1)}

# Citim și memorăm ponderile muchiilor în dicționar
for i in range(m):
vf1, vf2, pondera = muchii[i]
ponderi_vf[vf1].append(pondera)
ponderi_vf[vf2].append(pondera)

# Calculăm media aritmetică a ponderilor pentru fiecare vârf
medii_ponderi = {vf: sum(ponderi) / len(ponderi) for vf, ponderi in ponderi_vf.items()}

# Găsim vârful cu media minimă
vf_min_media = min(medii_ponderi, key=medii_ponderi.get)

return vf_min_media

# Citirea numărului de vârfuri
n = int(input("Introduceți numărul de vârfuri "))
if not (1 <= n <= 100):
print("Datele nu corespund restrictiilor impuse")
else:
# Citirea numărului de muchii
m = int(input("Introduceți numărul de muchii: "))

# Citirea muchiilor și ponderilor
print("Introduceți extremitățile și ponderea fiecărei muchii:")
muchii = [tuple(map(int, input().split())) for _ in range(m)]

# Apelarea funcției și afișarea rezultatului
rezultat = gaseste_varf_minim_media_ponderilor(n, m, muchii)
if rezultat is not None:
print(rezultat)

</syntaxhighlight>

3693 – Binary Tree

2023-12-27T06:58:36Z

Simina: Pagină nouă: == Enunț == Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia. = Cerința = Se dau un arbore binar complet infinit cu rădăcina în nodul <code>1</code> în care pentru orice nod <code>i</code> copiii săi sunt nodurile <code>2*i</code>, respectiv <code>2*i+1</code> și <code>Q</code>...

== Enunț ==
Un arbore binar complet este un arbore binar în care toate nivelurile, cu excepția ultimului sunt ocupate în întregime. În general, deși nu este obligatoriu, toate nodurile de pe ultimul nivel sunt grupate în partea stânga a acestuia.

= Cerința =
Se dau un arbore binar complet infinit cu rădăcina în nodul <code>1</code> în care pentru orice nod <code>i</code> copiii săi sunt nodurile <code>2*i</code>, respectiv <code>2*i+1</code> și <code>Q</code> perechi de numere <code>u v</code>. Se cere să se afle pentru fiecare pereche lungimea cel mai scurt drum(ca număr de muchii) dintre nodurile <code>u</code> și <code>v</code> din arbore.

= Date de intrare =
Programul citește de la tastatură numărul <code>Q</code>, iar apoi <code>Q</code> perechi de numere naturale, fiecare pereche pe câte o linie.

= Date de ieșire =
Programul va afișa pe ecran pentru fiecare pereche <code>u v</code> distanța dintre nodurile <code>u</code> și <code>v</code> din arbore.

= Restricții și precizări =

* <code>1 ≤ Q ≤ 100.000</code>
* <code>1 ≤ u, v ≤ 2.000.000.000</code>

= Exemplul 1: =
Intrare
5
1 2
4 5
8 15
11 3
12 14
Ieșire
1
2
6
4
4

=== Explicație ===
Așa arată primele <code>4</code> nivele ale arborelui descris în enunț:

== Exemplul 2: ==
Intrare
100000000
Consola
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(Q, u, v):
if not (1 <= Q <= 100000) or not (1 <= u <= 2000000000) or not (1 <= v <= 2000000000) or u < 0 or v < 0:
print("Datele nu corespund restrictiilor impuse")
exit()

def gaseste_distanta(u, v):
# Funcție pentru a găsi distanța dintre două noduri în arborele binar complet
distanta = 0
while u != v:
# Asigurăm că u este întotdeauna mai mic sau egal decât v
if u > v:
u, v = v, u
v //= 2 # Urmează căutarea pe nivelul anterior pentru v
distanta += 1

return distanta

# Citim numărul de perechi
Q = int(input("Introdu numărul de perechi (Q): "))

# Verificăm restricțiile pentru Q
verificare_restrictii(Q, Q, Q)

valori_u = []
valori_v = []

# Citim și procesăm fiecare pereche
for _ in range(Q):
u, v = map(int, input("Introdu perechea u v: ").split())
valori_u.append(u)
valori_v.append(v)

# Verificăm restricțiile pentru u și v
verificare_restrictii(Q, max(valori_u), max(valori_v))

# Afișăm rezultatele la final
print("\nRezultate:")

for u, v in zip(valori_u, valori_v):
distanta = gaseste_distanta(u, v)
print(f"{distanta}")

</syntaxhighlight>

0647 – Subarbore2

2023-12-26T23:32:51Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>subarbore2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe a doua linie se află vectorul de...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Fiecare nod al arborelui are asociată o valoare numerică întreagă. Determinați suma valorilor asociate nodurilor din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarbore2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe a doua linie se află vectorul de tați al arborelui, valorile fiind separate prin spații. Pe linia a treia se află, în ordine, valorile asociate nodurilor din arbore.

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

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* <code>1 ≤ k ≤ n</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* valorile asociate nodurilor din arbore sunt numere întregi din intervalul <code>[-1000,1000]</code>

= Exemplul 1: =
<code>subarbore2IN.txt</code>
8 4
4 3 0 3 2 1 4 1
-3 -2 4 4 0 -3 3 2
<code>subarbore2OUT.txt</code>
3

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, k):
if not (1 <= n <= 100) or not (1 <= k <= n):
with open('subarbore2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, lista_adiacenta, valori):
suma_subarbore = valori[nod - 1] # Corectarea indexării pentru a evita IndexError
for copil in lista_adiacenta[nod]:
suma_subarbore += dfs(copil, lista_adiacenta, valori)
return suma_subarbore

def main():
# Citirea datelor de intrare
with open('subarbore2IN.txt', 'r') as fisier:
n, k = map(int, fisier.readline().split())

# Verificarea restricțiilor
if not verificare_restrictii(n, k):
return

# Citirea celorlalte date de intrare
with open('subarbore2IN.txt', 'r') as fisier:
fisier.readline() # Trecem peste linia cu n și k
parinti = list(map(int, fisier.readline().split()))
valori = list(map(int, fisier.readline().split()))

# Construirea listei de adiacență
lista_adiacenta = {i: [] for i in range(1, n + 1)}
for i in range(n):
if parinti[i] != 0:
lista_adiacenta[parinti[i]].append(i + 1)

# Calcularea sumei valorilor asociate nodurilor din subarborele cu rădăcina în k
rezultat = dfs(k, lista_adiacenta, valori)

# Scrierea rezultatului în fișierul de ieșire
with open('subarbore2OUT.txt', 'w') as fisier_iesire:
fisier_iesire.write(str(rezultat))

if __name__ == "__main__":
main()

</syntaxhighlight>

0646 – Subarbore1

2023-12-26T23:28:15Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații....

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile terminale din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarbore1IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarbore1OUT.txt</code> va conține pe prima linie nodurile terminale din subarborele cu rădăcina în <code>k</code>, în ordine crescătoare, separate printr-un spațiu.

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarbore1IN.txt</code>
8 4
4 3 0 3 2 1 4 1
<code>subarbore1OUT.txt</code>
6 7 8

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def dfs(nod, lista_adiacenta, rezultat):
# Verificăm dacă nodul este terminal
if nod not in lista_adiacenta:
rezultat.append(nod)
return

# Parcurgem vecinii nodului și aplicăm DFS pe fiecare dintre ei
for vecin in lista_adiacenta[nod]:
dfs(vecin, lista_adiacenta, rezultat)

def verifica_restrictii(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarbore1OUT.txt", 'w') as fisier:
fisier.write("Datele nu corespund restrictiilor impuse")
exit()

def main(fisier_intrare, fisier_iesire):
with open(fisier_intrare, 'r') as fisier:
# Citim numărul de noduri și nodul k
n, k = map(int, fisier.readline().split())

# Verificăm dacă restricțiile sunt respectate
verifica_restrictii(n, k)

# Citim vectorul de tați al arborelui
tati = list(map(int, fisier.readline().split()))

# Construim o listă de adiacență bazată pe vectorul de tați
lista_adiacenta = {}
for i in range(n):
parinte = tati[i]
if parinte not in lista_adiacenta:
lista_adiacenta[parinte] = []
lista_adiacenta[parinte].append(i + 1) # Adăugăm nodul curent ca fiu al nodului părinte

# Aplicăm DFS pentru a identifica nodurile terminale din subarborele cu rădăcina în nodul k
rezultat = []
dfs(k, lista_adiacenta, rezultat)

# Scriem rezultatul în fișierul de ieșire
with open(fisier_iesire, 'w') as fisier:
if not rezultat:
fisier.write("Subarborele nu are noduri terminale")
else:
fisier.write(' '.join(map(str, sorted(rezultat))))

# Exemplu de utilizare
main("subarbore1IN.txt", "subarbore1OUT.txt")

</syntaxhighlight>

0649 – Subarbori

2023-12-26T23:21:46Z

Simina: 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...

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

0648 – Subarbore Numărare

2023-12-26T23:08:11Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați câte noduri conține subarborele cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>subarborenumarareIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de ieșir...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Determinați câte noduri conține subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarborenumarareIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarborenumarareOUT.txt</code> va conține pe prima linie valoarea cerută.

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarborenumarareIN.txt</code>
8 4
4 3 0 3 2 1 4 1
<code>subarborenumarareOUT.txt</code>
5

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def numara_noduri_subarbore(n, k, vector_tati):
relatii = {}

for i in range(1, n + 1):
parinte = vector_tati[i - 1]
if parinte not in relatii:
relatii[parinte] = []
relatii[parinte].append(i)

def numara_noduri_recursiv(nod):
numar_noduri = 1
if nod in relatii:
for copil in relatii[nod]:
numar_noduri += numara_noduri_recursiv(copil)
return numar_noduri

rezultat = numara_noduri_recursiv(k)

return rezultat

def verificare_restricții(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarborenumarareOUT.txt", "w") as f:
f.write("Datele nu corespund restrictiilor impuse")
return False
return True

# Citire date de intrare
with open("subarborenumarareIN.txt", "r") as f:
n, k = map(int, f.readline().split())
vector_tati = list(map(int, f.readline().split()))

# Verificare restricții
if verificare_restricții(n, k):
# Calcul și scriere rezultat în fișierul de ieșire
rezultat = numara_noduri_subarbore(n, k, vector_tati)
with open("subarborenumarareOUT.txt", "w") as f:
f.write(str(rezultat))

</syntaxhighlight>

0641 – Subarbore

2023-12-26T22:58:37Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile din subarborele cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>subarboreIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și un nod <code>k</code>. Afișați, în ordine crescătoare, nodurile din subarborele cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>subarboreIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodul <code>k</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>subarboreOUT.txt</code> va conține pe prima linie nodurile din subarbore, în ordine crescătoare, separate printr-un spațiu.

= Restricții și precizări =

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

= Exemplul 1: =
<code>subarboreIN.txt</code>
7 7
4 1 7 0 7 7 1
<code>subarboreOUT.txt</code>
3 5 6 7

= Exemplul 2: =
<code>subarboreIN.txt</code>
101 2
4 1 7 0 7 7 1
<code>subarboreOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k):
if not (1 <= n <= 100 and 1 <= k <= n):
with open("subarboreOUT.txt", "w") as outfile:
outfile.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, lista_adiacenta, noduri_subarbore):
noduri_subarbore.append(nod)
for copil in lista_adiacenta[nod]:
dfs(copil, lista_adiacenta, noduri_subarbore)

def main():
# Citirea datelor de intrare
with open("subarboreIN.txt", "r") as infile:
n, k = map(int, infile.readline().split())
parinti = list(map(int, infile.readline().split()))

# Verificarea restricțiilor
if not verifica_restrictii(n, k):
return

# Construirea listei de adiacență bazată pe vectorul de tați
lista_adiacenta = {i: [] for i in range(1, n + 1)}
for i in range(1, n + 1):
if parinti[i - 1] != 0:
lista_adiacenta[parinti[i - 1]].append(i)

# Identificarea și colectarea nodurilor din subarbore
noduri_subarbore = []
dfs(k, lista_adiacenta, noduri_subarbore)

# Sortarea și scrierea rezultatelor în fișierul de ieșire
noduri_subarbore.sort()
with open("subarboreOUT.txt", "w") as outfile:
outfile.write(" ".join(map(str, noduri_subarbore)))

if __name__ == "__main__":
main()

</syntaxhighlight>

0640 – NrFii

2023-12-26T22:52:20Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare. = Date de intrare = Fișierul de intrare <code>nrfiiIN.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ț...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

= Date de intrare =
Fișierul de intrare <code>nrfiiIN.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>nrfiiOUT.txt</code> va conține pe prima linie nodurile din arbore cu număr maxim de fii, în ordine crescătoare, separate printr-un spațiu.

= 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: =
<syntaxhighlight lang="python3" line="1">
def citeste_arbore(file_path):
with open(file_path, 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().split()))
return n, tati

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("nrfiiOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False

def determina_noduri_max_fii(n, tati):
fii = [0] * (n + 1)
for tata in tati:
if tata != -1:
fii[tata] += 1

max_fii = max(fii)
noduri_max_fii = [i for i in range(1, n + 1) if fii[i] == max_fii]

return noduri_max_fii

def scrie_rezultat(file_path, noduri_max_fii):
with open(file_path, 'w') as file:
if noduri_max_fii:
file.write(' '.join(map(str, noduri_max_fii)))
else:
file.write("Datele nu corespund restrictiilor impuse")

if __name__ == "__main__":
file_input = "nrfiiIN.txt"
file_output = "nrfiiOUT.txt"

n, tati = citeste_arbore(file_input)

if verificare_restrictii(n):
noduri_max_fii = determina_noduri_max_fii(n, tati)
scrie_rezultat(file_output, noduri_max_fii)

</syntaxhighlight><code>nrfiiIN.txt</code>
7
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
7

= Explicație =
Nodul <code>7</code> are număr maxim de fii, <code>3</code>.

== Exemplul 2: ==
<code>nrfiiIN.txt</code>
101
4 1 7 0 7 7 1
<code>nrfiiOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==

0650 – kNivel

2023-12-26T22:45:49Z

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și o valoare <code>k</code>. Determinați nodurile situate pe nivelul <code>k</code> în arbore. = Date de intrare = Fișierul de intrare <code>knivelIN.txt</code> conține pe prima lin...

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și o valoare <code>k</code>. Determinați nodurile situate pe nivelul <code>k</code> în arbore.

= Date de intrare =
Fișierul de intrare <code>knivelIN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și valoarea <code>k</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>knivelOUT.txt</code> va conține pe prima linie, în ordine crescătoare, nodurile situate pe nivelul <code>k</code> în arbore.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* pe nivelul <code>k</code> va exista cel puțin un nod

= Exemplul 1: =
<code>knivelIN.txt</code>
8 3
4 3 0 3 2 1 2 1
<code>knivelOUT.txt</code>
1 5 7

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verificare_restrictii(n, k):
if 1 <= n <= 100:
return True
else:
return False

def gaseste_noduri_pe_nivel(tati, nivel):
noduri_pe_nivel = []
for i in range(len(tati)):
nivel_nod_curent = 1 # Nivelul rădăcinii
parinte_curent = tati[i]

while parinte_curent != 0:
parinte_curent = tati[parinte_curent - 1]
nivel_nod_curent += 1

if nivel_nod_curent == nivel:
noduri_pe_nivel.append(i + 1)

return noduri_pe_nivel

def main():
# Citirea datelor de intrare din fișier
with open("knivelIN.txt", "r") as fisier_intrare:
n, k = map(int, fisier_intrare.readline().split())
tati = list(map(int, fisier_intrare.readline().split()))

# Verificarea restricțiilor
if not verificare_restrictii(n, k):
with open("knivelOUT.txt", "w") as fisier_iesire:
fisier_iesire.write("Datele nu corespund restrictiilor impuse")
return

# Găsirea nodurilor de pe nivelul k
noduri_pe_nivel_k = gaseste_noduri_pe_nivel(tati, k)

# Scrierea rezultatului în fișierul de ieșire
with open("knivelOUT.txt", "w") as fisier_iesire:
if noduri_pe_nivel_k:
fisier_iesire.write(" ".join(map(str, noduri_pe_nivel_k)))
else:
fisier_iesire.write("Nu există noduri pe nivelul specificat")

if __name__ == "__main__":
main()

</syntaxhighlight>

4159 – Nivele11

2023-12-26T22:36:20Z

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat. = Date de intrare = Fișierul de intrare <code>nivele11IN.txt</code>...

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungime lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Afișați parcurgerea pe nivele a arborelui dat.

= Date de intrare =
Fișierul de intrare <code>nivele11IN.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>nivele11OUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>i-1</code>, separate prin câte un epațiu.

= 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>nivele11IN.txt</code>
8
4 3 0 3 2 1 2 1
<code>nivele11OUT.txt</code>
3
2 4
1 5 7
6 8

= Explicație =
Pe nivelul 0 se află rădăcina, adică nodul 3. Pe nivelul 1 se află nodurile 2 și 4 (descentenții direcți ai rădăcinii). Pe nivelul 2 se află nodurile 1, 5 și 7. Pe ultimul nivel se află nodurile 6 și 8.

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from collections import defaultdict, deque

def verificare_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open('nivele11OUT.txt', 'w') as file:
file.write("Datele nu corespund restrictiilor impuse")
return False

def parcurgere_pe_nivele(n, tati):
if not verificare_restrictii(n):
return []

# Construim lista de adiacență pentru arbore
graf = defaultdict(list)
radacina = -1

for i in range(n):
parinte = tati[i]

if parinte == 0:
radacina = i + 1
else:
graf[parinte].append(i + 1)

# Folosim BFS pentru a parcurge nodurile pe nivele
nivele = []
vizitat = [False] * (n + 1)
queue = deque([(radacina, 0)]) # Rădăcina se află pe nivelul 0

while queue:
nod, nivel = queue.popleft()
if not vizitat[nod]:
vizitat[nod] = True

# Adăugăm nodul la lista corespunzătoare nivelului său
if len(nivele) <= nivel:
nivele.append([])
nivele[nivel].append(nod)

# Adăugăm fiii nodului în coadă cu nivelul actual + 1
for fiu in graf[nod]:
if not vizitat[fiu]:
queue.append((fiu, nivel + 1))

return nivele

# Citim datele din fișierul de intrare
with open('nivele11IN.txt', 'r') as file:
n = int(file.readline().strip())
tati = list(map(int, file.readline().strip().split()))

# Obținem rezultatul
rezultat = parcurgere_pe_nivele(n, tati)

# Dacă rezultatul nu este gol, scriem rezultatul în fișierul de ieșire
if rezultat:
with open('nivele11OUT.txt', 'w') as file:
for nivel in rezultat:
file.write(' '.join(map(str, nivel)) + '\n')

</syntaxhighlight>

4156 – Nivele Pare

2023-12-26T22:29:08Z

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, nivelul unui nod este lungimea lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodurile situate pe nivele pare. = Date de intrare = Fișierul de intrare <code>nivelepareIN.txt</code>...

== Enunț ==
Într-un arbore cu rădăcină, nivelul unui nod este lungimea lanțului de la rădăcină la acel nod. Astfel, rădăcina este pe nivelul <code>0</code>, fiii rădăcinii pe nivelul <code>1</code>, fiii fiilor rădăcinii pe nivelul <code>2</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați nodurile situate pe nivele pare.

= Date de intrare =
Fișierul de intrare <code>nivelepareIN.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>nivelepareOUT.txt</code> va conține mai multe linii. Fiecare linie <code>i</code> conține, în ordine crescătoare, nodurile aflate pe nivelul <code>2*(i-1)</code>.

= 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>nivelepareIN.txt</code>
8
4 3 0 3 2 1 2 1
<code>nivelepareOUT.txt</code>
3
1 5 7

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
return False

def citeste_arbore_din_fisier(file_path):
with open(file_path, 'r') as file:
n = int(file.readline())
if not verifica_restrictii(n):
return None, None, "Datele nu corespund restrictiilor impuse"
parinti = list(map(int, file.readline().split()))
return n, parinti, None

def scrie_noduri_pe_nivele_pare(file_path, nivele_pare):
with open(file_path, 'w') as file:
for nivel in nivele_pare:
file.write(' '.join(map(str, nivel)) + '\n')

def noduri_pe_nivele_pare(n, parinti):
nivele_pare = [[] for _ in range(n)]

for i in range(n):
parinte = parinti[i]
nivel = 0
while parinte != 0:
nivel += 1
parinte = parinti[parinte - 1]

if nivel % 2 == 0:
nivele_pare[nivel // 2].append(i + 1)

return nivele_pare

if __name__ == "__main__":
input_file = "nivelepareIN.txt"
output_file = "nivelepareOUT.txt"

n, parinti, restrictii_msg = citeste_arbore_din_fisier(input_file)

if restrictii_msg:
with open(output_file, 'w') as file:
file.write(restrictii_msg)
else:
nivele_pare = noduri_pe_nivele_pare(n, parinti)
scrie_noduri_pe_nivele_pare(output_file, nivele_pare)

</syntaxhighlight>

0639 – Înălțime

2023-12-26T21:55:31Z

Simina: Pagină nouă: == Enunț == Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui. = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați înălțimea arborelui. = Date de intrare = Fișierul de intrare <code>inaltimeIN.txt</code> con...

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc. Numărul de nivele distincte din arbore determină înălțimea arborelui.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri. Determinați înălțimea arborelui.

= Date de intrare =
Fișierul de intrare <code>inaltimeIN.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>inaltimeOUT.txt</code> va conține pe prima linie numărul <code>H</code> , reprezentând înălțimea arborelui.

= Restricții și precizări =

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

= Exemplu 1: =
<code>inaltimeIN.txt</code>
7
4 1 7 0 7 7 1
<code>inaltimeOUT.txt</code>
4

= Exemplu 2: =
<code>inaltimeIN.txt</code>
101
4 1 7 0 7 7 1
<code>inaltimeOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n):
if 1 <= n <= 100:
return True
else:
with open("inaltimeOUT.txt", "w") as file:
file.write("Datele nu corespund restrictiilor impuse")
return False

def calculeaza_inaltimea(n, tati):
if not verifica_restrictii(n):
return

inaltime = 0
nivele = [0] * n

for i in range(n):
nivel = 0
j = i
while tati[j] != 0:
nivel += 1
j = tati[j] - 1
if nivele[j] != 0:
nivel += nivele[j]
break

nivele[i] = nivel
inaltime = max(inaltime, nivel + 1)

with open("inaltimeOUT.txt", "w") as file:
file.write(str(inaltime))

def main():
# Citirea datelor de intrare
with open("inaltimeIN.txt", "r") as file:
n = int(file.readline())
if not verifica_restrictii(n):
return
tati = list(map(int, file.readline().split()))

# Calcularea inaltimii arborelui
calculeaza_inaltimea(n, tati)

if __name__ == "__main__":
main()

</syntaxhighlight>

2749 – Tată

2023-12-26T21:42:58Z

Simina: Pagină nouă: = Cerința = Se dă un vector <code>t=(t[1], t[2], ..., t[n])</code> care memorează numere naturale cuprinse între <code>0</code> și <code>n</code>. Să se verifice dacă <code>t</code> este sau nu vector de tați asociat unui arbore cu rădăcină. = Date de intrare = Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale, separate prin spații. = Date de ieșire = Programul va afișa pe ecran mesajul <code>DA</code>, dacă...

= Cerința =
Se dă un vector <code>t=(t[1], t[2], ..., t[n])</code> care memorează numere naturale cuprinse între <code>0</code> și <code>n</code>. Să se verifice dacă <code>t</code> este sau nu vector de tați asociat unui arbore cu rădăcină.

= Date de intrare =
Programul citește de la tastatură numărul <code>n</code>, iar apoi <code>n</code> numere naturale, separate prin spații.

= Date de ieșire =
Programul va afișa pe ecran mesajul <code>DA</code>, dacă <code>t</code> este vector de tați, sau mesajul <code>NU</code> în caz contrar.

= Restricții și precizări =

* <code>1 ≤ n ≤ 100.000</code>
* <code>0 ≤ t[i] ≤ n</code>

= Exemplul 1: =
Intrare
5
0 1 1 3 3
Ieșire
DA

= Exemplul 2: =
Intrare
5
2 0 2 5 4
Ieșire
NU

=== Explicație ===
Nodul <code>4</code> are ca tată pe <code>5</code>, iar nodul <code>5</code> are ca tată pe <code>4</code>

== Exemplul 3: ==
Intrare
100001
Consola
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
def sunt_restrictii_incorecte(n, t):
# Verifică restricțiile pentru n
if not (1 <= n <= 100000):
return True

# Verifică restricțiile pentru t[i]
for i in range(n):
if not (0 <= t[i] <= n):
return True

return False

def este_vector_de_tati(t):
n = len(t)

# Verifică dacă restricțiile sunt respectate
if sunt_restrictii_incorecte(n, t):
return False

# Verifică dacă rădăcina arborelui este corectă
if t[0] != 0:
return False

# Verifică dacă fiecare element al vectorului este un index valid
for i in range(1, n):
if not (0 <= t[i] < n):
return False

return True

# Citeste numarul n
n = int(input("Introduceti numarul n: "))

# Ieși din program dacă restricțiile pentru n nu sunt respectate
if n < 1 or n > 100000:
print("Datele nu corespund restrictiilor impuse")
else:
# Citeste vectorul t
t = list(map(int, input("Introduceti vectorul t: ").split()))

# Verifica daca restrictiile sunt respectate si afiseaza mesajul corespunzator
if sunt_restrictii_incorecte(n, t):
print("Datele nu corespund restrictiilor impuse")
else:
# Verifica daca t este vector de tati si afiseaza rezultatul
if este_vector_de_tati(t):
print("DA")
else:
print("NU")

</syntaxhighlight>

4167 – FlșiElimină

2023-12-26T21:35:59Z

Simina:

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:
struct Nod
{
int info;
Nod *leg;
};
în care câmpul <code>info</code> memorează un număr întreg, iar câmpul <code>leg</code> memorează adresa următorului element al listei.

= Cerinţa =
Să se scrie o funcție C++ cu următorul prototip:
void FLsiElimina(Nod * &head);
care, în lista pentru care primul element are adresa memorată în pointerul <code>head</code>, elimină toate nodurile cuprinse între cel mai din stânga nod care memorează un număr divizibil cu <code>3</code> și cel mai din dreapta nod care memorează un număr divizibil cu <code>3</code>, inclusiv acestea. Se garantează că lista va conține cel puțin două noduri care au informația divizibilă cu <code>3</code>. Dacă se elimină toate nodurile, atunci după apelul funcției trebuie ca <code>head = NULL</code>. De exemplu, dacă lista conține inițial informațiile <code>1,27,3,4,13,12,44,23</code>, atunci la final lista va fi: <code>1,44,23</code>.

= Important =
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

== Rezolvare ==
<syntaxhighlight lang="python3">
class Nod:
def __init__(self, info):
self.info = info
self.leg = None

def FLsiElimina(head):
# Cautăm primul nod cu informația divizibilă cu 3
primul_nod = None
nod_curent = head

while nod_curent is not None and nod_curent.info % 3 != 0:
primul_nod = nod_curent
nod_curent = nod_curent.leg

# Cautăm ultimul nod cu informația divizibilă cu 3
ultimul_nod = None
nod_curent = head
while nod_curent is not None:
if nod_curent.info % 3 == 0:
ultimul_nod = nod_curent
nod_curent = nod_curent.leg

# Eliminăm nodurile cuprinse între primul_nod și ultimul_nod, inclusiv acestea
nod_curent = head
while nod_curent is not None and nod_curent != primul_nod:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

if primul_nod is not None:
primul_nod.leg = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator
else:
# Dacă primul_nod este None, eliminăm toate nodurile de la început până la ultimul_nod
head = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

return head

# Funcție de afișare a listei
def afisare_lista(head):
while head is not None:
print(head.info, end=" ")
head = head.leg
print()

head = Nod(1)
head.leg = Nod(27)
head.leg.leg = Nod(3)
head.leg.leg.leg = Nod(4)
head.leg.leg.leg.leg = Nod(13)
head.leg.leg.leg.leg.leg = Nod(12)
head.leg.leg.leg.leg.leg.leg = Nod(44)
head.leg.leg.leg.leg.leg.leg.leg = Nod(23)

print("Lista initiala:", end=" ")
afisare_lista(head)

head = FLsiElimina(head)

print("Lista finala:", end=" ")
afisare_lista(head)

</syntaxhighlight>

0636 – Arbore

2023-12-26T21:35:38Z

Simina:

= Cerința =
Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui.

= Date de ieșire =
Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-un spațiu.

= Restricții și precizări =

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

= Exemplul 1 : =
<code>arboreIN.txt</code>
7 4
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
4 1 7 0 7 7 1

= Exemplul 2 : =
<code>arboreIN.txt</code>
1000 1001
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
Datele nu corespund restrictiilor impuse

== Rezolvare ==
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k, muchii):
if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
# Verifică dacă nodurile din muchii sunt în intervalul corect
for muchie in muchii:
if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, parinte, graf, rezultat):
rezultat[nod] = parinte
for vecin in graf[nod]:
if vecin != parinte:
dfs(vecin, nod, graf, rezultat)

def main():
# Citirea datelor de intrare
with open("arboreIN.txt", "r") as file_in:
n, k = map(int, file_in.readline().split())
muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]

# Verificarea restricțiilor
if not verifica_restrictii(n, k, muchii):
return

# Construirea grafului
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])

# Inițializarea vectorului de tați cu 0
parinti = [0] * (n + 1)

# Apelarea algoritmului DFS
dfs(k, 0, graf, parinti)

# Scrierea rezultatului în fișierul de ieșire
with open("arboreOUT.txt", "w") as file_out:
file_out.write(" ".join(map(str, parinti[1:])))

if __name__ == "__main__":
main()

</syntaxhighlight>

0652 – Afișare Fii

2023-12-26T21:35:18Z

Simina:

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri distincte din arbore. Afișați fiii fiecăruia dintre cele <code>k</code> noduri.

= Date de intrare =
Fișierul de intrare <code>afisarefiiIN.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. Linia a trei conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>afisarefiiOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține numărul de fii ai lui <code>x[i]</code> urmat de un spațiu și de lista fiilor lui <code>x[i]</code>, separați și ei printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* dacă un nod <code>x[i]</code> nu are fii, linia corespunzătoare din fișierul de ieșire va contine doar valoarea <code>0</code>

= Exemplul 1: =
<code>afisarefiiIN.txt</code>
8
4 3 0 3 2 1 2 1
4
3 4 7 1
<code>afisarefiiOUT.txt</code>
2 2 4
1 1
0
2 6 8

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

== Rezolvare ==
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k):
if not (1 <= k <= n <= 100):
return "Datele nu corespund restrictiilor impuse"
return None

def afisare_fii(n, tati, k, noduri_selectate):
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
return restrictii_mesaj

rezultat = []

for nod in noduri_selectate:
if not (1 <= nod <= n):
return "Datele nu corespund restrictiilor impuse"

fii = [i for i, parinte in enumerate(tati, 1) if parinte == nod]
rezultat.append((len(fii), fii))

return rezultat

# Citirea datelor de intrare
with open("afisarefiiIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().strip().split()))
k = int(f.readline().strip())
noduri_selectate = list(map(int, f.readline().strip().split()))

# Verificarea restricțiilor și obținerea rezultatului
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
with open("afisarefiiOUT.txt", "w") as f:
f.write(restrictii_mesaj)
else:
rezultat = afisare_fii(n, tati, k, noduri_selectate)
with open("afisarefiiOUT.txt", "w") as f:
if isinstance(rezultat, str):
f.write(rezultat)
else:
for nr_fii, fii in rezultat:
f.write(f"{nr_fii} {' '.join(map(str, fii))}\n")

</syntaxhighlight>

0638 – Nivele

2023-12-26T21:34:36Z

== Enunț ==
Într-un arbore cu rădăcină, spunem că rădăcina este pe nivelul <code>1</code>, fiii rădăcinii pe nivelul <code>2</code>, fiii fiilor rădăcinii pe nivelul <code>3</code>, etc.

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri din arbore. Determinați pentru fiecare dintre cele <code>k</code> noduri nivelul pe care se află.

= Date de intrare =
Fișierul de intrare <code>niveleIN.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. Linia a treia conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>niveleOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține nivelul pe care se află nodul <code>x[i]</code> în arborele dat

= Restricții și precizări =

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

= Exemplul 1: =
<code>niveleIN.txt</code>
7
4 1 7 0 7 7 1
4
1 3 4 7
<code>niveleOUT.txt</code>
2
4
1
3

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

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verifica_restrictii(n, k, tati):
if not(1 <= k <= n <= 100) or tati.count(0) != 1:
with open("niveleOUT.txt", "w") as f_out:
f_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def determina_nivelul(n, tati, k, noduri):
# Verificare pentru restricții
if not verifica_restrictii(n, k, tati):
return

nivele = [0] * n # nivelele pentru fiecare nod
radacina = tati.index(0) + 1 # găsim poziția rădăcinii în vectorul de tați

def dfs(nod, nivel):
nivele[nod - 1] = nivel # nodurile sunt numerotate de la 1, așa că indexăm cu nod-1
for fiu in range(1, n + 1):
if tati[fiu - 1] == nod:
dfs(fiu, nivel + 1)

dfs(radacina, 1)

rezultate = [nivele[nod - 1] for nod in noduri]

# Scrierea rezultatelor în fișierul de ieșire
with open("niveleOUT.txt", "w") as f_out:
for rezultat in rezultate:
f_out.write(str(rezultat) + "\n")

# Citirea datelor de intrare
with open("niveleIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().split()))
k = int(f.readline().strip())
noduri = list(map(int, f.readline().split()))

# Determinarea nivelului pentru fiecare nod dat
determina_nivelul(n, tati, k, noduri)

</syntaxhighlight>

0652 – Afișare Fii

2023-12-26T21:29:55Z

Simina: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri distincte din arbore. Afișați fiii fiecăruia dintre cele <code>k</code> noduri. = Date de intrare = Fișierul de intrare <code>afisarefiiIN.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. Linia a trei conține numărul <code>k</code>, i...

= Cerința =
Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și <code>k</code> noduri distincte din arbore. Afișați fiii fiecăruia dintre cele <code>k</code> noduri.

= Date de intrare =
Fișierul de intrare <code>afisarefiiIN.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. Linia a trei conține numărul <code>k</code>, iar linia a patra <code>k</code> noduri, <code>x[1]</code>, <code>x[2]</code>, … , <code>x[k]</code>.

= Date de ieșire =
Fișierul de ieșire <code>afisarefiiOUT.txt</code> va conține <code>k</code> linii. Linia <code>i</code> va conține numărul de fii ai lui <code>x[i]</code> urmat de un spațiu și de lista fiilor lui <code>x[i]</code>, separați și ei printr-un spațiu.

= Restricții și precizări =

* <code>1 ≤ k ≤ n ≤ 100</code>
* în vectorul de tați rădăcina este marcată cu <code>0</code>
* dacă un nod <code>x[i]</code> nu are fii, linia corespunzătoare din fișierul de ieșire va contine doar valoarea <code>0</code>

= Exemplul 1: =
<code>afisarefiiIN.txt</code>
8
4 3 0 3 2 1 2 1
4
3 4 7 1
<code>afisarefiiOUT.txt</code>
2 2 4
1 1
0
2 6 8

= Exemplul 2: =
<code>afisarefiiIN.txt</code>
101
4 3 0 3 2 1 2 1
4
3 4 7 1
<code>afisarefiiOUT.txt</code>
Datele nu corespund restrictiilor impuse
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k):
if not (1 <= k <= n <= 100):
return "Datele nu corespund restrictiilor impuse"
return None

def afisare_fii(n, tati, k, noduri_selectate):
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
return restrictii_mesaj

rezultat = []

for nod in noduri_selectate:
if not (1 <= nod <= n):
return "Datele nu corespund restrictiilor impuse"

fii = [i for i, parinte in enumerate(tati, 1) if parinte == nod]
rezultat.append((len(fii), fii))

return rezultat

# Citirea datelor de intrare
with open("afisarefiiIN.txt", "r") as f:
n = int(f.readline().strip())
tati = list(map(int, f.readline().strip().split()))
k = int(f.readline().strip())
noduri_selectate = list(map(int, f.readline().strip().split()))

# Verificarea restricțiilor și obținerea rezultatului
restrictii_mesaj = verifica_restrictii(n, k)
if restrictii_mesaj:
with open("afisarefiiOUT.txt", "w") as f:
f.write(restrictii_mesaj)
else:
rezultat = afisare_fii(n, tati, k, noduri_selectate)
with open("afisarefiiOUT.txt", "w") as f:
if isinstance(rezultat, str):
f.write(rezultat)
else:
for nr_fii, fii in rezultat:
f.write(f"{nr_fii} {' '.join(map(str, fii))}\n")

</syntaxhighlight>

0636 – Arbore

2023-12-26T21:24:40Z

Simina: Pagină nouă: = Cerința = Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>. = Date de intrare = Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui. = Date de ieșire = Fișierul de ieșire <code>arb...

= Cerința =
Se dau cele <code>n-1</code> muchii ale unui arbore cu <code>n</code> noduri și un nod <code>k</code> . Afișați vectorul de tați al arborelui cu rădăcina în <code>k</code>.

= Date de intrare =
Fișierul de intrare <code>arboreIN.txt</code> conține pe prima linie numerele <code>n k</code>, Următoarele <code>n-1</code> linii vor conține câte o pereche <code>i j</code>, reprezentând muchiile arborelui.

= Date de ieșire =
Fișierul de ieșire <code>arboreOUT.txt</code> va conține pe prima linie elementele vectorului de tați al arborelui cu rădăcina în <code>k</code>, separate printr-un spațiu.

= Restricții și precizări =

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

= Exemplul 1 : =
<code>arboreIN.txt</code>
7 4
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
4 1 7 0 7 7 1

= Exemplul 2 : =
<code>arboreIN.txt</code>
1000 1001
1 2
1 4
1 7
3 7
5 7
6 7
<code>arboreOUT.txt</code>
Datele nu corespund restrictiilor impuse
<syntaxhighlight lang="python3">
def verifica_restrictii(n, k, muchii):
if not (1 <= n <= 100) or not (1 <= k <= n) or len(muchii) != n - 1:
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
# Verifică dacă nodurile din muchii sunt în intervalul corect
for muchie in muchii:
if not (1 <= muchie[0] <= n) or not (1 <= muchie[1] <= n):
with open("arboreOUT.txt", "w") as file_out:
file_out.write("Datele nu corespund restrictiilor impuse")
return False
return True

def dfs(nod, parinte, graf, rezultat):
rezultat[nod] = parinte
for vecin in graf[nod]:
if vecin != parinte:
dfs(vecin, nod, graf, rezultat)

def main():
# Citirea datelor de intrare
with open("arboreIN.txt", "r") as file_in:
n, k = map(int, file_in.readline().split())
muchii = [tuple(map(int, file_in.readline().split())) for _ in range(n - 1)]

# Verificarea restricțiilor
if not verifica_restrictii(n, k, muchii):
return

# Construirea grafului
graf = {i: [] for i in range(1, n + 1)}
for muchie in muchii:
graf[muchie[0]].append(muchie[1])
graf[muchie[1]].append(muchie[0])

# Inițializarea vectorului de tați cu 0
parinti = [0] * (n + 1)

# Apelarea algoritmului DFS
dfs(k, 0, graf, parinti)

# Scrierea rezultatului în fișierul de ieșire
with open("arboreOUT.txt", "w") as file_out:
file_out.write(" ".join(map(str, parinti[1:])))

if __name__ == "__main__":
main()

</syntaxhighlight>

4167 – FlșiElimină

2023-12-26T21:12:23Z

Simina: Pagină nouă: Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos: struct Nod { int info; Nod *leg; }; în care câmpul <code>info</code> memorează un număr întreg, iar câmpul <code>leg</code> memorează adresa următorului element al listei. = Cerinţa = Să se scrie o funcție C++ cu următorul prototip: void FLsiElimina(Nod * &head); care, în lista pentru care primul element are adresa memorată...

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:
struct Nod
{
int info;
Nod *leg;
};
în care câmpul <code>info</code> memorează un număr întreg, iar câmpul <code>leg</code> memorează adresa următorului element al listei.

= Cerinţa =
Să se scrie o funcție C++ cu următorul prototip:
void FLsiElimina(Nod * &head);
care, în lista pentru care primul element are adresa memorată în pointerul <code>head</code>, elimină toate nodurile cuprinse între cel mai din stânga nod care memorează un număr divizibil cu <code>3</code> și cel mai din dreapta nod care memorează un număr divizibil cu <code>3</code>, inclusiv acestea. Se garantează că lista va conține cel puțin două noduri care au informația divizibilă cu <code>3</code>. Dacă se elimină toate nodurile, atunci după apelul funcției trebuie ca <code>head = NULL</code>. De exemplu, dacă lista conține inițial informațiile <code>1,27,3,4,13,12,44,23</code>, atunci la final lista va fi: <code>1,44,23</code>.

= Important =
Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.<syntaxhighlight lang="python3">
class Nod:
def __init__(self, info):
self.info = info
self.leg = None

def FLsiElimina(head):
# Cautăm primul nod cu informația divizibilă cu 3
primul_nod = None
nod_curent = head

while nod_curent is not None and nod_curent.info % 3 != 0:
primul_nod = nod_curent
nod_curent = nod_curent.leg

# Cautăm ultimul nod cu informația divizibilă cu 3
ultimul_nod = None
nod_curent = head
while nod_curent is not None:
if nod_curent.info % 3 == 0:
ultimul_nod = nod_curent
nod_curent = nod_curent.leg

# Eliminăm nodurile cuprinse între primul_nod și ultimul_nod, inclusiv acestea
nod_curent = head
while nod_curent is not None and nod_curent != primul_nod:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

if primul_nod is not None:
primul_nod.leg = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator
else:
# Dacă primul_nod este None, eliminăm toate nodurile de la început până la ultimul_nod
head = ultimul_nod.leg
nod_curent = ultimul_nod.leg
while nod_curent is not None:
nod_urmator = nod_curent.leg
del nod_curent
nod_curent = nod_urmator

return head

# Funcție de afișare a listei
def afisare_lista(head):
while head is not None:
print(head.info, end=" ")
head = head.leg
print()

head = Nod(1)
head.leg = Nod(27)
head.leg.leg = Nod(3)
head.leg.leg.leg = Nod(4)
head.leg.leg.leg.leg = Nod(13)
head.leg.leg.leg.leg.leg = Nod(12)
head.leg.leg.leg.leg.leg.leg = Nod(44)
head.leg.leg.leg.leg.leg.leg.leg = Nod(23)

print("Lista initiala:", end=" ")
afisare_lista(head)

head = FLsiElimina(head)

print("Lista finala:", end=" ")
afisare_lista(head)

</syntaxhighlight>