MINISTERUL EDUCAIEI AL REPUBLICII MOLDOVA MHCTEPCTBO IIPOCBEEH PECJIK MO Olimpiada Republican la Informatic Ediia 2011 Chiinu 2011 2 Olimpiada Republican la Informatic. Ediia 2011. LucrareaconineproblemelepropuselaOlimpiadaRepublicanlaInformatica elevilor, ediia 2011. Pentru fiecare problem sunt descrise algoritmul i soluia respectiv n limbajul de programare PASCAL. Materialele Olimpiadei pot fi de un real folos la studierea Informaticii att elevilor, ct i profesorilor de Informatic. La elaborarea ediiei au contribuit: Ion Bolun,profesor universitar, Academia de Studii Economice a Moldovei Anatol Gremalschi,profesor universitar, Institutul de Politici Publice Iurie Mocanu, ef de direcie, Ministerul Educaiei Viorel Afteni,consultant superior, Ministerul Educaiei Nicolai Falico,lector superior, Universitatea Tehnica a Moldovei Dumitru Codreanu, doctorand, Universitatea Bucureti Dumitru Ciubati,director, TenerLab SRL Bogdna Denis,asistent, Universitatea Tehnic, Iai Constantin Dolghier,inginer, ICS Micrologic Design Automation SRL 3 Cuprins Cuvnt de salut ............................................................................................................................ 4 Clasele 79 ................................................................................................................................... 6 Anagrame ............................................................................................................................................ 7 Bilete ................................................................................................................................................. 10 Hrubele de la Cricova ........................................................................................................................ 12 Jocul .................................................................................................................................................. 16 Ptratul numrului binar ................................................................................................................... 18 Turnuri ............................................................................................................................................... 20 Punctajul competitorilor ................................................................................................................... 23 Complexitatea problemelor .............................................................................................................. 23 Clasele 1012 ............................................................................................................................. 24 Comoara ............................................................................................................................................ 25 Bilete ................................................................................................................................................. 29 Hrubele de la Cricova ........................................................................................................................ 31 Jocul .................................................................................................................................................. 35 Rdcina numrului binar ................................................................................................................. 38 Turnuri ............................................................................................................................................... 41 Punctajul competitorilor ................................................................................................................... 44 Complexitatea problemelor .............................................................................................................. 44 Lista premianilor ....................................................................................................................... 45 4 Cuvnt de salut Dragi elevi i stimai profesori, care v druii acestui domeniu de vrfal tiinei i tehnologiei moderne pe nume Informatica, Orice competiie este o experien pentru participani. Cu ct mai nalt este rating-ulcompetiiei,cuattmaibogatifructuoasesteexperienaobinut. OlimpiadaRepublicanlaInformaticntruneteceimaibunielevindomeniu din republic i are ca scop att ncurajarea i susinerea interesului elevilor ctre informatic,ctievaluareagraduluidepregtirealorndomeniu,elucidarea lacunelor n instruire i definirea unor ci de mbuntire continu a acesteia. Ea permite,deasemenea,stabilireadenoicunotinentreeleviiprofesori,dari reevaluareavalorilor.Rezultateleacesteiasuntfolositelaselectareacandidailor pentru echipa de elevi ce vor participa la competiii internaionale n informatic.Printreolimpiadelerepublicanealeelevilor,cealaInformaticare,totui,unrol aparte,determinatderoluldeosebitalinformaticiinsocietateamodern. Informaiaadevenit,nultimeledecenii,unneofactordeproduciemultmai important,deseori,dectmateriileprimeienergia:Cinedeineinformaia stpnetesituaia.Informatica,larndulsu,faciliteazconsiderabil valorificarea eficient a informaiilor deja cunoscute i, de asemenea, procesele de obinere a unor noi informaii. Calculatoareleceamaicomplexoperaraiuniiumane,fortificconsiderabil, uneorigreudeimaginat,capacitileintelectualeumane.Astfel,ntimpul parcurgeriidectreorazdeluminnvidadistaneideunsingurmilimetru, supercalculatorulTianhe-1AalUniversitiiNUDT(China)executcca.15000 instruciuni. Efectul aplicrii unorasemenea capaciti de procesarea informaiei esteconsiderabil.Serezolvproblemecareeraimposibilderezolvat,crete semnificativproductivitateaisembunteteconsiderabilcalitateamuncii. Avantajelefolosiriimijloacelorinformaticeauconduslaimplementarealortot mai larg. Sectorul informaticii a devenit un sector strategic de susinere a creterii economice i de prosperare a societii. Cercetri recente arat c pn la 30-50% dincretereaeconomicauneirisedatoreazsectoruluiTehnologiilor informaionale i de telecomunicaii.Anumeimpactulbeneficconsiderabilalinformaticiiasuprasocietiiacondusla concluzia despre evoluia spre societatea informaional-societatea cunoaterii. Pai concreinedificareaSocietiiinformaionalesuntntrepriniinRepublica Moldova. De exemplu, agenii economici care activeaz n domeniul TI se bucur de anumite faciliti fiscale. Solicitarea informaticienilor pe piaa muncii este att denaltcchiarinperioadedecrizeconomicnmulterisesimteun deficit de specialiti n domeniu.Dac tinerii sunt viitorul societii, atunci tinerilor informaticieni le revine rolul de avangardnedificareasocietiiviitoruluisocietiiinformaionale.Ne mndrimcuacestroldeosebitdeimportantalinformaticiinsocietate,dari responsabilitateacenerevineestepemsur.Pentruafacefasarcinilor 5 respective,trebuiesnepregtimbinedintimp,orientatisistematic.Conform raportuluigrupuluiBangemannctreConsiliulEuropei:rile,carenuvor ntreprindemsuriradicaleorientatelaedificareaintensasocietii informaionale, vor rmne economic n urm pentru totdeauna. Nu trebuie s ne liniteasc,naceastprivin,legeavaselorcomunicanteneraInternet-ului. Iarnavangardntotdeaunaseaflceimaibuni.Deeidepinde,nprimulrn, bunstareazileideminepentrutoi.Cualtecuvinte,minevoi,tinerii informaticienideazi,veifiaceeadecarevadepindesubstanialprosperarea acesteipalmedepmntRepublicaMoldova.Sarcinilesuntdiverseifiecare din noi la fel. Astzi unul din noi gsete o soluie original, iar mine un altul i n rezultat avem de ctigat cu toii. Lumeaaparinecelorcapabiliienergici.nprimiicinci,dinceimaibogai oameniailumiilaoraactual,treisuntdindomeniulinformaticiii telecomunicaiilor: pe primul loc este Carlos Slim telecomunicaii, pe al doilea William(Bill)Gates(fondatoralcompanieiMicrosoft)informaticipeal cincilea-LarryEllison(fondatoralcompanieiOracle)informatic.Existi multe alte exemple demne de urmat. Din2007la17maisesrbtoreteZiuaMondialaTelecomunicaiilori Societii Informaionale. Felicitri clduroase tuturor cu aceast srbtoare este srbtoareanoastrainformaticienilor,ispermcaceledouziledecompetiii n informatic ce urmeaz v vor mobiliza la noi realizri n domeniu.n numele Consiliului Olimpic la Informatic, Ion Bolun Profesor universitar, ASEM 6 Clasele 79 Denumirea problemei Numrul de puncte alocat problemei Denumirea fiierului surs Denumirea fiierului de intrare Denumirea fiierului de ieire Anagrame100 ANA.PAS ANA.C ANA.CPP ANA.INANA.OUT Bilete100 BILETE.PAS BILETE.C BILETE.CPP BILETE.INBILETE.OUT Hrubele de la Cricova 100 HRUBE.PAS HRUBE.C HRUBE.CPP HRUBE.INHRUBE.OUT Jocul100 JOCUL.PAS JOCUL.C JOCUL.CPP JOCUL.INJOCUL.OUT Ptratul numrului binar 100 PATRAT.PAS PATRAT.C PATRAT.CPP PATRAT.INPATRAT.OUT Turnuri100 TURNURI.PAS TURNURI.C TURNURI.CPP TURNURI.INTURNURI.OUT Total600--- 7 Anagrame Se consider mulimea irurilor de caractere} ..., , , {2 1 ns s s S = . Prin definiie, muimea S este o mulime fra anagrame, dac n ea nu exist nici o pereche} , {j is sde iruri, unul din care poate fi obinut din cellat prin operaii de anagramare. Amintim,canagramareaesteunprocedeuliterar,ceconstnschimbareaordinii literelorntr-uncuvnt.Deexemplu,nantichitate,numeleregeluiPtolemaios,prin anagramare,afosttransformatnApomelitos(careprovinedinmiere).Cuvinteleobinute prin anagramare se numesc anagrame. Sarcin. Elaborai un program care, cunoscnd mulimea} ..., , , {2 1 ns s s S = , calculeaz numrul m de iruri din cea mai mare submulime fr anagrame a mulimii S. Date de intrare. Prima linie a fiierului text ANA.IN conine numrul ntreg n. Fiecare dinurmtoarelenliniialefiieruluideintrareconinecteunirdecaractere.Linia1 + i a fiierului de intrare conine irul si. Date de ieire. Fiierului text ANA.OUT va conine pe o singur linie numrul ntreg m. Exemplu. ANA.INANA.OUT 6 AnaAreMere MereAreAna IonAreMere AreIonMere SiCeDacaIonAreMere IonAreMulteMere 4 Restricii.000 10 1 s s n . irurile de caractere din mulimea S sunt formate din literele mariimicialealfabetuluilatin.Fiecareirconinecelmult250decaractere.Timpulde execuienuvadepi0,5secunde.Programulvafolosicelmult32Megaocteidememorie operativ. Fiierul surs va avea denumirea ANA.PAS, ANA.C sau ANA.CPP. Rezolvare Mai nti vom ncerca sa rezolvm aceast problem prin metodaforei brute sau, prin alte cuvinte, prin metoda trierii. Vom elabora n acest scop urmtoarele subprograme: FunctionSuntAnagrame(A,B:string):booleanfunciareturneaz TRUE dac irurile de caractere A i B sunt anagrame i FALSE n caz contrar. Valorile acestei funciipotficalculate,verificnddacfrecveneledeapariieafiecruicaracternambele iruri sunt egale. FunctionEsteFaraAnagrame(C:setofstring):booleanfuncia repurneazTRUEdacmulimeaCdeiruridecaractereestefranagrameiFALSEncaz contrar.Valorileacesteifunciipotficalculateformndtoateperechileposibiledeiruri ) , ( B A ,C AeiC Be , apelnd pentru fecare pereche funcia EsteFaraAnagrame. 1.Un posibil algoritm, bazat pe metoda trierii, va avea urmtoarea structur: 2.Formm o submulime nevid C a mulimii de iruri S. 3.CuagutorulapeluluiEsteFaraAnagrame(C)verificmdacsubmulimea 8 respectivestefranagrame.Dacvaloareareturnatdefuncia EsteFaraAnagrame este TRUE, memorm numrul de elemente ale mulimii C. 4.ncontinuareformmonousubmulimeCamulimiiS.a.m.d.pnvorfi examinate toate submulimile posibile. ntruct numrul de submulimi nevide ale mulimii S este n2 , complexitatea temporal aunuiastfeldealgoritmvafi) 2 (nO .Evident,pentru20 > n ,programulbazatpemetoda trierii nu se va ncadra n timpul indicat n restriciile problemei. Prinurmare,competitoriicareaumerspeaceastcale,auavutansesobinpuncte doar n cazul testelor cu valori mici ale lui n. Complexitateatemporalaalgoritmuluipoatefinsredus,dac,nlocdetrierea tuturor submulimilor lui S, vom construi doar submulimea ce conine cel mai mare numr de cuvinte fr anagrame. O astfel de mulime poate fi construit dup cum urmeaz: 1.SortamcaractereledinfiecareiralmulimiiSnordinealfabetic.Evident,dup sortare, irurile care sunt anagrame devin egale ntre ele. 2.SortmiruriledinmulimeaSnordinelexicografic.Dupsortare,nmulimea ordonat S, irurile egale vor ocupa poziii consecutive. 3.ExcludemdinSsubmulimiledeiruricecoincid,lsndnSdoarcteunirdin submulimileexcluse.Evident,excludereapropriu-zisnicinuestenecesara,este suficient s numrm doar irurile ce difer. Complexitateatemporalaunuiastfeldealgoritmdepindedemetodeledesortare utilizate.ncazulmetodeibulelor,complexitateasortriicaracterelordinfiecareiral mulimiiSeste) (2nm O ,undemestenumrulmaximaldecaracterentr-unir,iar complexitateasortriiiruriloreste) (2n O .ntructcucreterealuiminvalorile) (2nm O cresccumultmaincetdectvalorile) 2 (nO ,anselecvortrecemaimultetestecresc. Totui,pentru250 = m i000 10 = n ,valoarea 8 210 25 , 6 ~ nm estepreaaproapede viteza de procesare a calculatoarelor moderne. Prinurmare,pentruafisiguricprogramulsevancadranrestriciiletemporale, trebuie utilizat o metod rapid de sortare, de exemplu, QuickSort, MergeSort sau HeapSort, caresuntdescrisenliteratur.Complexitateaunorastfeldemetodedesortareeste ) log ( n n O , fapt ce ne garanteaz respectarea restriciilor problemei. nprogramulceurmeaz,iruriledecaracteresuntstocatenmemoriadinamic,iar sortarea lor se face prin metoda QuickSort. Program Anagrame; type TSiruri = Array[1..10000] of String; var n : Integer; siruri : TSiruri; i, count : Integer; f, g : Text; procedure Swap(var a, b : string); var temp : string; begin temp := a; a := b; b := temp; end; procedure Sort(var s : String); { sorteaza caracterele unui sir de caracter prin numarare } 9 var i, k : Integer; c : Char; l : integer; hist: Array[char] of ShortInt; begin { numara caracterele } FillChar(hist, sizeof(hist), 0); for i := 1 to Length(s) do Inc(hist[s[i]]); l := 1; for c := char(0) to char(250) do for k := 1 to hist[c] do begin s[l]:=c; Inc(l); end; end; { Sort } function Partition(varv : TSiruri; left, right : Integer) : Integer; { partitionarea pentru procedeul QuickSort: Aduce elementele mai mici ca valoarea pivotului pe pozitiile 1..p, si returneaza acea valoare p } var pv : String; p, i: Integer; begin pv := v[right]; p:= left; for i := left to right - 1 do if v[i] < pv then begin Swap(v[i], v[p]); Inc(p); end; Swap(v[p], v[right]); Partition := p; end; { Partition } procedure QuickSort(var v : TSiruri; left, right : integer); var pivotIndex : Integer; begin if left >= right then exit; pivotIndex := Partition(v, left, right); QuickSort(v, left, pivotIndex -1); QuickSort(v, pivotIndex + 1, right); end; { QuickSort } begin { Citeste Datele } Assign(f, 'ana.in'); Reset(f); Readln(f, n); for i := 1 to n do Readln(f, siruri[i]); Close(f); { sorteaza caracterele sirurilor } for i := 1 to n do Sort(Siruri[i]); { sorteaza lexicografic sirurile de caractere } QuickSort(Siruri, 1, n); { numara cate sunt diferite } count := 1; for i:= 2 to n do if Siruri[i] Siruri[i-1] then Inc(count); { Scrie raspunsul } Assign(g, 'ana.out'); Rewrite(g); Writeln(g, count); Close(g); end. 10 Bilete Bileteledintransportulpublicdinmareleoraesuntnumerotate.De obicei, un numr de bilet este format din ase cifre zecimale. Unii elevi i studeni consider c n cazul n care suma primelor trei cifre din componena numrului de bilet este egal cu suma ultimelor trei cifre, biletul respectiv aduce noroc sau, prin alte cuvinte, este un bilet fericit. De exemplu, biletul cu numrul 032050 este fericit, iar cel cu numrul 283357 nu. Sarcin. Elaborai un program care, cunoscnd numrul de bilet, determin dac biletul respectiv este fericit. Datedeintrare.PrimalinieafiieruluitextBILETE.INconinenumrulntregn numrultotaldebiletesupuseexaminrii.Fiecaredinurmtoarelenliniialefiieruluide intrare conine cte un numr de bilet, format din ase cifre zecimale. Datedeieire.PrimalinieafiieruluitextBILETE.OUTvaconinenumrulntregn. Fiecare din urmtoarelen linii ale fiierului de ieire va conine cuvntulDA dac biletul din linia respectiv a fiierului de intrare este fericit din i NU n caz contrar. Exemplu. BILETE.INBILETE.OUT 3 032050 283375 121301 3 DA NU DA Restricii.1000 1 s s n .Timpuldeexecuienuvadepi0,5secunde.Programulva folosicelmult32Megaocteidememorieoperativ.Fiierulsursvaaveadenumirea BILETE.PAS, BILETE.C sau BILETE.CPP. Rezolvare Vomnotaprinc1,c2,c3,c4,c5,c6cifrelenumruluidebilet.Deexemplu,ncazul numrului de bilet 360710 avem31 = c ,62 = c ,03 = c ,74 = c ,15 = c ,06 = c . Cifrelenumruluidebiletpotficalculatenordineac6,c5,c4,c3,c2,c1prinmpriri succesiveanumruluidebiletiacturilorobinutelabaza10asistemuluizecimalde numeraie, reinnd resturile mpririlor. Evident, un bilet este fericit atunci cnd). ( ) (6 5 4 3 2 1c c c c c c + + = + + Program Bilete; { Clasele 07-09 } var Intrare, Iesire : text; n : longint; { numarul de bilete in fisierul de intrare } Numar : longint; { numarul de bilet } c1, c2, c3, c4, c5, c6 : integer; { cifrele numarului de bilet } i : longint; begin assign(Intrare, 'BILETE.IN'); reset(Intrare); assign(Iesire, 'BILETE.OUT'); rewrite(Iesire); 11 readln(Intrare, n); writeln(Iesire, n); for i:=1 to n do begin readln(Intrare, Numar); c6:=Numar mod 10; Numar:=Numar div 10; c5:=Numar mod 10; Numar:=Numar div 10; c4:=Numar mod 10; Numar:=Numar div 10; c3:=Numar mod 10; Numar:=Numar div 10; c2:=Numar mod 10; Numar:=Numar div 10; c1:=Numar mod 10; if (c1+c2+c3)=(c4+c5+c6) then writeln(Iesire, 'DA') else writeln(Iesire, 'NU'); end; { for } close(Intrare); close(Iesire); end. 12 Hrubele de la Cricova Dup o vizit la renumitele hrube* de la Cricova, un informatician a construit un robot carelucreazntr-uncmpdivizatnptrele(vezidesenul).Ptrelelehauratereprezint obstacolele,iarcelenehauratespaiilelibere. Ptreleledepeperimetrulplanului,cuexcepia celor de intrare sau ieire, snt haurate prin definiie. Robotul poate executa doar instruciunile SUS, JOS,DREAPTA,STANGA,conformcroraelse deplaseaznunuldinptrelevecine.Dacn ptratulvecinesteunobstacol,deexemplu,un peretesauunbutoi,arelocunaccidentirobotul iese din funciune. nformnumericplanulhrubeloresteredat printabloulAcunliniiimcoloane.Elementele ] , [ j i A aleacestuitablouauurmtoareasemnificaie:0spaiuliber;1obstacol;2 intrareanhrube;3ieireadinhrube.Iniial,robotulseaflnptrelulpentrucare 2 ] , [ = j i A . Sarcin. Elaborai un program, care, cunoscnd planul hrubelor, deplaseaz robotul prin ncperile subterane, de la intrarea n hrube la ieire. Colecia de vinuri fiind foarte bogat, nu se cere vizitarea obligatorie a tuturor ncperilor subterane. Date de intrare.Fiierul text HRUBE.IN conine pe prima linie numerele ntregi n, m separate prin spaiu. Pe fiecare din urmtoarele n linii se conin cte m numere ntregi] , [ j i A , separate prin spaiu. Datedeieire.FiierultextHRUBE.OUTvaconinepefiecareliniecteunadin instruciunileSUS,JOS,DREAPTA,STANGA,scrisenordineaexecutriilordectrerobot. Dac problema admite mai multe soluii, n fiierul de ieire se va scrie doar una, oricare din ele. Exemplu: HRUBE.INHRUBE.OUT 7 9 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 2 1 1 1 1 1 3 1 SUS DREAPTA DREAPTA DREAPTA DREAPTA SUS SUS DREAPTA DREAPTA JOS JOS JOS Restricii.100 , 5 s s m n . Timpul de execuie nu va depi0,5 secunde. Fiierul surs se va numi HRUBE.PAS, HRUBE.C sau HRUBE.CPP. *Hrubncperesaugaleriesubterancareserveteladepozitareaproduseloralimentare.nhrubeledela Cricova pe parcursul a mai multor decenii sunt depozitate cele mai bune vinuri din Republica Moldova. 13 Rezolvare Vomdenumipereteoricesuccesiunedelaturiadiacentedeptrele,fiecaredincare separunptrelnehaurat(spaiuliber)deunulhaurat(obstacol).Conformcondiiilor problemei, ntotdeauna exist un perete, care se ncepe la intrare i se termin la ieire. Prin urmare, pentru a gsi ieirea, este suficient s deplasm robotul de-a lungul unuia i aceluiaiperete,deexemplu,celuiadinmnadreaptarobotului.Evident,nprocesul deplasrii, robotul nu trebuie s se ndeprteze de peretele respectiv sau, prin alte cuvinte, el trebuie s in permanent mna dreapt pe perete. Pentruasimulaprocesuldedeplasarearobotului,introducemnstudiuurmtoarele variabile: y x, coordonatele curente ale robotului; Ddireciancareesteorientatrobotul(vomnotaacestedireciiprinNORD,SUD, EST, VEST); C instruciunea pe care trebuie s o execute robotul. Coordonateleurmtoruluiptrelliberncaretrebuiestreacrobotulsedetermin, analiznd direcia n care el este orientat i starea ptrelelor adiacente. De exemplu, presupunem c robotul este orientat n direciaNORD = D . Analizmmaintiptrelul) 1 , ( + y x dinmnadreaptarobotului.Dacacest ptrelestenehaurat,robotultreceneliischimborientarea:DREAPTA := C ; 1 : + = y y ;EST := D . Dacptreluldinmnadreaptarobotuluiestehaurat,analizm ptrelul ) , 1 ( y x din faa robotului. Dac acest ptrel este nehaurat, robotul trece n el fr ai schimba orientarea:SUS := C ,1 : = x x . Dacaambeleptrele,iceldinmnadreapt,iceldinfaarobotuluisunt haurate,analizmptrelul) 1 , ( y x dinmnastngarobotului.Dacacestptrel estenehaurat,robotultreceneliiischimborientarea:STANGA := C ;1 : = y y ; VEST := D . nsfrit,dacptreleledinmnadreapt,dinfaidinmnastnga robotului sunt haurate, robotul doar se ntoarce napoi, cu faa ctre ptrelul din care a venit:SUD := D . ntr-un mod similar se analizeaz i cazurile n care robotul este orientat spre SUD, EST sau VEST. Program Hrube; { Clasele 07-09 } const nmax=100; mmax=100; type Directie = (NORD, SUD, EST, VEST); var A : array[1..nmax, 1..mmax] of integer; n, m : integer; { dimensiunile campului } p, q : integer; { coordonatele intrarii } r, s : integer; { coordonatele iesirii} DI : Directie;{ orientarea initiala a robotului } Iesire : text; procedure Citeste; { Citeste datele de intrare } var i, j : integer; Intrare : text; begin assign(Intrare, 'HRUBE.IN'); 14 reset(Intrare); readln(Intrare, n, m); for i:=1 to n do begin for j:=1 to m do begin read(Intrare, A[i, j]); if A[i, j]=2 then begin p:=i; q:=j; A[i, j]:=0; end; if A[i, j]=3 then begin r:=i; s:=j; A[i, j]:=0; end; end; { for } readln(Intrare); end; { for } close(Intrare); if q=1 then DI:=EST; if q=m then DI:=VEST; if p=1 then DI:=SUD; if p=n then DI:=NORD; end; { Citeste } procedure Mergi(x, y : integer; D : Directie); label 1; begin repeat if D=NORD then begin if A[x, y+1]=0 then begin writeln(Iesire, 'DREAPTA'); y:=y+1; D:=EST; goto 1; end; if A[x-1, y]=0 then begin writeln(Iesire, 'SUS');x:=x-1; D:=NORD; goto 1; end; if A[x, y-1]=0 then begin writeln(Iesire, 'STANGA'); y:=y-1; D:=VEST; goto 1; end; D:=SUD; goto 1; end; { Nord } if D=SUD then begin if A[x, y-1]=0 then begin writeln(Iesire, 'STANGA'); y:=y-1; D:=VEST; goto 1; end; if A[x+1, y]=0 then begin writeln(Iesire, 'JOS'); x:=x+1; D:=SUD; goto 1; end; if A[x, y+1]=0 then begin writeln(Iesire, 'DREAPTA'); y:=y+1; D:=EST; goto 1; end; D:=NORD; goto 1; end; { SUD } if D=EST then begin if A[x+1, y]=0 then begin writeln(Iesire, 'JOS'); x:=x+1; D:=SUD; goto 1; end; if A[x, y+1]=0 then begin writeln(Iesire, 'DREAPTA'); y:=y+1; D:=EST; goto 1; end; if A[x-1, y]=0 then begin writeln(Iesire, 'SUS'); x:=x-1; D:=NORD; goto 1; end; D:=VEST; goto 1; end; { EST } if D=VEST then begin if A[x-1, y]=0 then begin writeln(Iesire, 'SUS'); x:=x-1; D:=NORD; goto 1; end; if A[x, y-1]=0 then begin writeln(Iesire, 'STANGA'); y:=y-1; D:=VEST; goto 1; end; if A[x+1, y]=0 then begin writeln(Iesire, 'JOS'); x:=x+1; D:=SUD; goto 1; end; D:=EST; goto 1; end; { VEST } 1: 15 until ((x=r) and (y=s)); end; { Mergi } begin Citeste; assign(Iesire, 'HRUBE.OUT'); rewrite(Iesire); Mergi(p, q, DI); close(Iesire); end. Pentruaevaluacomplexitateatemporalaalgoritmului,vompornidelafaptulc numruldeptrelealecmpuluidelucruarobotuluinudepetevaloareanm.Prin urmare,numrulderepetrialeinstruciunilordinciclulrepeat ... untilalprocedurii MERGI este de ordinulnm. Conform restriciilor problemei,100 , 5 s s m n . Evident, 410 = nm , mrime cu mult mai micdectcapacitateadeprelucrareacalculatoarelorpersonaledinlaboratorulde informatic. 16 Jocul Seconsideruncmpdejoc,formatdinnrnduriimcoloane(vezidesenul).La interseciiledernduriicoloaneseformeazcsue.Fiecarecsuestedefinitprin coordonatele sale: numrul de rnd x i numrul de coloan y. 12345 1 2 3 4 5 6 Juctorularuncunzar,carecadelantmplarenunadincsue.ngeneral, coordonatele acestei csue nu sunt cunoscute apriori, ns ele pot fi aflate explornd cmpul de joc. Deexemplu,ncazulcmpuluidejocdepedesen,zarulseaflncsuacu coordonatele5 = xi3 = y . Sarcin.Elaboraiunprogramcare,cunoscndsituaiadepecmpuldejoc,afl coordonatele csuei n care se afl zarul. Date de intrare. Fiierul text JOCUL.IN conine pe prima linie numerele ntregi n i m, separate prin spaiu. Fiecare din urmtoarele n linii ale fiierului de intrare conine cte un ir decaractere,formatdinexactmcifrebinare{0,1}.Daczarulseaflncsuacu coordonatelex,y,atuncicifrabinardinpoziiayaliniei1 + x afiieruluideintrareare valoarea 1. n caz contrar, cifra binar respectiv are valoarea 0.Datedeieire.FisierultextJOCUL.OUTvaconinepeosingurliniedounumere ntregi, separate prin spaiu: coordonatele x, y ale csuei n care se afl zarul. Exemplu. Pentru desenul din enunul problemei, fiierele de intrare i ieire sunt: JOCUL.INJOCUL.OUT 6 5 00000 00000 00000 00000 00100 00000 5 3 Restricii.1000 , 1 s s m n . Timpul de execuie nu va depi 1,0 secunde. Programul va folosicelmult32Megaocteidememorieoperativ.Fiierulsursvaaveadenumirea JOCUL.PAS, JOCUL.C sau JOCUL.CPP. 17 Rezolvare Vomexplorafiieruldeintrarecaractercucaracter.Evident,explorareafiieruluide intrare poate fi terminat imediat cum a fost citit cifra binar cu valoarea 1. Program Jocul; { Clasele 07-09 } label 1; var Intrare, Iesire : text; n, m : longint; x, y : longint; c : char; begin assign(Intrare, 'JOCUL.IN'); reset(Intrare); readln(Intrare, n, m); for x:=1 to n do begin for y:=1 to m do begin read(Intrare, c); if c='1' then goto 1; end; { for } readln(Intrare); end; { for } 1: close(Intrare); assign(Iesire, 'JOCUL.OUT'); rewrite(Iesire); writeln(Iesire, x, ' ', y); close(Iesire); end. 18 Ptratul numrului binar Seconsiderunnumrbinarnaturalx,formatdinncifrebinare{0,1}.Deexemplu, numrul binar1001 = xeste format din4 = ncifre binare. Sarcin. Elaborai un program care calculeaz numrul binar y, 2x y = . Date de intrare. Fiierului text PATRAT.IN conine pe o singur linie numrul binar x. Date de ieire. Fiierului text PATRAT.OUT va conine pe o singur linie numrul binar y, scris fr zerouri nesemnificative. Exemplu. PATRAT.INPATRAT.OUT 10011010001 Restricii.120 1 s s n .Timpuldeexecuienuvadepi0,5secunde.Programulva folosicelmult32Megaocteidememorieoperativ.Fiierulsursvaaveadenumirea PATRAT.PAS, PATRAT.C sau PATRAT.CPP. Rezolvare Vommemoranumrulbinarxntr-unirdecaractere.Ptratulacestuinumrlvom calcula implementnd algoritmul de nmulire a dou numere binare n coloni. Program PatratulNumaruluiBinar; { Clasele 07-09 } var A, B : string; procedure Citeste(var X : string); { Citeste X din fisierul de intrare } var Intrare : text; begin assign(Intrare, 'PATRAT.IN'); reset(Intrare); readln(Intrare, X); close(Intrare); end; { Citeste } procedure Scrie(X : string); { Scrie X in fisierul de iesire } var Iesire : text; begin assign(Iesire, 'PATRAT.OUT'); rewrite(Iesire); writeln(Iesire, X); close(Iesire); end; { Scrie } procedure AdunaCifreBinare(a, b, c : char; var s, t : char); { Aduna cifrele binare a, b, c } { Returneaza suma s si transportul t } begin if (a='0') and (b='0') and (c='0') then begin t:='0'; s:='0' end; if (a='0') and (b='0') and (c='1') then begin t:='0'; s:='1' end; if (a='0') and (b='1') and (c='0') then begin t:='0'; s:='1' end; 19 if (a='0') and (b='1') and (c='1') then begin t:='1'; s:='0' end; if (a='1') and (b='0') and (c='0') then begin t:='0'; s:='1' end; if (a='1') and (b='0') and (c='1') then begin t:='1'; s:='0' end; if (a='1') and (b='1') and (c='0') then begin t:='1'; s:='0' end; if (a='1') and (b='1') and (c='1') then begin t:='1'; s:='1' end; end; { AdunaCifre } procedure AliniazaNumereBinare(var X, Y : string); { Aduce numerele X, Y la acelasi numar de cifre binare } label 1; var n, m, i : integer; begin n:=length(X); m:=length(Y); if n=m then goto 1; if n n , reducem problemacu n discuri la cea cu ) 1 ( n discuri: 1.Apelm procedura MutaDiscurile pentru a muta1 ndiscuri de pe tija TI pe tija TM, folosind ca tija de manevr tija TF. 2.Mutm discul rmas de pe tija TI pe tija TF. 3.ApelmproceduraMutaDiscurilepentruamutadiscuriledepetijaTM petijaTF, folosind ca tij de manevr tija TI. 22 Prezentm n continuare programul ce implementeaz procedura MutaDiscurile. program Turnuri; { Clasele 07-09 } var n : integer; Intrare, Iesire : text; procedure MutaDiscurile(n, TI, TF, TM : integer); begin if n=1 then writeln (Iesire, TI, ' ', TF) else begin MutaDiscurile(n-1, TI, TM, TF); writeln (Iesire, TI, ' ', TF); MutaDiscurile(n-1, TM, TF, TI); end; { else } end; { MutaDiscurile } begin assign(Intrare, 'TURNURI.IN'); reset(Intrare); readln(Intrare, n); close(Intrare); assign(Iesire, 'TURNURI.OUT'); rewrite(Iesire); MutaDiscurile(n, 1, 3, 2); Close(Iesire); end. Prin msurri directe de putem convinge c timpul de execuie a programuluiTurnuri corespunde restriciilor problemei. 23 Punctajul competitorilor Punctajul competitorilor, Clasele 07-090501001502002503003504004505001 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47Competitorii Complexitatea problemelor Punctajul mediu pe problema, Clasele 07-09372897 710510152025303540Bilete Jocul Patrat Hrube Anagrame Turnuri24 Clasele 1012 Denumirea problemei Numrul de puncte alocat problemei Denumirea fiierului surs Denumirea fiierului de intrare Denumirea fiierului de ieire Comoara100 COMOARA.PAS COMOARA.C COMOARA.CPP COMOARA.INCOMOARA.OUT Bilete100 BILETE.PAS BILETE.C BILETE.CPP BILETE.INBILETE.OUT Hrubele de la Cricova 100 HRUBE.PAS HRUBE.C HRUBE.CPP HRUBE.INHRUBE.OUT Jocul100 JOCUL.PAS JOCUL.C JOCUL.CPP JOCUL.IN Rdcina numrului binar 100 RAD.PAS RAD.C RAD.CPP RAD.INRAD.OUT Turnuri100 TURNURI.PAS TURNURI.C TURNURI.CPP TURNURI.INTURNURI.OUT Total600--- 25 Comoara Vntorii de comori au descoperit n una din ncperile nchise ale unui castel medieval nlingourideaurdedimensiunidistincte.Fiecarelingoui,n i , , 3 , 2 , 1 = ,reprezintun paralelipiped dreptunghiular cu dimensiunile i i iz y x . Pentru a scoate lingourile la lumina zilei, vntorii de comori trebuie s perforeze ntr-un zid de piatr unul sau mai multe orificii dreptunghiulare,carenuaupunctedetangen.Unlingoupoatefiscosprintr-unorificiu dreptunghiulardoaratuncicndlimeainlimeaorificiuluisuntegalesaumaimarica limeainlimeauneiadinfeeledreptunghiularealeparalelipipedului.Evident,lingoul poate fi rotit in orice fel. Pentru ai uura munca, vntorii de comori doresc ca suma ariilor orificiilor ce trebuie perforate s fie ct mai mic. Sarcin.Elaboraiunprogramcare,cunoscnddimensiunilelingourilordeaur, calculeaz valoarea minim S a sumei ariilor orificiilor de perforat, ce vor fi suficiente pentru a scoate toate lingourile. Datedeintrare.FiierultextCOMOARA.INconinepeprimalinienumrulntregn. Fiecaredinurmtoarelenliniialefiieruluideintrareconinectetreinumerentregi, separateprinspaiu.Linia1 + i afiieruluideintrareconinedimensiunilexi,yiiziale lingoului i. Date de ieire. Fiierul text COMOARA.OUT va conine pe o singur linie numrul ntreg S valoarea minim a sumei ariilor orificiilor de perforat. Exemplu. COMOARA.INCOMOARA.OUT 3 1 4 4 5 3 2 1 2 2 8 Restricii.5000 1 s s n ;10000 , , 1 s si i iz y x .Timpuldeexecuienuvadepi3,0 secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea COMOARA.PAS, COMOARA.C sau COMOARA.CPP. Rezolvare Maintivommeniona,cncazulunuisingurlingoui,dimensiuniledreptunghiului de cea mai mic arie sedetermin n mod trivial, selectnd din valorile i i iz y x , ,doar dou, cele mai mici din ele. n continuare, pentru fiecare lingou i vom nota astfel de dimensiuni prin i iy x ,i le vom aranja n ordine descresctoare, adic i iy x > . Valoareaminimasumeiariilororificiilordeperforatpoateficalculatprinmetoda programrii dinamice dup cum urmeaz: 1.Conformdimensiunilorx,sortamlingourilenordinecresctoare.Dacexistdou sau mai multe lingouri cu aceiai dimensiune x, sortm astfel de lingouri n ordine cresctoare conform dimensiunii y. 2.Eliminm din studiu lingourile mici, care ncap integral in alte lingouri, mai mari. nacestscop,parcurgemlingouriledejasortatei,lafiecarepasi,eliminamtoatelingourile 26 precedentej,pentrucare i jx x s i i jy y s .Sepoateobservacdupeliminare,pentru lingourile ramase se respect inegalitile i ix x 1. 3.Fie n numrul curent de lingouri rmase. Introducem n studiu irul) 0 ( F ,) 1 ( F , ..., ) (i F ,...,) (n F , n care) (i Feste aria minima a orificiilor ce trebuie perforate pentru a scoate primeleilingourinordineastabilitlapasul2. Valorileacestuiirpotficalculateconform urmtoarelor formule recurente: 0 ) 0 ( = F ; } ..., , 1 ) 1 ( min{ ) ( i j x y j F i Fi j= + = ,n i ..., , 2 , 1 = . Program Comoara; const MAXN = 5000; MAXXY = 10000; type TLingou = record x, y : longint; end; var n : longint; L : array[1..MAXN] of TLingou; F : array[0..MAXN] of longint; procedure Citeste; { Citeste datele de intrare } { Selecteaza cele doua, mai mici, dimensiuni ale lingoului } { Ordoneaza dimensiunile selectate in ordine descrescatoare } var Intrare : text; x, y, z : longint; { dimensinule lingoului curent } i : longint; r : longint; begin assign(Intrare, 'COMOARA.IN'); reset(Intrare); readln(Intrare, n); for i:=1 to n do begin readln(Intrare, x, y, z); if ((z>=x) and (z>=y)) then begin L[i].x:=x; L[i].y:=y end; if ((y>=x) and (y>=z)) then begin L[i].x:=x; L[i].y:=z end; if ((x>=y) and (x>=z)) then begin L[i].x:=y; L[i].y:=z end; if (L[i].x