Page 9 - MATINF Nr. 3
P. 9

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
   4   5   6   7   8   9   10   11   12   13   14