Din GInfo 8:
SOLUȚIILE problemelor propuseCe îi pasionează pe rezolvitorii de probleme din domeniul algoritmicii? În primul rând varietatea enunțurilor. Apoi varietatea rezolvărilor. Vă prezentăm posibile abordări pentru problemele Olimpiadei de Informatică a Europei Centrale și de Est, rezolvări care aparțin autorilor problemelor din Croația. Pentru explicații și implementarea algoritmilor mulțumim colaboratorilor revistei noastre: prof. dr. Horia Georgescu, studentul Mihai Scorțaru și elevul Andrei Vancea. P089801: PătrateFiecărui al i-lea pătrat i se vor asocia două variabile de tip articol Pi și Qi având câmpurile x și y, reprezentând coordonatele colțurilor din stânga sus, respectiv dreapta jos, ale pătratului. Problema vizibilității pătratelor se reduce la problema vizibilității segmentelor PiQi. Este evident că Qi.x=Pi.x+lungi, iar Qi.y=Pi.y-lungi, unde lungi este lungimea laturii pătratului. Mai observăm că distanța de la origine la un segment PiQi este (Pi.x+Pi.y)/. Observația se bazează pe faptul că segmentul PiQi este diagonala unui pătrat, deci întotdeauna formează un unghi de 45 de grade cu abscisa. Rezultă că la compararea distanței a două segmente față de origine este suficient să luăm în calcul cantitățile Pi.x+Pi.y . Vom utiliza o funcție Orientare care, apelată pentru două puncte A și B din primul cadran, va întoarce una dintre valorile 1, 0, -1 după cum panta dreptei OA este mai mare, egală sau mai mică decât panta dreptei OB. Începem prin a ordona segmentele PiQi descrescător după pantele lui OPi. Considerăm pe rând segmentele PiQi, i=1,...,n și dacă un astfel de segment este vizibil, vom mări cu o unitate variabila n_viz, inițializată cu 0. Fie PiQi un astfel de segment. Fie R' punctul curent de pe PiQi cu proprietatea că PiR' este obturată de segmentele PjQj analizate până la acest moment de timp; inițial R'=Pi. Deoarece ne interesează numai panta lui OR', vom memora în loc de R' puncte R care sunt actualizate cu anumite puncte Qj. Atunci pentru segmentul PiQi vom efectua următoarele calcule: R Ź Pi Úț pentru j=1,n execută ł Úț dacă distanța de la O la PiQi este mai mică decât ł ł cea de la O la PjQj ł ł atunci {segmentul PiQi nu poate fi obturat de PjQj} ł ł altfel ł ł Úț dacă panta lui OR este cuprinsă între panta lui OQj ł ł ł și cea a lui OPj, adică dreapta OR taie ł ł ł segmentul PjQj (vezi figura) ł ł ł atunci R Ź Qj ł ł Àț ł Àț Àț Úț dacă panta lui OQi < panta lui OR ł atunci n_viz Ź n_viz+1 Àț Ajungem astfel la următorul program: P089802: Cărți de jocFie q permutarea de grad n citită de la intrare și p permutarea căutată, adică permutarea inițială care trebuie reconstituită. Este esențial ca din enunțul problemei să reținem următoarele:
De exemplu (2) arată că permutarea inițială p nu este oarecare, ci are proprietatea pn=en, unde en este permutarea identică de grad n. Problema cere ca, plecând de la numerele naturale n, s și de la permutarea q, să determinăm acea permutare p de grad n care ridicată la puterea 2s să dea tocmai q. Să observăm că (2s,n)=1 deoarece n este impar. Atunci, conform unui rezultat din cartea de Algebră de clasa a XII-a, va exista un număr natural u având proprietatea: 2su=1 (mod n). Fie t restul împărțirii lui 2s la n; el se calculează astfel: t Ź 1; pentru i=1,s execută t Ź (t+t) mod n; Acum u poate fi obținut după cum urmează: u Ź 1; cât timp restul împărțirii lui u*t la n diferă de 1 execută u Ź u+1; Rezultă că 2su=k*n+1 pentru un anumit k natural. Deci trebuie determinată permutarea p de grad n care ridicată la puterea 2su să fie egală cu qu, adică p=qu . Suntem conduși astfel la următorul program: Listing CARDS.PAS P089803: ReduceriFie a vectorul cu n componente, citit de la intrare și fie t valoarea la care trebuie să ajungem făcând reduceri. Prin reduceri, unele dintre componentele lui a își schimbă semnul. Căutăm deci vectorul r cu proprietatea: r1a1+r2a2+...+rnan=t și r1,r2,...,rnÎ{-1,1} (1) Fie a1+a2+...+an=sum. Prin adunare cu relația (1) obținem: s1a1+s2a2+...+snan=t+sum cu s1,s2,...,snÎ{0,2}. Cum r1=1 și r2=-1, rezultă că s1=2, s2=0 și că urmează să determinăm s3,...,snÎ{0,2} având proprietatea: s3a3+...+snan=scop, unde scop=t+sum-2a1 și cu precizarea că si va fi 0 dacă și numai dacă ri este -1. În continuare vom calcula sumele posibile: s3a3+... +snan și "geneza" lor. Vom folosi un vector sume indexat de la 0 la 20000 (acum sumele posibile pot fi doar pozitive și egale cu cel mult 20000, deoarece fiecare dintre cei maximum 100 de termeni este cel mult 200). Inițial vom pune sume[0]=-1 și sume[i]=-2 pentru i=1,...,scop. Când o valoare v va fi marcată ca putând fi atinsă, vom pune sume[v]=i, unde v=v'+ai și v' atinsă. În acest mod va fi posibilă identificarea acelor elemente ai care au fost adăugate (de fapt a fost adăugat dublul lor), adică putem determina vectorul r satisfăcând (1). Mai trebuie să reconstituim din vectorul r pozițiile pe care s-au efectuat reducerile. Pentru aceasta să observăm că dacă este valabilă egalitatea: t = a1- ... ?ai+ai+1+...+ai+k-ai+k+1-...-an atunci efectuând k reduceri pe poziția i obținem: t = a1- ... ?bi-ai+k+1-...-an cu bi=(...((ai-ai+1)-ai+2)-...ai+k). Conform observației de mai sus vom pleca cu poziția curentă poz egală cu n și vom repeta succesiv următoarele operații până când ajungem pe prima poziție (mergem mereu de la dreapta la stânga): - trecem peste toate pozițiile pentru care valoarea r corespunzătoare este ?1, micșorând pe poz; - trecem peste toate pozițiile pentru care valoarea r corespunzătoare este 1, micșorând pe poz; fie nr numărul lor; - introducem în vectorul reduc de nr ori valoarea curentă a lui poz. În final se completează cu 1 pozițiile din reduc ce nu au primit valori, corespunzător faptului că acum t se exprimă ca o "sumă" în care doar primul termen are valoarea r corespunzătoare egală cu 1, deci se fac numai reduceri pe prima poziție. P089804: SoldațiEtapa 1. Este evident că toate punctele date date (toți soldații) trebuie să "cadă" pe o dreaptă orizontală y=yf. Drept urmare vom căuta yf cu minim, reprezentând suma distanțelor punctelor la dreapta y=yf. Tentația de a aborda această problemă folosind cunoștințele de analiză matematică este normală, dar neproductivă în acest caz. Este momentul de a preciza că dacă afirmația "matematica ajută informatica" este cât se poate de corectă, la fel de corectă este afirmația că "informatica ajută matematica". Vom ordona crescător vectorul y, deci acum y1 Ł y2 Ł ... Ł yn. Pentru aceasta vom utiliza metoda heapsort (sortare de ansamble) nu numai pentru a nu intoxica pe cititor cu sortarea rapidă folosită în programele prezentate, dar și ca prilej pentru a reaminti că metoda heapsort necesită totdeauna un timp de ordinul O(log n), pe când sortarea rapidă (Quicksort) are aceeași complexitate în timp, dar numai în medie. Să considerăm mai întâi y1 și yn. Este clar că suma distanțelor lor la y=yf este minimă dacă drept yf luăm oricare număr întreg din intervalul [y1,yn]; suma minimă va fi yn-y1, oricare ar fi yf astfel ales. Continuăm cu perechea y2, yn-1. Rezultă, la fel ca mai sus, că suma distanțelor lor la y=yf este minimă dacă yf este oricare număr întreg din [y2,yn-1] și că în acest caz suma va fi yn-1-y2. Se continuă în același mod. Dacă în final ajungem la un singur număr (adică n este impar) este clar că yf va trebui ales ca fiind acel număr. Dacă în final ajungem la două numere (adică n este par), putem lua drept yf oricare număr dintre ele și suma distanțelor la y=yf este diferența lor. În concluzie yf poate fi ales ca fiind componenta din y de pe poziția (n+1)/2. Să mai observăm că de fapt nu ne interesează efectiv valoarea lui yf, ci numai valoarea minimă a sumei , care se poate calcula după cum urmează conform celor de mai sus: sy Ź 0; p Ź 1; u Ź n; Úț cât timp p<u ł sy Ź sy + yn - yp; ł p Ź p + 1; ł u Ź u - 1; Àț Etapa 2. Am redus acum problema din plan pe dreaptă și anume pe dreapta y=yf. Punctele de abscise x1,x2,...,xn trebuie deplasate pe pozițiile consecutive (de pe această dreaptă) xf+1,xf+2,?,xf+n. Rezultă că vom căuta xf cu suma minimă, adică minimă. Repetând raționamentul de mai sus referitor la ordonate, vom salva vectorul x în vectorul xinit, vom înlocui fiecare valoare xi cu xi-i și vom obține sortare valoarea xf căutată. Acum efortul de a aduce valorile x1,x2,...,xn pe pozițiile xf+1,xf+2,?,xf+n se poate calcula imediat ca fiind suma valorilor |xf-(xiniti-i)|. Lăsăm pe seama cititorului să demonstreze că mutarea soldaților poate fi efectuată în sx+sy pași, cu respectarea regulii ca pe fiecare poziție să apară la fiecare moment de timp cel mult un soldat (așa cum cere problema). Programul este următorul: P089805: ȘoseleReformulăm problema în termeni din teoria grafurilor. Fiind dat un multigraf orientat cu vârfurile 1,...,n, între două vârfuri pot exista mai multe arce (muchii orientate). Fiecărei muchii i se atașează o lungime și o taxă care trebuie plătită la traversarea sa. Se mai dă o sumă de bani k. Se cere cel mai scurt drum (dacă există) de la 1 la N pentru care taxa totală plătită să nu depășească valoarea k. O muchie este memorată ca o înregistrare (numită muchie) cu câmpurile sursa, tinta, lung, cost cu semnificații evidente. Numărul muchiilor este nm iar valorile lor sunt memorate în tabloul M. Vom folosi tabloul L(10000) care corespunde unei liste. Fiecare element al listei va fi o înregistrare de tip stare, având câmpurile:
Elementul 0 al listei L conține („,„,„) pentru ușurarea inserării unui element în listă. Variabila cap păstrează valoarea poziției imediat următoare ultimului element din listă (care de fapt va fi primul scos); deci inițial cap=1. Vectorul distmin va păstra distanțele minime curente ale drumurilor de la 1 la fiecare vârf, cu respectarea regulii de a nu depăși valoarea k. Elementele listei L sunt întotdeauna ordonate după cost; deci L(cap-1) va avea cel mai mic cost. La adăugarea unui triplet (cost, nod, dist) acest triplet nu va fi efectiv inserat dacă există un element din listă cu aceeași valoare pentru nod, dar cu valorile cost și dist mai mari. După citirea tabloului M de muchii, acestea vor fi ordonate crescător după sursă și pentru fiecare iÎ{1,...,n} se identifică poziția start[i] de pe care încep muchiile cu sursa i. Ideea rezolvării se bazează pe o parcurgere pe lățime (BF) a arborelui, plecând de la lista L, având doar elementul (0,1,0). Se extrage primul element din listă (cel de pe poziția cap-1); fie el (cost, nod, dist). Vârful nu se expandează dacă dist>distmin[nod]. În caz contrar se determină vârfurile j în care se poate ajunge din nod. Se va adăuga la lista L tripletul (cost', j, dist') unde cost' = cost + costul muchiei (nod,j) alese și dist' = dist + lungimea muchiei alese, numai dacă cost' Ł k. Algoritmul se încheie când lista devine vidă. Rezultatul va fi distmin[n]. P089806: MingeaPutem considera problema ca o generalizare a problemei colorării hărților, deoarece se urmărește colorarea muchiilor prin intermediul culorilor aflate pe laturile căpăcelelor date. De aceea vom aplica metoda backtracking. Am ales varianta recursivă, deși cea nerecursivă era mai bună ca timp și ca facilitate de a opri căutarea când s-a ajuns la o soluție. Începem prin a numerota muchiile după cum urmează: Vom memora muchiile vecine fiecărei fețe în vectorul mvec(12,5). Așezarea căpăcelelor se va face în ordine pe fețele 1, 2, ..., 12. În matricea mnoi(12,5) vom memora muchiile care primesc culoare când este așezat un căpăcel pe o față. Vectorul x(30) va păstra culorile atașate muchiilor (dacă o muchie încă nu este colorată, valoarea va fi 3). Căpăcelele vor fi memorate în vectorul Placi având 5 elemente care conțin culorile muchiilor fiecărui căpăcel. În vectorul folosita(12) de tip Boolean, păstrăm starea curentă a căpăcelelor (au fost folosite sau nu). Procedura Back, apelată din programul principal prin Back(1), are următoarea formă: Úț procedură Back(k) ł Úț dacă k=13 ł ł atunci scrie_rezultat; stop ł ł altfel ł ł Úț pentru i=1,12 execută ł ł ł { încerc să pun căpăcelul i pe fața k } ł ł ł Úț dacă folosita(i) ł ł ł ł atunci ł ł ł ł altfel p Ź Placi(i) ł ł ł ł Úț pentru j=1,5 execută ł ł ł ł ł { cele 5 poziții ale căpăcelului } ł ł ł ł ł Úț dacă cont(k,p) ł ł ł ł ł ł { condiția de continuare } ł ł ł ł ł ł atunci ł ł ł ł ł ł { colorez muchiile noi la care ajung } ł ł ł ł ł ł folosita(i) Ź true ł ł ł ł ł ł x(k) Ź i ł ł ł ł ł ł Back(k+1) ł ł ł ł ł ł { "decolorez" muchiile nou colorate } ł ł ł ł ł ł folosita(i) Ź false ł ł ł ł ł Àț ł ł ł ł ł { rotește placa p } ł ł ł ł Àț ł ł ł Àț ł ł Àț ł Àț Àț Funcția de continuare cont(k,p) verifică dacă, prin plasarea căpăcelului p pe fața k, am respectat colorarea muchiilor deja colorate. Observație: Modul în care am numerotat muchiile permite reducerea volumului de calcule. Într-adevăr, se observă că vectorii caracteristici din mnoi au 1 doar pe ultimele poziții, deci în loc de mnoi era suficient să reținem (într-un vector) doar câți de 1 apar (câte muchii vor primi culori la așezarea unui căpăcel pe fața curentă). Listing MINGEA.PAS [cuprins] |