Corjuc Eunice: Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu `n` noduri și doua noduri `p q`. Determinați drumul elementar de la nodul `p` la nodul `q`. = Date de intrare = Fișierul de intrare `detdrum2IN.txt` conține pe prima linie numărul de noduri `n` și nodurile `p q`. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date de ie...

2024-01-03T15:04:41Z

Pagină nouă: = Cerința = Se dă vectorul de tați al unui arbore cu rădăcină cu <code>n</code> noduri și doua noduri <code>p q</code>. Determinați drumul elementar de la nodul <code>p</code> la nodul <code>q</code>. = Date de intrare = Fișierul de intrare <code>detdrum2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodurile <code>p q</code>. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. = Date 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 doua noduri <code>p q</code>. Determinați drumul elementar de la nodul <code>p</code> la nodul <code>q</code>.

= Date de intrare =
Fișierul de intrare <code>detdrum2IN.txt</code> conține pe prima linie numărul de noduri <code>n</code> și nodurile <code>p q</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>detdrum2OUT.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 ==
detdrum2IN.txt:

7 2 5

4 1 7 0 7 7 1

detdrum2OUT.txt:

2 1 7 5

== Exemplul 2 ==
detdrum2IN.txt:

101 2 5

4 1 7 0 7 7 1

Output:

Error: n should be between 1 and 100 (inclusive).

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
def validate_input(n, k):
if not (1 <= n <= 100):
print("Error: n should be between 1 and 100 (inclusive).")
return False
if not (1 <= k <= n):
print("Error: k should be between 1 and n (inclusive).")
return False
return True

with open("detdrum2IN.txt", "r") as infile:
n, p, q = map(int, infile.readline().split())
t = [0] + list(map(int, infile.readline().split()))
if not validate_input(n, p) or not validate_input(n, q):
exit()

v1, v2 = [], []

def afis(x, b):
if x != 0 and t[x] != 0:
b.append(x)
afis(t[x], b)

ok1, ok2 = 0, 0
afis(p, v1)
afis(q, v2)
nr1, nr2 = len(v1), len(v2)

for i in range(1, nr1 + 1):
for j in range(1, nr2 + 1):
if v1[i - 1] == v2[j - 1]:
ok1 = i
ok2 = j
break
with open("detdrum2OUT.txt", "w") as outfile:
for i in range(0, ok1):
outfile.write(f"{v1[i]} ")

for i in range(ok2 - 2, -1, -1):
outfile.write(f"{v2[i]} ")

</syntaxhighlight>

0644 – Det Drum2 - Revision history