SOLUŢIILE problemelor propuse

Ce î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ătrate

Fiecărui al i-lea pătrat i se vor asocia două variabile de tip articol P_i şi Q_i 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 P_iQ_i. Este evident că Q_i.x=P_i.x+lung_i, iar Q_i.y=P_i.y-lung_i, unde lung_i este lungimea laturii pătratului.

Mai observăm că distanţa de la origine la un segment P_iQ_i este (P_i.x+P_i.y)/. Observaţia se bazează pe faptul că segmentul P_iQ_i 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 P_i.x+P_i.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 P_iQ_i descrescător după pantele lui OP_i.

Considerăm pe rând segmentele P_iQ_i, 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 P_iQ_i un astfel de segment. Fie R' punctul curent de pe P_iQ_i cu proprietatea că P_iR' este obturată de segmentele P_jQ_j analizate până la acest moment de timp; iniţial R'=P_i. Deoarece ne interesează numai panta lui OR', vom memora în loc de R' puncte R care sunt actualizate cu anumite puncte Q_j. Atunci pentru segmentul P_iQ_i vom efectua următoarele calcule:

R Ź P_i

Úţ pentru j=1,n execută

ł Úţ dacă distanţa de la O la P_iQ_i este mai mică decât

ł ł cea de la O la P_jQ_j

ł ł atunci {segmentul P_iQ_i nu poate fi obturat de P_jQ_j}

ł ł altfel

ł ł Úţ dacă panta lui OR este cuprinsă între panta lui OQ_j

ł ł ł şi cea a lui OP_j, adică dreapta OR taie

ł ł ł segmentul P_jQ_j (vezi figura)

ł ł ł atunci R Ź Q_j

ł ł Ŕţ

ł Ŕţ

Ŕţ

Úţ dacă panta lui OQ_i < panta lui OR

ł atunci n_viz Ź n_viz+1

Ŕţ

Ajungem astfel la următorul program:

Listing SQUARES.PAS

P089802: Cărţi de joc

Fie 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:

• n este impar (1)
• modul în care a fost construită permutarea p de la care s-a plecat. (2)

De exemplu (2) arată că permutarea iniţială p nu este oarecare, ci are proprietatea pⁿ=e_n, unde e_n 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 2^s să dea tocmai q.

Să observăm că (2^s,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: 2^su=1 (mod n).

Fie t restul împărţirii lui 2^s 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ă 2^su=k*n+1 pentru un anumit k natural. Deci trebuie determinată permutarea p de grad n care ridicată la puterea 2^su să fie egală cu q^u, adică p=q^u .

Suntem conduşi astfel la următorul program:

Listing CARDS.PAS 

P089803: Reduceri

Fie 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:

r₁a₁+r₂a₂+...+r_na_n=t şi r₁,r₂,...,r_nÎ{-1,1} (1)

Fie a₁+a₂+...+a_n=sum. Prin adunare cu relaţia (1) obţinem:

s₁a₁+s₂a₂+...+s_na_n=t+sum cu s₁,s₂,...,s_nÎ{0,2}.

Cum r₁=1 şi r₂=-1, rezultă că s₁=2, s₂=0 şi că urmează să determinăm s₃,...,s_nÎ{0,2} având proprietatea:

s₃a₃+...+s_na_n=scop, unde scop=t+sum-2a₁

şi cu precizarea că s_i va fi 0 dacă şi numai dacă r_i este -1.

În continuare vom calcula sumele posibile:

s₃a₃+... +s_na_n ş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'+a_i şi v' atinsă.

În acest mod va fi posibilă identificarea acelor elemente a_i 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 = a₁- ... ?a_i+a_i+1+...+a_i+k-a_i+k+1-...-a_n

atunci efectuând k reduceri pe poziţia i obţinem:

t = a₁- ... ?b_i-a_i+k+1-...-a_n

cu b_i=(...((a_i-a_i+1)-a_i+2)-...a_i+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.

Listing REDUCERI.PAS

P089804: Soldaţi

Etapa 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 y₁ Ł y₂ Ł ... Ł y_n. 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 y₁ şi y_n. Este clar că suma distanţelor lor la y=yf este minimă dacă drept yf luăm oricare număr întreg din intervalul [y₁,y_n]; suma minimă va fi y_n-y₁, oricare ar fi yf astfel ales.

Continuăm cu perechea y₂, y_n-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 [y₂,y_n-1] şi că în acest caz suma va fi y_n-1-y₂.

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 x₁,x₂,...,x_n 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 x_i cu x_i-i şi vom obţine sortare valoarea xf căutată. Acum efortul de a aduce valorile x₁,x₂,...,x_n pe poziţiile xf+1,xf+2,?,xf+n se poate calcula imediat ca fiind suma valorilor |xf-(xinit_i-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:

Listing SOLDATI.PAS

P089805: Şosele

Reformulă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:

• nod = vârful curent la care s-a ajuns (plecând de la 1);
• cost = taxa care a trebuit plătită pe drumul prin care s-a ajuns la nod;
• dist = lungimea drumului prin care s-a ajuns la nod.

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].

Listing SOSELE.PAS

P089806: Mingea

Putem 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]