Page 157 - MATINF Nr. 13-14

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 157

Date de intrare
Fis , ierul nrsubm.in cont , ine pe prima linie n, iar pe linia a doua n numere separate prin
cˆate un spat , iu.

Date de ies , ire
Fis , ierul de ies , ire nrsubm.out va cont , ine pe prima linie elementele lui A, separate prin cˆate
un spat , iu, s , i pe linia a doua num˘arul de submult , imi cu proprietatea din enunt , .
Exemplu

nrsubm.in nrsubm.out Explicat , ie
a
5 1 56 200 8 56 apare de dou˘ ori, deci:
1 56 200 56 8 4 A = {1, 56, 200, 8}, Max = 200, Min = 1.
Se pot forma 4 submult , imi:
{1, 200}, {1, 200, 56}, {1, 200, 8}, {1, 200, 56, 8}.
Doru Constantin, Pites , ti

I 165 (frunze). Se d˘a un arbore cu n noduri prin vectorul tata t, cu nodurile etichetate cu
ˆ
1, 2, . . . , n. In fiecare nod se afl˘ cˆate un num˘ar, nodul i are asociat num˘arul x i , i = 1, 2, . . . , n.
a
Pentru un lant , ˆın arbore definim suma sa ca fiind suma numerelor din nodurile lui. Dorim s˘a
a
determin˘am cea mai mare s , i cea mai mic˘ sum˘a, notate cu Max s , i Min, pentru lant , urile care
au capetele ˆın frunze diferite.
Cerint , ˘
a
Cunoscˆand n, vectorii t s , i x, determinat , i Max s , i Min.

Restrict , ii s , i preciz˘ari

1. 1 ≤ n ≤ 1000.
2. 1 ≤ x i ≤ 100, i = 1, 2, . . . , n.

Date de intrare
Fis , ierul frunze.in cont , ine pe prima linie n, pe linia a doua sunt elementele lui t separate
prin cˆate un spat , iu, iar pe linia a treia elementele lui x, separate prin cˆate un spat , iu.

Date de ies , ire
Fis , ierul de ies , ire frunze.out va cont , ine Max s , i Min, separate printr-un spat , iu.
Exemplu

frunze.in frunze.out Explicat , ie
5 160 80 Lant , ul [1, 5, 3] are suma cea mai mare,
5 4 5 0 4 Max = 100 + 20 + 40 = 160.
100 10 40 10 20 Lant , ul [3, 5, 4, 2] are suma cea mai mic˘a,
Min = 40 + 20 + 10 + 10 = 80.
Doru Anastasiu Popescu, Pites , ti