Clasa VI

Cerc
Se considera numerele 1, 2, … , N dispuse in aceasta ordine pe un cerc. Se porneste de la
numarul K. La prima etapa se marcheaza numarul curent. La a doua etapa se merge pe cerc un
pas si se marcheaza din nou numarul curent. La a treia etapa se merge pe cerc 2 pasi si se
marcheaza numarul curent. La etapa i se merge i-1 pasi pe cerc. Procesul se opreste in momentul
in care se incearca sa se marcheze a doua oara un anumit numar. Afisati in ordinea data de
algoritm numerele care vor fi marcate.

Exemplu:
N=7 K=3
Iesire: 3 4 6 2

prof. Radu Visinescu

Clasa VII

Oras
Se considera un oras in care strazile formeaza un caroiaj alcatuit din celule patrate de
latura egala cu unitatea. Centrul orasului are coordonatele (0,0), celelate intersectii avand
coordonate de forma (i, j) cu i, j numere intregi. O persoana pleca din centrul orasului si
parcurge o secventa de strazi si intersectii. Drumul persoanei este codificat printr-un sir de
lungime L de directii cu elemente din multimea {E,S,V,N}. Intersectiile vor fi desemnate prin
abscisa si ordonata lor.
Sa se determine:
a)Numarul de intersectii distincte pe care le parcurge (inclusiv cea de coordonate (0,0)).
b)Lista intersectiilor in care intra de cel putin doua ori.
c)Una din intersectiile cele mai intalnite in drumul sau(in care a intrat de cele mai multe ori).

Exemplu:

L=16
NEENVSSESENVVNEE

Iesire:
Numarul de intersectii: 12

Intersectiile parcurse de cel putin doua ori:

11
10
20
21

Cea mai intalnita:

1 1 de 3 ori

Restrictii si precizari :
1<=L<=30

prof. Radu Visinescu

Clasa X

Mutari

Consideram o tabla de joc de forma dreptunghiulara avand N linii si M coloane. Piesele

jocului se misca incepand de la o pozitie initiala aflata pe prima linie pana la o pozitie finala
aflata pe ultima linie a tablei. Este data o lista de mutari posibile sub forma unor cvadruple de
forma: x1, y1, x2, y2 cu semnificatia ca piesa situata in punctul de coordonate (x1,y1) se poate
muta in punctul de coordonate (x2,y2); in plus de fiecare data avem relatia: x1<x2 (piesele
avanseaza spre ultima linie a tablei).
Sa se determine numarul secventelor posibile(distincte) de mutari pe care le poate efectua
o piesa plecand de le un punct situat pe prima linie si ajungand la un punct situat pe ultima linie a
tablei.

Date de intrare: fisierul [Link] cu urmatoarea structura:

-pe prima linie numerele N M K semnificand numarul de linii ale tablei, numarul de coloane ale
tablei si numarul de elemente ale listei de mutari
-pe urmatoarele K linii cvadruple de forma x1 y1 x2 y2 semnificand o mutare posibila.

Date de iesire: fisierul [Link]

-pe prima linie numarul NR semnificand numarul secventelor posibile de mutari

Exemplu:

[Link]
5 9 15
1231
1223
2333
3151
3143
4353
2346
3355
4355
1536
3646
4655
1928
2949
4859

[Link]
6

Restrictii si precizari:
1<=N, M<=200 1<=K<=1000
prof. Radu Visinescu
Clasa XI-XII

Lifturi

Avem o cladire cu N nivele. In interiorul acesteia sunt un numar de M lifturi. Fiecare lift
Li face legatura intre nivelul de plecare Pi si nivelul de sosire Ui. Avem intotdeauna relatia
Pi<Ui. Initial toate lifturile se afla la nivelele lor de plecare si intotdeuna lifurile circula numai in
sus. Lifturile nu se opresc la etajele intermediare. O persoana isi propune sa plece de la nivelul 1
si sa ajunga la nivelul N, folosind cat mai putine lifturi.
Determinati (daca exista) acest numar minim de lifturi precum si un sir posibil de lifturi
care respecta acesta cerinta. Sirul va fi dat prin numerele de ordine ale lifturilor care il compun.

Date de intrare: fisierul [Link]

-pe prima linie numerele N si M separate printr-un spatiu.
-pe urmatoarele M linii perechi de valori Pi si Ui reprezentand nivelele intre care circula liftul
respectiv. Numarul de ordine al liftului este determinat de pozitia in fisier a perechii de nivele
intre care circula acesta.

Date de iesire: fisierul [Link]

-pe prima linie numarul minim de lifturi sau valoare –1 daca problema nu are solutie.
-pe a doua linie, in cazul in care exista solutii, numerele de ordine ale unei secvente posibile de
lifturi care respecta cerinta problemei, in ordinea in care persoana foloseste aceste lifturi.

Restrictii si precizari:
1<=N<=100 1<=M<=500
-daca exista mai multe solutii se va determina una singura.
-intre doua etaje pot exista mai multe lifturi.

Exemplu: [Link]

56
25
12
13
45
24
35
1 2 3 4 5 6
[Link]
2
2 1 (sau 3 6)

prof. Radu Visinescu

Oras (clasa VII)
Descriere solutie:
Se folosesc trei vectori paraleli X,Y,NR cu urmatoarea semnificatie:
X[J],Y[J] : coordonatele unei intersectii vizitate, NR[J] : numarul de vizitari respective. Vectorii
X, Y, NR se construiesc treptat in functie de valorile datelor de intrare. In pseudocod:
read (L);
K:=0; K:=K+1; X[K]:=0; Y[K]:=0;NR[K]:=1;
P:=0;Q:=0 // coordonatele orasului curent
for J:=1 to L do
{ read (D);
if (D=’E’) then P:=P+1;
else if (D=’S’) then Q:=Q-1;
else if (D=’V’) then P:=P-1;
else if (D=’N’) atunci Q:=Q+1;

OK:=false; POZ:=0;
for H:=1 to K do
if (X[H]=P) and (Y[H]=Q) then
{OK:=true; POZ:=H}
if (OK=false) then
{ K:=K+1;X[K]:=P; Y[K]:=Q; NR[K]:=1}
else NR[POZ]:= NR[POZ]+1;
}
write (K);
for J:=1 to K do
if (NR[J]>=2) then write (X[J], Y[J]);
// se calculeaza maximul din NR si se scriu coordonatele
respective din X si Y

Complexitatea algoritmului este data de instructiunile din ciclu for interior. Cum avem
relatia K<=N rezulta o complexitate de ordinul: O(N 2).
Mutari (clasa X)
Descriere solutie:
Folosim vectorii XP, YP, XF, YF pentru memorarea capatelor arcelor si o matrice auxiliata A cu
N linii si M coloane. In pseudocod:
//Se sorteaza vectorii XP,YP,XF,YF crescator dupa valorile din
vectorul XP
//Se initializeaza cu 0 matricea A.
for J:=1 to K do
if (XP[J]=1) then A[1,YP[J]]:=1;
for J:=1 to K do
A[XF[J],YF[J]]:=A[XF[J],YF[J]]+A[XP[J],YP[J]];
S:=0;
for J:=1 to M do S:=S+A[N,J];
write(‘nr=’,s);

Algoritmul are complexitatea O(max{K*log(K),N*M}). Datorita existentei relatiilor de

recurenta si a rezolvarii lor in modul bottom-up putem spune ca problema se incadreaza in
tehnica programarii dinamice.
Lift (clasa XI-XII)
Descriere solutie:
Daca L1, L2,… LK-2, LK-1, Lk este un sir optim de lifturi cu U[Lk]=N atunci L1, L2,… LK-2, LK-1 este
un sir optim pana la nivelul U[Lk-1]=P[Lk], L1, L2,… LK-2 este un sir optim de lifturi pana la nivelul
U[Lk-2] s.a.m.d.. Folosim doi vectori auxiliari: NR si PRED care memoreaza numarul minim de
lifturi respectiv predecesorul unui lift in sirul de lifturi.
In pseudocod:
//Calculul vectorilor NR si PRED
NR[1]:=0;PRED[1]:=0;
for I:=2 to N do
{MIN:=32000;
for J:=1 to I-1 do
{ for K:=1 to M do
if (P[K]=J)and(U[K]=I) then
if (MIN>NR[J])and(NR[J]>=0) then
{MIN:=NR[J]; POZ:=K;}
}
if (MIN<>32000) then
{NR[I]:=MIN+1; PRED[I]:=POZ;}
else
{NR[I]:=-1; PRED[I]:=0;}

}
end;
// Afisarea rezultatelor
if (NR[N]=-1) then write(-1)
else
{write(NR[N]);
drum(N);
}
// Procedura recursiva
algoritm drum(NIV);
{if (PRED[NIV]>0) then
{drum(P[PRED[NIV]]);
write(PRED[NIV],' ')
}
}
Algoritmul are complexitatea O(N2*M) data de cele trei cicluri for incluse. Aceasta
deoarece am memorat lifturile prin lista de muchii. Propunem refacerea algoritmului, memorand
lifurile care ajung la etajul I in lista de adiacenta a nodului I. Se cere o complexitate de O(N+M).