Page 19 - MATINF Nr. 1

Concursul de Informatic˘a Programming Day 19

ˆ
In acest caz,ˆın fis , ierul de ies , ire grupuri.out se va scrie un singur num˘ar natural reprezentˆand
valoarea maxim˘a a num˘arului total de situat , ii de ajutor reciproc ˆıntr-un grup.

Restrict , ii s , i preciz˘ari

• 1≤N≤500

• 1≤M≤100000

• Pentru rezolvarea corect˘a a fiec˘arei cerint , e se acord˘a 50% din punctaj

Exemple
grupuri.in grupuri.out Explicat , ie
1 2 p = 1
5 3 Elevii sunt ˆımp˘art , it , i ˆın dou˘a grupuri:
1 4 5 Grupul 1 cu elevii 1 s , i 4;
2 3 10 Grupul 2 cu elevii 2, 3, 5.
3 5 15
grupuri.in grupuri.out Explicat , ie
2 25 p = 2
5 3 Elevii sunt ˆımp˘art , it , i ˆın dou˘a grupuri:
1 4 5 Grupul 1 cu elevii 1 s , i 4 (total situatii de ajutor reciproc:
2 3 10 5);
3 5 15 Grupul 2 cu elevii 2, 3, 5 (total situat , ii de ajutor reciproc:
10+15=25).
Valoarea cea mai mare este 25.
Timp maxim de execut , ie: 0.1 secunde/test.

Memorie total˘a disponibil˘a 8 MB, din care 2 MB pentru stiv˘a.
Doru Constantin, Costel B˘alc˘au, Pites , ti, Gabriel Boroghin˘a, Bucures , ti

Solut , ie
Cerint , a 1
Se construies , te un graf neorientat ponderat ˆın care nodurile sunt elevii, iar o muchie are costul
egal cu num˘arul de situat , ii ˆın care elevii asociat , i s-au ajutat reciproc. Pentru acest graf se
determin˘a num˘arul de componente conexe.

Cerint , a 2
Se construies , te un graf neorientat ponderat ˆın care nodurile sunt elevii, iar o muchie are costul
egal cu num˘arul de situat , ii ˆın care elevii asociat , i s-au ajutat reciproc. Pentru acest graf se

determin˘a componentele conexe: C 1 , C 2 , . . . , C k . Apoi pentru fiecare component˘a conex˘a C i
se determin˘a ˆın x i suma total˘a a costurilor muchiilor ei. Valoarea maxim˘a din vectorul x este
num˘arul c˘autat.

Concursul de programare a robotilor LEGO
,
La acest concurs a fost propus˘a urm˘atoarea problem˘a.

Problema – robotic˘a
Punctaj maxim 120+20=140 puncte