Problema - Labirint circular - algoritm de rezolvare

Problema 1. Labirint circular

Teste

Un algoritm de rezolvare a acestei probleme nu este foarte dificil de gasit. Totusi, implementarea, prin numarul mare de calcule de geometrie analitica, poate da nastere usor erorilor.

Ideea generala din spatele algoritmului este construirea unui graf cu nodurile puncte din plan, graf format din: centrul labirintului, capetele arcelor (iesirilor) si cercul exterior (asa cum a fost el definit in enunt). Pentru a stabili distanta dintre centru si exterior, vom aplica o metoda de determinare a drumului minim intre doua noduri (ex. algoritmul lui Dijkstra).

Prin conventie D(x,y) va reprezenta distanta directa (in labirint) dintre varfurile x si y (fara a trece prin noduri intermediare).

Prin noduri interne vom defini varfurile grafului care sunt capete ale iesirilor in labirint. Calculul distantei directe dintre doua noduri interne (x si y) presupune analizarea a doua cazuri:

a. Segmentul [x,y] nu intersecteaza nici un perete: D(x,y) coincide cu distanta in plan dintre puncte.

b. Segmentul [x,y] intersecteaza cel putin un perete: Fie C_x cercul pe care se afla varful x si C_y cercul pe care se afla varful y. Daca C_x=C_y atunci distanta dintre puncte va fi egala cu lungimea arcului de cerc determinat de x si y. Daca valorile C_x si C_y sunt distincte, putem presupune, fara a pierde din generalitate, ca raza(C_x)<raza(C_y). In acest caz, pentru a calcula D(x,y) vom determina tangentele din punctul y la cercul C_x. Daca nici una din aceste tangente nu intersecteaza un perete atunci D(x,y) va fi egal cu Lungime_Tangenta+Min(Lungime_Arc(Tan₁,x), Lungime_Arc(Tan₂,x)), unde Lungime_Tangenta este distanta dintre punctul y si punctele de tangenta la cercul C_x, distanta egala pentru ambele puncte, Lungime_Arc(a,b) este lungimea arcului determinat de punctele a si b pe cercul C_x iar Tan₁ si Tan₂ reprezinta punctele de tangenta ale punctului y la cercul C_x. Daca una dintre tangente intersecteaza cel putin un perete, distanta D(x,y) se va calcula in modul prezentat anterior fara a lua in calcul tangenta in cauza. In cazul in care ambele tangente intresecteaza pereti, drumul direct dintre cele doua puncte nu face parte din solutia optima.

Pentru determinarea distantei de la centrul labirintului la varfurile interne vom lua in considerare doar segmentele care nu intersecteaza nici un perete. Distanta directa la cercul exterior o vom calcula doar in cazul in care exista un segment care uneste centrul labirintului cu unul din punctele arcelor de pe cercul de raza maxima, segment care, ca si in celelalte situatii, nu trebuie sa intersecteze nici un perete.

Pentru stabilirea distantelor de la varfurile interne la cercul exterior se va proceda analog modului de determinare a distantei directe de la centru la exterior.

Orice alt caz nu afecteaza traseul optim.

Pentru toate perechile de varfuri interne avem de determinat intersectia cu cei N peretii. Prin urmare, complexitatea algoritmului este O(N*K²).

Problema 2. Echipa fantastica

Teste

Problema se rezolva prin metoda programarii dinamice. In Sol[J,F,M,A] vom avea valoarea maxima a unei echipe formate din F fundasi, M mijlocasi si A atacanti, folosind numai primii J jucatori. Pentru stabilirea valorilor Sol[J] avem nevoie de valorile Sol[J-1]. Astfel:

pentru m=0,4 executa
 pentru a=0,2 executa
  pentru f=1,4 executa
   Sol[j,f,m,a]=Sol[j-1,f-1,m,a]+ValoareFundas[j];

pentru f=0,4 executa
 pentru a=0,2 executa
  pentru m=1,4 executa
   Sol[j,f,m,a]=Max(Sol[j-1,f,m-1,a]+ValoareMijlocas[j],Sol[j,f,m,a]);

pentru f=0,4 executa
 pentru m=0,4 executa
  pentru a=1,2 executa
   Sol[j,f,m,a]=Max(Sol[j-1,f,m,a-1]+ValoareAtacant[j],Sol[j,f,m,a]);

pentru f=0,4 executa
 pentru m=0,4 executa
  pentru a=0,2 executa
   Sol[j,f,m,a]=Max(Sol[j,f,m,a],Sol[j-1,f,m,a]);

La sfarsitul executiei algoritmului, in Sol[N,4,4,2] vom avea solutia problemei. Pentru ca numarul de fundasi, mijlocasi si atacanti necesari este constant (4-4-2), complexitatea algoritmului va fi O(N).

Observand ca pentru obtinerea solutiilor la nivelul J avem nevoie doar de solutiile de la nivelul J-1, putem transforma structura Sol[J,F,M,A] in Sol[F,M,A], cu pretul folosirii unei variabile auxiliare, fapt care reduce necesarul de memorie de N/2 ori, scazand usor si timpul de executie.

Problema 3. Romb

Teste

Pentru rezolvarea acestei probleme propunem un algoritm intuitiv, a carui complexitate este O(N²). Vom descompune rombul in doua triunghiuri, cu baza comuna, unul orientat in sus si celalalt in jos. La randul lor, triunghiurile vor fi descompuse in segmente (blocuri compacte de valori 1, aflate pe aceeasi linie).

Prin Segment[i,j] vom defini raza celui mai mare grup compact de valori 1 aflat pe linia i, cu centrul in pozitia [i,j]. Triunghi_sus[i,j] arata raza celui mai mare triunghi orientat in sus, pentru care mijlocul bazei se afla in pozitia [i,j]. Triunghi_jos[i,j] va reprezenta raza celui mai mare triunghi orientat in jos, pentru care mijlocul bazei se afla in pozitia [i,j]. Romb[i,j] indica raza celui mai mare romb cu centrul in pozitia [i,j].

pentru i=1,N executa
 k=-1
 pentru j=1,M executa
  daca A[i,j]=1 executa
   k=k+1
  altfel
   k=-1
  sfarsit daca
  Segment[i,j]=Min(k,Min(i-1,N-i))
 sfarsit pentru
 k=-1
 pentru j=M,1,-1 executa
  daca A[i,j]=1 executa
   k=k+1
  altfel
   k=-1
  sfarsit daca
  Segment[i,j]=Min(k,Segment[i,j]);
 sfarsit pentru
sfarsit pentru

pentru j=1,M executa
 Triunghi_sus[1,j]=Segment[1,j]
pentru i=2,N executa
 pentru j=1,M executa
  Triunghi_sus[i,j]=Min(Triunghi_sus[i-1,j]+1,Segment[i,j])

pentru j=1,M executa
 Triunghi_jos[N,j]=Segment[N,j]
pentru i=N-1,1,-1 executa
 pentru j=1,M executa
  Triunghi_jos[i,j]=Min(Triunghi_jos[i+1,j]+1,Segment[i,j])

pentru i=1,N executa
 pentru j=1,M executa
  Romb[i,j]=Min(Triunghi_jos[i,j],Triunghi_sus[i,j])

Solutia va fi reprezentata de valoarea maxima din matricea Romb.

Problema 4. Flori pentru aniversare

Teste

Pentru rezolvarea acestei probleme vom avea nevoie de un algoritm de drum minim. Data fiind structura grafului in care se cere determinarea drumurilor minime, o metoda indicata este algoritmul lui Lee.

Vom construi doua matrice: V si A. Matricea V va contine lungimea drumului minim de la punctul de plecare al lui Vasilica la orice alt punct de pe harta orasului, in timp ce matricea A va indica lungimea drumului minim de la destinatia lui Vasilica (aniversarea) la orice alt punct de pe harta. Nu vom insista asupra modului de obtinere a valorilor din matricele A si V, deoarece algoritmul necesar este usor de implementat in cazul de fata.

Pentru constructia solutiei optime se va analiza fiecare punct de pe harta. Astfel:

Cost_Minim=Suma_Initiala pentru i=1,N executa
 pentru j=1,N executa
  Timp=A[i,j]+V[i,j]-1;
  daca Timp<=Timp_Disponibil executa
   Cost=Timp*10+Cost_Flori(i,j);    daca Cost<Cost_Minim executa
    Cost_Minim=Cost;
   sfarsit daca
  sfarsit daca
 sfarsit pentru
sfarsit pentru

La sfarsitul algoritmului Cost_Minim va indica solutia optima a problemei. Complexitatea algoritmului este O(N²).

Problema 5. Subsir de numere prime

Teste

Rezolvarea acestei probleme se realizeaza prin implementarea algoritmului clasic de determinare a subsirului crescator de lungime maxima, algoritm ce are complexitatea O(N²). Desi exista algoritmi ce se executa in O(N*log(N)), dimensiunea datelor permite implementarea metodei standard. Pentru a avea un timp de executie mai bun, este necesara filtrarea sirului initial astfel incat acesta sa contina doar numerele prime. Complexitatea algoritmului de filtrare este O(N*Val_Max^1/2), Val_Max^1/2 reprezentand estimarea numarului de operatii ale unui test de primalitate pentru valori din intervalul [2,Val_Max]. Elementele sirului sunt limitate superior (la valoarea 30000) si, prin urmare, Val_Max este o constanta. De aici rezulta ca algoritmul de filtrare are complexitatea O(N), neafectand complexitatea generala de O(N²).

Algoritmul de rezolvare este urmatorul:

Eliminate=0;
pentru i=1,N executa
 daca Este_Prim(S[i]) executa
  S[i-Eliminate]=S[i]
 altfel
  Eliminate=Eliminate+1
 sfarsit daca
sfarsit pentru
N=N-Eliminate

pentru i=1,N executa
 Subsir_Maxim[i]=0
 pentru j=1,i-1 executa
  daca (S[i]>S[j]) si (Subsir_Maxim[j]>Subsir_Maxim[i]) executa
   Subsir_Maxim[i]=Subsir_Maxim[j]
  sfarsit daca
 sfarsit pentru
 Subsir_Maxim[i]=Subsir_Maxim[i]+1
sfarsit pentru

Pentru determinarea lungimii maxime a unui subsir cu specificatiile enuntate vom cauta valoarea maxima a elementelor din variabila Subsir_Maxim. Deoarece reconstituirea solutiei este facila, nu vom insista asupra acestui aspect.