Page 123 - MATINF Nr.2

˘
PROBLEME DE INFORMATICA PENTRU CONCURSURI 123

I 24 (ec). Alexandru are la dispozit , ie un tablou p˘atratic de dimensiune n cu numere ˆıntregi s , i
k ecuat , ii de tipul I s , i II. Ecuat , iile de tipul I sunt de forma ax + b = c, cu a, b, c numere naturale,
2
iar ecuat , iile de tipul II sunt de forma: ax + bx + c = d, cu a, b, c, d numere naturale.
Alexandru ˆıs , i propune s˘a determine pentru fiecare tip de ecuat , ie num˘arul lor s , i cˆate dintre
ele au r˘ad˘acinile ˆın tabloul dat.
Cerint , ˘a

S˘a se scrie un program care determin˘a num˘arul de ecuat , ii de tipul I, cˆate dintre acestea au
exact o r˘ad˘acin˘a ˆın tablou, respectiv num˘arul de ecuat , ii de tipul II s , i cˆate dintre acestea au
ambele r˘ad˘acini ˆın tablou.

Date de intrare
Fis , ierul de intrare ec.in va cont , ine: pe prima linie numerele naturale n s , i k separate
printr-un spat , iu, pe urm˘atoarele n linii elementele tabloului separate prin cˆate un spat , iu, iar pe
urm˘atoarele k linii ecuat , iile ˆın forma din enunt , , cˆate una pe fiecare linie.

Date de ies , ire
Fis , ierul de ies , ire ec.out va cont , ine pe prima linie dou˘a numere separate printr-un spat , iu
reprezentˆand num˘arul de ecuat , ii de tipul I, respectiv num˘arul de ecuat , ii de tipul I care au
exact o r˘ad˘acin˘a, aflat˘a ˆın tablou, iar pe a doua linie tot dou˘a numere separate printr-un spat , iu
reprezentˆand num˘arul de ecuat , ii de tipul II, respectiv num˘arul de ecuat , ii de tipul II cu exact
dou˘a r˘ad˘acini (posibil egale), ambele r˘ad˘acini ˆın tablou.
Restrict , ii s , i preciz˘ari

• 1 ≤ n ≤ 500
• 1 ≤ k ≤ 1000
• Elementele tabloului sunt numere ˆıntregi cu maxim 4 cifre fiecare
• La fiecare ecuat , ie de tipul I a, b, c vor fi precizate, chiar dac˘a acestea au valoarea 0 sau 1
(de exemplu x + 2 = 3 va ap˘area 1x + 2 = 3)
• La fiecare ecuat , ie de tipul II a, b, c, d vor fi precizate, chiar dac˘a acestea au valoarea 0 sau
2
2
1 (de exemplu x + 1 = 3 va ap˘area 1x + 0x + 1 = 3)
• Pentru ecuat , iile de tipul I a, b, c sunt numere naturale cu maxim 4 cifre
• Pentru ecuat , iile de tipul II a, b, c, d sunt numere naturale cu maxim 4 cifre
• Se va acorda: 10% din punctaj pentru num˘arul de ecuat , ii de tipul I, 30% din punctaj
pentru cˆate dintre ele au exact o r˘ad˘acin˘a ˆın tablou, 20% din punctaj pentru num˘arul de
ecuat , ii de tipul II s , i 40% din punctaj pentru cˆate dintre ele au ambele r˘ad˘acini ˆın tablou
Exemplu
ec.in ec.out Explicat , ie
2 5 2 1 Prima ecuat , ie este de tipul I si are r˘ad˘acina 0, care nu se
1 2 3 1 g˘ases , te ˆın tablou.
2 -1 A doua ecuat , ie este de tipul II s , i are dou˘a r˘ad˘acini egale cu -1,
1x+0=0 care se g˘asesc ˆın tablou.
20x2+40x+20=0 A treia ecuat , ie este de tipul I s , i are r˘ad˘acina 2, care se
101x+200=402 g˘ases , te ˆın tablou.
2x2+1x+4=0 A patra ecuat , ie este de tipul II s , i nu are r˘ad˘acinile ˆın tablou.
1x2+1x+3=5 A cincea ecuat , ie este de tipul II s , i are r˘ad˘acinile -2 s , i 1, dar
nu sunt amˆandou˘a ˆın tablou.
Timp maxim de execut , ie: 0.8 secunde/test.

Memorie total˘a disponibil˘a 4 MB.
Doru Anastasiu Popescu, Pites , ti (ONI 2011)