Page 8 - MATINF Nr. 13-14

8 D.A. Popescu, C. B˘alc˘au, D. Constantin

Exemplu

ecuatii.in ecuatii.out
1 1
3
1xˆ2+1x+2=0
20x+40=0
2xˆ2+4x+2=0
4
1 8 2 10
2 2
3
1xˆ2+1x+2=0
20x+40=0
1xˆ2+5x+6=0
4
1 8 2 10

Explicat , ii
a
a
Pentru prima cerint , ˘a, exist˘ o singur˘ ecuat , ie de gradul 1.
Pentru a doua cerint , ˘a: prima ecuat , ie nu are r˘ad˘acini reale, a doua are r˘ad˘acina −2 cu
| − 2| = 2, care este ˆın s , irul v, iar a treia ecuat , ie are r˘ad˘acinile −2 s , i −3, cu | − 2| = 2 care este
ˆın s , irul v. Astfel exist˘ dou˘a ecuat , ii avˆand m˘acar o r˘ad˘acin˘a cu valoarea absolut˘a ˆın s , irul v.
a
Timp maxim de execut , ie: 0.2 secunde/test.
Memorie total˘ disponibil˘a: 4 MB.
a
Solut , ie

Cerint , a 1 ( 20 puncte)
a
Pentru fiecare ecuat , ie citim cˆate un s , ir de caractere s , i verific˘am dac˘ acesta cont , ine caracterul
,,ˆ”. Dac˘a nu ˆıl cont , ine, num˘ar˘am ecuat , ia ca fiind de gradul 1. Timp de execut , ie: O(N).

Cerint , a 2 ( 80 puncte)
Pentru fiecare ecuat , ie citim cˆate un s , ir de caractere s , i determin˘am r˘ad˘acinile.

Astfel, construim un tablou bidimensional a cu N linii s , i 3 coloane:

a[i][0] = num˘arul de r˘ad˘acini ˆıntregi ale ecuat , iei num˘arul i;

a
a[i][1] = prima r˘ad˘acin˘ ˆıntreag˘ a acesteia, dac˘a exist˘a;
a
a[i][2] = a doua r˘ad˘acin˘a ˆıntreag˘a a acesteia, dac˘ exist˘a, i = 1, 2, . . . , N.
a
Citim cele M numere din s , irul v s , i construim un vector caracteristic:

a
c[i] = 1, dac˘ i este ˆın s , irul v;
c[i] = 0, ˆın caz contrar, i = 0, 1, . . . , 1000000.

Apoi num˘ar˘am ecuat , iile care au cel put , in o r˘ad˘acin˘a cu valoarea absolut˘a ˆın v, folosind
tabloul bidimensional a s , i vectorul c. Timp de execut , ie: O(N + M).