Page 170 - MATINF Nr. 1
P. 170
˘
170 PROBLEME DE INFORMATICA PENTRU CONCURSURI
Date de intrare
Fis , ierul de intrare case.in cont , ine pe prima linie un num˘ar natural p. Pentru toate testele de
intrare, num˘arul p poate avea doar valoarea 1 sau 2.
Pe linia a doua se afl˘a n s , i k, pe linia a treia se afl˘a n perechi de numere, una dup˘a alta,
separate prin cˆate un spat , iu, perechi de forma abscis˘a ordonat˘a, reprezentˆand coordonatele
caselor, iar pe linia a patra se afl˘a k triplete de forma abscis˘a ordonat˘a lungime, separate ˆıntre
ele prin spat , ii, reprezentˆand coordonatele colt , ului din stˆanga-jos s , i lungimea suprafet , ei satelor.
Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire case.out se va scrie un singur num˘ar natural reprezentˆand
num˘arul de case care nu fac parte din niciun sat.
Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire case.out se vor scrie, separate prin cˆate un spat , iu, numerele
de case ce vor face parte din sistemul de canalizare al fiec˘arui sat i, i = 1, 2, . . . , k.
Restrict , ii s , i preciz˘ari
• 1 ≤ n ≤ 1000
• 1 ≤ k ≤ 10
• Pentru rezolvarea corect˘a a cerint , ei 1 se acord˘a 20% din punctaj
• Coordonatele caselor sunt numere naturale mai mici sau egale cu 10 9
• O cas˘a dac˘a se g˘ases , te pe un segment al sistemului de canalizare ˆınseamn˘a c˘a face parte
din acest sistem
• O cas˘a aflat˘a chiar pe frontiera satului se presupune c˘a face parte din sat
• Satele sunt disjuncte, adic˘a nu au interior sau frontier˘a comun˘a
Exemple
case.in case.out Explicat , ie
1 1 p = 1
7 1 Avem casele cu coordonatele:
6 10 8 0 20 0 2 5 4 5 4 0 6 0 C 1 (6, 10), C 2 (8, 0), C 3 (20, 0),
2 0 10 C 4 (2, 5), C 5 (4, 5), C 6 (4, 0), C 7 (6, 0)
s , i un singur sat cu suprafat , a
p˘atratic˘a avˆand colt , ul din stˆanga-
jos de coordonate (2, 0) s , i latura de
lungime 10.
C 3 este singura cas˘a care nu face
parte din sat.
