Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri și un nod `k`. Determinați drumul de la nodul `k` la rădăcina arborelui. = Date de intrare = Fișierul de intrare `detdrumIN.txt` conține pe prima linie numărul de noduri `n` și nodul `k`. 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...

2024-01-02T21:28:54Z

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 drumul de la nodul <code>k</code> la rădăcina arborelui. = Date de intrare = Fișierul de intrare <code>detdrumIN.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...

New page

= 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 drumul de la nodul <code>k</code> la rădăcina arborelui.

= Date de intrare =
Fișierul de intrare <code>detdrumIN.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>detdrumOUT.txt</code> va conține pe prima linie nodurile care alcătuiesc drumul determinat, 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 ==
detdrumIN.txt:

7 2

4 1 7 0 7 7 1

detdrumOUT.txt:

2 1 4

== Exemplul 2 ==
detdrumIN.txt:

101 2

4 1 7 0 7 7 1

detdrumOUT.txt:

Invalid input. Constraints not satisfied.

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def verify_constraints(n, k):
return 1 <= n <= 100 and 1 <= k <= n

def solve_detdrum(n, k, t):
a = [0] * 101
rad = 0

for i in range(1, n + 1):
if t[i - 1] == 0:
rad = i
a[i] = t[i - 1]

result = []

def afis(x, a):
nonlocal result
if x != 0 and t[x - 1]:
result.append(x)
afis(t[x - 1], a)

afis(k, a)
result.append(rad)
return result

if __name__ == "__main__":
with open("detdrumIN.txt", "r") as infile, open("detdrumOUT.txt", "w") as outfile:
n, k = map(int, infile.readline().split())

if not verify_constraints(n, k):
outfile.write("Invalid input. Constraints not satisfied.")
else:
t = list(map(int, infile.readline().split()))

result = solve_detdrum(n, k, t)

outfile.write(" ".join(map(str, result)))

</syntaxhighlight>

0642 – Det Drum - Revision history