Page 150 - MATINF Nr. 1

˘
150 PROBLEME DE INFORMATICA PENTRU CONCURSURI

˘
PROBLEME DE INFORMATICA PENTRU
CONCURSURI

Probleme propuse

Clasa a IX-a

I 1 (becuatii). Tic˘a s , i Ionic˘a sunt buni prieteni, pasionat , i de dou˘a lucruri: matematic˘a s , i
informatic˘a. Aces , tia particip˘a la un concurs de propun˘atori de probleme pe echipe. Pentru a
avea succes Tic˘a vrea s˘a propun˘a o problem˘a cu ecuat , ii, iar Ionic˘a o problem˘a cu mult , imi. Dup˘a
consult˘ari repetate se decid s˘a participe la concurs cu o problem˘a care foloses , te atˆat ecuat , ii cˆat s , i
ˆ
2
2
mult , imi. In aceast˘a problem˘a se dau N ecuat , ii de forma x = A i + y , 1 ≤ i ≤ N, s , i se noteaz˘a
2
2
cu S i mult , imea solut , iilor celei de-a i-a ecuat , ie, S i = {(x, y)|x = A i + y , x, y numere naturale}.
Cerint , a problemei este determinarea a dou˘a numere B = card(S 1 ) + card(S 2 ) + . . . + card(S n ),
respectiv C = card (S 1 ∪ S 2 ∪ . . . ∪ S n ).
Cerint , ˘a

Se cunosc N s , i numerele A 1 , A 2 , . . . , A N s , i se cere s˘a se determine numerele B s , i C.
Date de intrare

Din fis , ierul becuatii.in se citesc: num˘arul natural p de pe prima linie (ce poate avea dou˘a
valori: 1 sau 2, corespunz˘atoare uneia din cele dou˘a cerint , e, adic˘a 1 pentru determinarea lui B,
iar 2 pentru determinarea lui C), num˘arul N de pe a doua linie s , i de pe a treia linie numerele
A 1 , A 2 , . . . , A N cu cˆate un spat , iu ˆıntre ele.
Date de ies , ire
ˆ
In fis , ierul becuatii.out se va scrie num˘arul B, dac˘a p = 1 s , i respectiv num˘arul C, dac˘a p = 2,
cu semnificat , ia din enunt , .

Restrict , ii s , i preciz˘ari
• 1 < N ≤ 10000, num˘ar natural
• A i sunt numere naturale nenule mai mici strict decˆat 1000, 1 ≤ i ≤ N
• Pentru o mult , ime M, card(M) reprezint˘a num˘arul de elemente al mult , imii M
• Pentru mult , imile M s , i P, not˘am cu M ∪ P reuniunea dintre M s , i P
Exemple
becuatii.in becuatii.out Explicat , ie

1 3 p = 1 s , i deci afis , ˘am B. Prima ecuat , ie
2
2
2 este x = 1 + y , iar a doua ecuat , ie este
2
2
1 21 x = 21 + y . Mult , imile solut , iilor sunt
ˆ
S 1 = {(1, 0)} s , i S 2 = {(11, 10), (5, 2)}. In
acest caz B = 1 + 2 = 3.