Page 9 - MATINF Nr. 3

Concursul de Informatic˘a Programming Day 9

Timp maxim de execut , ie: 0.2 secunde/test.
Memorie total˘a disponibil˘a 4 MB.
Dimensiunea maxim˘a a sursei: 5 KB.

Solut , ie

Pentru rezolvarea primei cerint , e se va determina pentru fiecare linie suma elementelor s
(care reprezint˘a num˘arul de 1) s , i apoi se compar˘a s cu o variabila Max, care init , ial este 0. Dac˘a
s > Max, atunci Max = s. Valoarea final˘a a lui Max se va afis , a.

Pentru cerint , a a doua se parcurg elementele tabloului s , i cˆand se g˘ases , te un element egal cu
1 se incrementeaz˘a o variabil˘a Nr cu 1 (aceasta reprezint˘a num˘arul de lant , uri, init , ial avˆand
valoarea 0) s , i se merge pe lant , ul ce ˆıl cont , ine pe acesta (posibil, pe rˆand, ˆın dou˘a direct , ii),
elementele parcurse transformˆandu-se din 1 ˆın 0. Dup˘a parcurgerea elementelor tabloului se va
afis , a Nr.

Problema 2 – rain
Pe o plantat , ie s-au amplasat sisteme pentru analiza umidit˘at , ii, care detecteaz˘a pic˘aturile de
ploaie ce cad pe p˘amˆant ˆın raza lor de act , iune. Un astfel de sistem poate fi reprezentat printr-un
segment de dreapt˘a ce cont , ine senzori de la 1 la M (amplasat , i uniform de-a lungul segmentului).
Un senzor detecteaz˘a toate pic˘aturile care cad pe dreapta perpendicular˘a pe segmentul sistemului
de analiz˘a ˆın acel punct s , i ret , ine indexul senzorului unde a c˘azut pic˘atura. Senzorii sunt foarte
mici s , i des , i, astfel ˆıncˆat o pic˘atur˘a de ploaie va pica ˆıntotdeauna exact ˆın raza unui singur
senzor.

Dup˘a fiecare secund˘a, sistemul trimite datele ˆınregistrate la un calculator pentru a fi
interpretate. Dup˘a T secunde, expertul care analizeaz˘a datele ar dori s˘a afle care este distant , a
maxim˘a dintre doi senzori ˆıntre care nu a c˘azut nicio pic˘atur˘a de ploaie (acest lucru ˆınsemnˆand
c˘a zona respectiv˘a nu a primit suficient˘a ap˘a ˆın urma celor T secunde).
Deoarece num˘arul de senzori s , i num˘arul de pic˘aturi de ploaie ˆınregistrate sunt mult prea
mari pentru a fi analizate manual, expertul ar mai dori s , i ca programul de calculator s˘a ˆıi reduc˘a
num˘arul de senzori analizat , i, extr˘agˆandu-i numai pe cei cu indexul num˘ar prim din primii K
(el consider˘a c˘a aces , tia sunt suficient , i pentru analiz˘a), ˆınsot , it , i de num˘arul de secunde ˆın care
aces , tia au ˆınregistrat pic˘aturi de ploaie.

Cerint , ˘a
Cunoscˆand M, T, K, precum s , i T vectori ordonat , i cresc˘ator, cˆate unul pentru fiecare secund˘a,
cu indecs , ii senzorilor care au ˆınregistrat cel put , in o pic˘atur˘a de ploaie ˆın secunda respectiv˘a, se
cere:
1. distant , a maxim˘a dintre 2 senzori ˆıntre care nu a c˘azut nicio pic˘atur˘a de ploaie (ca diferent , a
dintre indecs , ii lor);
2. senzorii cu indexul num˘ar prim s , i mai mic sau egal cu K, ˆımpreun˘a cu numerele aferente
de secunde ˆın care au ˆınregistrat pic˘aturi de ploaie.
Date de intrare
Fis , ierul de intrare rain.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.

Urmeaz˘a o linie cont , inˆand cele 3 numere M, T s , i K, separate prin cˆate un spat , iu.

Urmeaz˘a T linii ce descriu pic˘aturile de ploaie ˆınregistrate ˆın fiecare din cele T secunde.
A i-a dintre aceste linii va cont , ine mai ˆıntˆai un num˘ar N i , reprezentˆand num˘arul de pic˘aturi