Page 119 - MATINF Nr. 11-12

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 119

Clasele a XI-a si a XII-a
,

I 146 (diagonala). Se d˘a o matrice p˘atratic˘a A de dimensiune n cu numere naturale.
n
Determinat , i elementele diagonalei principale din matricea A .
Cerint , ˘
a
Cunoscˆand n s , i elementele matricei A, se cere s˘ se determine elementele diagonalei principale
a
n
din A .
Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 10.
• Numerele din matrice sunt numere naturale ≤ 100.

Date de intrare
Fis , ierul diagonala.in cont , ine pe prima linie n, apoi elementele matricei, linii dup˘ linii, pe
a
fiecare linie numerele sunt separate prin cˆate un spat , iu.

Date de ie¸sire
Fis , ierul de ies , ire diagonala.out va cont , ine pe prima linie elementele diagonalei principale
separate prin cˆate un spat , iu.

Exemplu
diagonala.in diagonala.out Explicat , ie
2 24 56 Matricea din fis , ier la puterea a doua este:
2 5 24 40
4 6 32 56

Timp maxim de execut , ie: 0.1 secund˘a/test.
Memorie total˘ disponibil˘ 2 MB.
a
a
Ion Alexandru Popescu, Bucures , ti
I 147 (grhamilton). Se d˘a un graf neorientat ponderat prin n num˘arul de noduri, m num˘arul
a
de muchii s , i triplete de forma i, j, cost, unde cost este costul muchiei [i, j]. Se cere s˘ se verifice
dac˘a graful este hamiltonian s , i ˆın caz afirmativ s˘a se determine un ciclu hamiltonian de cost
minim.
Restrict , ii s , i preciz˘ari

• 3 ≤ n ≤ 20.
Date de intrare
Fis , ierul grhamilton.in cont , ine pe prima linie n s , i m separate prin spat , iu s , i pe urm˘atoarele
m linii triplete de forma i j cost, unde cost este costul muchiei [i, j].

Date de ie¸sire
Fis , ierul de ies , ire grhamilton.out va cont , ine pe prima linie DA – dac˘ graful este hamiltonian,
a
NU – dac˘a graful nu este hamiltonian. Dac˘a r˘aspunsul este DA, atunci pe linia a doua se va
scrie un ciclu hamiltonian de cost minim.