olimpiada republicană la informatică ediţia 2010 moldova

Ministerul Educaţiei al Republicii Moldova

Olimpiada Republicană la Informatică

Ediţia 2010

Chişinău 2010

2

Olimpiada Republicană la Informatică. Ediţia 2010.

Lucrarea conţine problemele propuse la Olimpiada Republicană la Informatică a elevilor, ediţia 2010. Pentru

fiecare problemă sunt descrise algoritmul şi soluţia respectivă în limbajul de programare PASCAL.

Materialele Olimpiadei pot fi de un real folos la studierea Informaticii atât elevilor, cât şi profesorilor de

Informatică.

La elaborarea ediţiei au contribuit:

Anatol Gremalschi, doctor habilitat, profesor universitar, UTM

Ion Bolun, doctor habilitat, profesor universitar, ASEM

Iurie Mocanu, Ministerul Educaţiei

Viorel Afteni Ministerul Educaţiei

Dumitru Codreanu, Universitatea Bucureşti

Dumitru Ciubatîi, Universitatea Bucureşti

Bogdănaş Denis Universitatea Tehnică, Iaşi

Constantin Dolghieru, Universitatea Politehnică, Bucureşti

3

Cuprins

CLASELE 7 9 .................................................................................................................... 4

EXPRESII .................................................................................................................................... 5 IEPURAŞII ................................................................................................................................... 7 SEGMENTE ............................................................................................................................... 11 PĂTRATE .................................................................................................................................. 15 NUMERE .................................................................................................................................. 17 LUPTA MARITIMĂ ...................................................................................................................... 19

CLASELE 10 12 .............................................................................................................. 22

VÂSLAŞII .................................................................................................................................. 23 IEPURAŞII ................................................................................................................................. 26 SEGMENTE ............................................................................................................................... 30 ŞARPELE .................................................................................................................................. 35 DESCOMPUNERI ........................................................................................................................ 39 RADIOUL .................................................................................................................................. 42

4

Clasele 7 9

Denumirea

problemei

Numărul de

puncte alocat

problemei

Denumirea

fişierului sursă

Denumirea

fişierului de

intrare

Denumirea

fişierului de

ieşire

Expresii 100 EXPRES.PAS

EXPRES.C

EXPRES.CPP

EXPRES.IN EXPRES.OUT

Iepuraşii 100 IEPURE.PAS

IEPURE.C

IEPURE.CPP

IEPURE.IN IEPURE.OUT

Segmente 100 SEGMENT.PAS

SEGMENT.C

SEGMENT.CPP

SEGMENT.IN SEGMENT.OUT

Pătrate 100 PATRAT.PAS

PATRAT.C

PATRAT.CPP

PATRAT.IN PATRAT.OUT

Numere 100 NUMERE.PAS

NUMERE.C

NUMERE.CPP

NUMERE.IN NUMERE.OUT

Lupta maritimă 100 LUPTA.PAS

LUPTA.C

LUPTA.CPP

LUPTA.IN LUPTA.OUT

Total 600 - - -

5

Expresii

Se consideră expresiile booleene de forma:

A <s1> B <s2> C <s3> D = Q

unde A, B, C, D şi Q sunt numere întregi fără semn, iar s1, s2 şi s3 operatorii aritmetici

+, - .

Exemple:

571734612 ;

6392645128 ;

2164221 .

Sarcină. Elaboraţi un program care, cunoscând valorile numerelor A, B, C, D şi Q,

selectează, dacă-i posibil, operatorii s1, s2 şi s3 în aşa mod, încât expresia booleană

A <s1> B <s2> C <s3> D = Q

să ia valoarea de adevăr true.

Date de intrare. Fişierul text EXPRES.IN conţine pe o singură linie numerele întregi

A, B, C, D şi Q, separate prin spaţiu.

Date de ieşire. Fişierul text EXPRES.OUT va conţine pe o singură linie un şir format din

operatorii s1, s2 şi s3. Dacă problema admite mai multe soluţii, în fişierul de ieşire se va scrie

doar una, oricare din ele. Dacă problema nu are soluţie, în fişierul de ieşire se va scrie şirul de

caractere ???.

Exemplu1 1.


2 6 34 17 47 -++

Exemplu1 2.


8 12 45 9 26 ???

Restricţii. 910,,,0 DCBA . Timpul de execuţie nu va depăşi 0,1 secunde.

Programul va folosi cel mult 32 Megaocteţi de memorie operativă. Fişierul sursă va avea

denumirea EXPRES.PAS, EXPRES.C sau EXPRES.CPP.

Rezolvare

Conform restricţiilor problemei, 910,,,0 DCBA . Prin urmare, pentru a evita

erorile de depăşire, variabilele A, B, C, D şi Q trebuie declarate cu tipul de date longint.

Program ExpresiiBooleene;

{ Clasele 07-09 }

var Intrare, Iesire : text;

A, B, C, D, Q : longint;

S : string;

6

begin

{ citirea datelor de intrare }

assign(Intrare, 'EXPRES.IN');

reset(Intrare);

readln(Intrare, A, B, C, D, Q);

close(Intrare);

{ deschiderea fisierului de iesire }

assign(Iesire, 'EXPRES.OUT');

rewrite(Iesire);

S:='???';

if(A+B+C+D=Q) then S:='+++';

if(A+B+C-D=Q) then S:='++-';

if(A+B-C+D=Q) then S:='+-+';

if(A+B-C-D=Q) then S:='+--';

if(A-B+C+D=Q) then S:='-++';

if(A-B+C-D=Q) then S:='-+-';

if(A-B-C+D=Q) then S:='--+';

if(A-B-C-D=Q) then S:='---';

{ scrierea datelor de iesire }

writeln(Iesire, S);

close(Iesire);

end.

7

Iepuraşii

În cartea sa Liber Abaci (Cartea Abacului), editată în anul 1202, marele matematician

Fibonacci (cunoscut şi sub numele Leonardo Pisano) a rezolvat „problema înmulţirii

iepuraşilor”, care constă în calcularea numărului de iepuraşi într-o populaţie ce evoluează

pornind de la o pereche iniţială. Conform acestei cărţi, dezvoltarea populaţiei de iepuraşi se

descrie cu ajutorul şirului 1, 1, 2, 3, 5, 8, 13, ... , denumit şirul lui Fibonacci. Formal, acest şir

se defineşte cu ajutorul următoarelor formule:

11 F , 12 F , 23 F , 34 F , ..., 11 iii FFF , ... ,

unde Fi reprezintă numărul de perechi de iepuraşi în luna i.

Sarcină. Elaboraţi un program care calculează suma S a primelor n numere din şirul lui

Fibonacci.

Date de intrare. Fişierul text IEPURE.IN conţine pe o singură linie numărul întreg n.

Date de ieşire. Fişierul text IEPURE.OUT va conţine pe singură linie numărul întreg S.

Exemplu.


4 7

Restricţii. 3002 n . Timpul de execuţie nu va depăşi 0,5 secunde. Programul va

folosi cel mult 32 Megaocteţi de memorie operativă. Fişierul sursă va avea denumirea

IEPURE.PAS, IEPURE.C sau IEPURE.CPP.

Rezolvare

În general, problema nu prezintă dificultăţi de algoritmizare, întrucât suma S poate fi

calculată printr-o singură parcurgere a şirului lui Fibonacci. Mai mult ca atât, nu este necesară

nici memorarea întregului şir, întrucât numărul curent poate fi calculat prin însumarea doar a

celor două numere precedente din şir.

Prin F1, F2 şi F3 vom nota oricare trei numere consecutive din şirul lui Fibonacci.

Evident, suma S poate fi calculată cu ajutorul următoarei secvenţe de algoritm:

F1:=1;

F2:=1;

S:=F1;

i:=2;

repeat

S:=S+F2;

F3:=F1+F2;

F1:=F2;

F2:=F3;

i:=i+1;

until i>n;

Implementând această secvenţă cu ajutorul declaraţiilor de variabile

var S, F1, F2, F3 : integer;

8

prin experimente de calcul ne convingem, că începând cu 20n , la calcularea valorilor

variabilelor în studiu au loc erori de depăşire.

Cei care cunosc alte tipuri de date, ar putea să încerce declaraţia

var S, F1, F2, F3 : longint;

din Turbo Pascal sau tipurile de date Longword, Int64, Qword din Object Pascal. Însă şi în

astfel de cazuri, pentru valorile mari ale lui n apar erori de depăşire.

Pentru a evita erorile de depăşire, vom reprezenta numerele mari S, F1, F2 şi F3 prin

tablouri, formate din K elemente. Fiecare element al tabloului memorează câte o cifra a

numărului respectiv.

Dacă în procesul adunării a două numere mari A şi B, formate din câte K cifre,

transportul calculat în cazul însumării cifrelor A[1], B[1] şi transportului din rangul precedent

diferă de zero, are loc o depăşire şi programul va semnaliza o eroare.

În programul ce urmează, pentru a realiza experimentul de calcul, în componenţa

procedurii Adunare a fost inclusă următoarea secvenţă de instrucţiuni:

if Transport=1 then

begin

writeln('Depasire');

readln;

end;

Evident, în condiţiile problemei, această secvenţă de instrucţiuni nu va fi executată nici

o dată numai atunci, când valoarea lui K va fi stabilită suficient de mare. Această valoare

poate fi determinată cu ajutorul experimentelor de calcul, atribuindu-i lui n valoarea limită

300n , aşa cum este indicat în restricţiile problemei.

Program Iepurasii;

{ Clasele 07-09 }

const K = 70; { numarul de cifre ale numerelor foarte mari }

type Cifra = 0..9;

Numar = array[1..K] of Cifra;

var n : integer;

S : Numar;

procedure Citeste;

{ Citeste numarul n din fisierul de intrare }

var Intrare : text;

begin

assign(Intrare, 'IEPURE.IN');

reset(Intrare);

readln(Intrare, n);

close(Intrare);

end; { Citeste }

procedure Scrie;

{ Scrie suma S in fisierul de iesire }

var Iesire : text;

j : integer;

1 2 3 ... K

9

begin

assign(Iesire, 'IEPURE.OUT');

rewrite(Iesire);

j:=1;

while S[j]=0 do j:=j+1;

while j<=K do

begin

write(Iesire, S[j]);

j:=j+1;

end; { while }

writeln(Iesire);

close(Iesire);

end; { Scrie }

procedure Unu(var A : Numar);

{ Atribuie numarului A valoarea 1 }

var j : integer;

begin

for j:=1 to K-1 do A[j]:=0;

A[K]:=1;

end; { Unu }

procedure Adunare(A, B : Numar; var C : Numar);

{ Calculeaza suma C:=A+B }

var Transport : Cifra;

j : integer;

q : 0..19;

begin

Transport:=0;

for j:=K downto 1 do

begin

q:=A[j]+B[j]+Transport;

if q<=9 then Transport:=0

else

begin

Transport:=1;

q:=q-10;

end;

C[j]:=q;

end; { for }

if Transport=1 then

begin


readln;

end;

end; { Adunare }

procedure Suma;

var i : integer;

F1, F2, F3 : Numar;

begin

Unu(F1);

Unu(F2);

S:=F1;

i:=2;

repeat

Adunare(F2, S, S);

Adunare(F1, F2, F3);

F1:=F2;

F2:=F3;

i:=i+1;

until i>n;

end; { Suma }

10

begin

Citeste;

Suma;

Scrie;

end.

Întrucât suma S se calculează printr-o singură parcurgere a şirului lui Fibonacci,

complexitatea temporală a programului este )(nKO . Conform restricţiilor problemei,

300n , iar 70K . Evident, pentru astfel de valori, timpul de execuţie al programului va fi

cu mult mai mic decât 0,5 secunde.

11

Segmente

Se consideră mulţimea S, formată din n segmente distincte, notate prin S1, S2, ..., Si, ...,

Sn. Fiecare segment Si este definit prin coordonatele întregi carteziene ),( ii yx , ),( ii yx ale

extremităţilor sale.

Segmentele Si, Sj se numesc

adiacente, dacă ele au o extremitate

comună.


conectate dacă există o succesiune

de segmente, care începe cu Si şi se

termină cu Sj şi în care oricare două

segmente consecutive sunt

adiacente.

De exemplu, segmentele S1, S5

de pe figura alăturată sunt conectate

întrucât există o succesiune de

segmente consecutiv adiacente: S1,

S3, S5.

Submulţimea de segmente Q, Q S, formează o reţea, dacă segmentele respective sunt

conectate între ele, fără a avea însă conexiuni cu segmentele din submulţimea S \ Q.

În general, mulţimea de segmente S poate avea mai multe reţele.

De exemplu, mulţimea de segmente de pe figura de mai sus conţine 3 reţele: {S1, S2, S3,

S5}, {S4} şi {S6, S7}.

Sarcină. Elaboraţi un program, care, cunoscând mulţimea de segmente S, calculează

numărul de reţele k.

Date de intrare. Fişierul text SEGMENT.IN conţine pe prima linie numărul întreg n.

Fiecare din următoarele n linii ale fişierului de intrare conţine numerele întregi iiii yxyx ,,, ,

separate prin spaţiu. Linia 1i a fişierului de intrare conţine coordonatele extremităţilor

segmentului Si.

Date de ieşire. Fişierul text SEGMENT.OUT va conţine pe singură linie numărul întreg k.

Exemplu.


7

1 7 4 8

2 6 4 8

4 8 7 4

2 4 9 7

5 2 7 4

8 3 11 8

8 3 13 1

3

Restricţii. 2501 n ; 00032,,,00032 iiii yxyx . Timpul de execuţie nu va

depăşi 1,5 secunde. Programul va folosi cel mult 32 Megaocteţi de memorie operativă.

Fişierul sursă va avea denumirea SEGMENT.PAS, SEGMENT.C sau SEGMENT.CPP.

12

Rezolvare

Vom construi consecutiv fiecare din eventualele reţele după cum urmează:

1. Iniţial, stabilim }{: 1SQ şi }{\: 1SSS .

2. Examinând fiecare segment din mulţimea S, le selectăm pe cele conectate cu

segmentele din Q şi le trecem din S în Q. Dacă astfel de segmente nu mai există,

s-a obţinut o reţea.

3. În continuare, stabilim }{: iSQ , unde Si este unul din segmentele rămase în

mulţimea S şi construim din nou o eventuală reţea.

4. Procesul de construire a reţelelor se termină atunci, când mulţimea S devine una

vidă.

În programul ce urmează coordonatele extremităţilor de segmente se memorează în

tablourile X1, Y1, X2, Y2. Adiacenţa segmentelor se verifică cu ajutorul funcţiei booleene

SuntAdiacente, iar conectivitatea segmentelor din mulţime S cu cele din mulţimea Q − cu

ajutorul funcţiei booleene EsteConectat.

Program Segmente;

{ Clasele 07-09 }

const nmax=250; { numarul maximal de segmente }

type Segment=1..nmax;

var Q, S : set of Segment;

X1, Y1, X2, Y2 : array [1..nmax] of integer;

n : 1..nmax; { numarul de segmente }

k : 0..nmax; { numarul de retele }

procedure Citeste;

var i : 1..nmax;

Intrare : text;

begin

assign(Intrare, 'SEGMENT.IN');

reset(Intrare);

readln(Intrare, n);

for i:=1 to n do

readln(Intrare, X1[i], Y1[i], X2[i], Y2[i]);

close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'SEGMENT.OUT');

rewrite(Iesire);

writeln(Iesire, k);

close(Iesire);

end; { Scrie }

function SuntAdiacente(i, j : Segment) : boolean;

{ returneaza true daca segmentele i, j sunt adiacente }

begin

SuntAdiacente := ((X1[i]=X1[j]) and (Y1[i]=Y1[j])) or

((X1[i]=X2[j]) and (Y1[i]=Y2[j])) or

((X2[i]=X1[j]) and (Y2[i]=Y1[j])) or

((X2[i]=X2[j]) and (Y2[i]=Y2[j]));

end; { SuntAdiacente }

13

function EsteConectat(i : Segment) : boolean;

{ returneaza true daca segmentul i este conectat cu segmentele din Q }

label 1;

var j : Segment;

begin

EsteConectat := false;

for j:=1 to n do

if j in Q then

begin

if SuntAdiacente(i, j) then

begin

EsteConectat := true;

goto 1;

end; { if }

end; { if }

1: end; { EsteConectat }

procedure NumaraRetele;

label 2;

var i, j : Segment;

Indicator : boolean;

begin

{ formam multimea de segmente S }

S:=[];

for i:=1 to n do S:=S+[i];

k:=0;

{ numaram retelele }

repeat

k:=k+1;

{ includem in multimea Q un segment din S }

for i:=1 to n do

if i in S then

begin

Q:=[i];

S:=S-[i];

goto 2;

end; { if }

2: { includem in Q segementele conexe din S }

repeat

Indicator:=true;

for i:=1 to n do

if i in S then

begin

if EsteConectat(i) then

begin

Q:=Q+[i];

S:=S-[i];

Indicator:=false;

end; { if }

end; { if }

until Indicator;

until S=[];

end; { NumaraRetele }

begin

Citeste;

NumaraRetele;

Scrie;

end.

Din analiza procedurii NumaraRetele rezultă că numărul de operaţii cerut de algoritm

este de ordinul 3n . Conform restricţiilor problemei, 2501 n . Prin urmare, numărul

14

necesar de operaţii va fi de ordinul 810 , mărime comparabilă cu capacitatea de prelucrare a

calculatoarelor din laboratorul de informatică.

15

Pătrate

Delia a decis sa taie o foaie dreptunghiulară, liniata in pătrăţele, dimensiunile căreia

sunt mn pătrăţele, în bucăţi pătrate după cum urmează:

1) iniţial, efectuând o singură tăietură pe una din liniile caroiajului, ea taie din foaie o

bucată de formă pătrată de dimensiuni maximal posibile;

2) în continuare, din fragmentul dreptunghiular rămas de foaie, efectuând o singură

tăietură pe una din liniile caroiajului, Delia taie din nou o bucată de formă pătrată de

dimensiuni maximal posibile ş.a.m.d.;

3) procesul de tăiere continuă până când fragmentul rămas de foaie va fi de formă

pătrată.

Pentru exemplificare, pe desenul de mai jos, prin literele A, B, C, D şi E sunt notate cele

cinci pătrate, obţinute în rezultatul tăierii.

Sarcină. Elaboraţi un program care, cunoscând dimensiunile n şi m ale foii

dreptunghiulare, calculează câte bucăţi k de formă pătrată va obţine Delia.

Date de intrare. Fişierul text PATRAT.IN conţine pe o singură linie numerele întregi n

şi m, separate prin spaţiu.

Date de ieşire. Fişierul text PATRAT.OUT va conţine pe singură linie numărul întreg k.

Exemplu.

PATRAT.IN PATRAT.OUT

5 8 5

Restricţii. 50000,1 mn . Timpul de execuţie nu va depăşi 1 secundă. Programul va


PATRAT.PAS, PATRAT.C sau PATRAT.CPP.

Rezolvare

Procesul de tăiere poate fi simulat cu ajutorul următoarelor operaţii:

1) selectam latura mai mare a foii;

2) micşorarea dimensiunii acestei laturi cu valoare laturii mai mici a foii;

3) continuăm procesul până când ambele laturi ale foii vor avea aceleaşi dimensiuni.

Întrucât numerele n, m şi k din enunţul problemei pot lua valori mai mari decât

constanta predefinită MaxInt, în programul ce urmează ele sunt declarate cu tipul longint.

Pătratele obţinute în rezultatil tăierii Foaia iniţială

1 2 3 4 5 6 7 8

1

2

3

4

5

1 2 3 4 5 6 7 8

1

2

3

4

5

A B

C D

E

16

Program Patrate;

{ Clasele 07-09 }

var

n, m, k : longint;

Intrare, Iesire : text;

begin


assign(Intrare, 'PATRAT.IN');

reset(Intrare);

readln(Intrare, n, m);

close(Intrare);

{ calcularea numarului de patrate }

k:=1;

while n<>m do

begin

if n>m then n:=n-m else m:=m-n;

k:=k+1;

end; { while }

{ scrierea datelor de iesire }

assign(Iesire, 'PATRAT.OUT');

rewrite(Iesire);

writeln(Iesire, k);

close(Iesire);

end.

Numărul de iteraţii din instrucţiunea while nu poate depăşi valoare mn , care,

conform restricţiilor problemei este de ordinul 1010

, mărime comparabilă cu capacitatea de

prelucrare a calculatoarelor moderne. Prin urmare, timpul de calcul va fi mai mic decât 1

secundă.

17

Numere

Se consideră o mulţime finită, elementele căreia sînt numere naturale mai mici ca

32700. Scrieţi un program, care selectează din această mulţime numerele prime.

Date de intrare.

Fişierul text NUMERE.IN conţine pe fiecare linie câte un număr natural.

Date de ieşire.

Fişierul text NUMERE.OUT va conţine pe fiecare linie cuvîntul DA dacă numărul natural

din linia respectivă a fişierului de intrare este un număr prim şi NU în caz contrar.

Exemplu. NUMERE.IN NUMERE.OUT

41

4

53

DA

NU

DA

Restricţii. Fişierul de intrare NUMERE.IN conţine cel mult 100 de linii. Timpul de

execuţie nu va depăşi 0.5 secunde. Fişierul sursă va avea denumirea NUMERE.PAS,

NUMERE.C sau NUMERE.CPP.

Rezolvare

Conform definiţiei, numărul i, i 2, este prim dacă el se împarte fără rest numai la 1 şi

la el însuşi. Această definiţie poate fi aplicată direct împărţind numărul i la 2, 3, 4, ..., (i div

2). Evident, timpul cerut de un astfel de algoritm T i. Luînd în considerare faptul că valoarea

maximă a numărului i este 32700, iar fişierul de intrare conţine cel mult 100 de numere,

timpul de execuţie T 32700 100 3 106. Intrucît capacitatea de prelucrare a calculatorului

personal este de ordinul 109 instrucţiuni pe secundă, timpul de execuţie T va fi mai mic ca 0,5

secunde.

Program Numere;

{ Clasele 07-09 }

var i : integer;

Finput, Foutput : text;

function EsteNumarPrim(i : integer) : string;

{ Returneaza DA daca numarul i este prim si NU in caz contrar }

label 1;

var j : integer;

begin

EsteNumarPrim:='DA';

if (i=0) or (i=1) then

begin

EsteNumarPrim:='NU';

goto 1;

end;

for j:=2 to (i div 2) do

if (i mod j)=0 then

begin

EsteNumarPrim:='NU';

18

goto 1;

end;

1: end; { EsteNumarPrim }

begin

assign(Finput, 'NUMERE.IN');

assign(Foutput, 'NUMERE.OUT');

reset(Finput);

rewrite(Foutput);

while not eof(Finput) do

begin

readln(Finput, i);

writeln(Foutput, EsteNumarPrim(i));

end;

close(Finput);

close(Foutput);

end.

19

Lupta maritimă

În cunoscutul joc „Lupta maritimă”, acţiunea are loc pe o foaie de hârtie, liniată în

pătrăţele, cu dimensiunile m rânduri şi n coloane. Pe câmpul de joc se pot afla corăbii

distincte de formă arbitrară. Fiecare corabie reprezintă o figură conexă (figura se numeşte

conexă dacă din orice pătrăţel al ei se poate ajunge la oricare alt pătrăţel din componenţa

acesteia, deplasarea din pătrăţelul curent în unul din cele patru pătrăţele vecine efectuându-se

prin latura comună). Oricare două corăbii nu au puncte comune şi nu se ating la colţuri (vezi

desenul din exemplu).

În procesul jocului, fiecare din corăbii se poate afla în una din următoarele trei stări:

dacă în corabie nu s-a „nimerit” nici o dată, ea se consideră „vie”;

dacă în fiecare din pătrăţelele din componenţa unei corabii s-a „nimerit”, ea se

consideră “ucisă”;

în caz contrar corabia se consideră „rănită”.

Sarcină. Elaboraţi un program care calculează numărul corăbiilor „vii”, numărul

corăbiilor „ucise” şi numărul corăbiilor „rănite”.

Date de intrare. Fişierul text LUPTA.IN conţine pe o singură linie numerele întregi m

şi n, separate prin spaţiu. Fiecare din următoarele m linii ale fişierului de intrare conţine câte n

numere întregi, separate prin spaţiu. Aceste numere pot lua următoarele valori:

0 –acest pătrăţel nu aparţine nici la o corabie (este apă);

1 – acest pătrăţel aparţine unei corăbii, dar în el nu s-a „nimerit”;

-1 – acest pătrăţel aparţine unei corăbii şi în el s-a „nimerit”.

Date de ieşire. Fişierul text LUPTA.OUT va conţine pe singură linie trei numere întregi,

separate prin spaţiu: numărul de corăbii „vii”, numărul de corăbii „ucise” şi numărul de

corăbii „rănite”.

Exemplu.

LUPTA.IN LUPTA.OUT

7 8

0 0 1 0 -1 -1 0 1

1 0 0 0 0 0 0 0

1 0 1 1 1 1 1 0

-1 0 1 0 0 0 1 0

0 0 1 1 1 -1 1 0

1 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

3 1 2

Restricţii. 25,1 nm . Timpul de execuţie nu va depăşi 0,1 secunde. Programul va


LUPTA.PAS, LUPTA.C sau LUPTA.CPP.

Rezolvare

Din analiza enunţului problemei se observă că operaţia de bază, ce trebuie efectuată de

mai multe ori, constă în determinarea tuturor pătrăţelelor, care formează o corabie. Această

operaţie poate fi făcută recursiv după cum urmează.

Presupunem că pătrăţelul curent (x, y) aparţine unei corăbii. În procesul de analiză a

pătrăţelului curent, în funcţie de valoarea respectivă, vom incrementa unul din contoarele k1

20

(nu s-a nimerit) sau k2 (s-a nimerit). Pentru a exclude pătrăţelul curent din analizele ulterioare,

înscriem în el valoarea „0”.

În continuare, vom analiza recursiv pătrăţelul de sus (x-1, y), cel din dreapta (x, y+1),

cel din stânga (x, y-1) şi cel de jos (x+1, y).

După parcurgerea tuturor pătrăţelelor din componenţa unei corăbii, în funcţie de valorile

k1 şi k2, incrementăm unul din contoarele t1 (vii), t2 (ucise) sau t3 (rănite).

Pentru a evita verificările de la marginile câmpului de joc, în programul ce urmează el

este încadrat în zerouri.

Program LuptaMaritima;

{ Clasele 07-09 }

const

mmax=25; nmax=25;

{ tablouri ce defines coordonatele patratelelor vecine }

dx : array [1..4] of integer = (-1, 1, 0 ,0);

dy : array [1..4] of integer = (0, 0, -1 ,1);

var

A : array [0..mmax+1, 0..nmax+1] of integer; { campul de joc }

m, n : integer; { dimensiunile curente ale campului de joc }

t1, t2, t3 : integer;

{ numarul de corabii: t1 - vii; t2 - ucise; t3 - ranite }

k1, k2 : integer;

{ k1 - numarul patratelelor in care nu s-a nimerit }

{ k2 - numarul patratelilor in care s-a nimerit }

procedure Citeste;

var i, j : integer;

Intrare : text;

begin

assign(Intrare, 'LUPTA.IN');

reset(Intrare);

readln(Intrare, m, n);

{ formam cadrul de zerouri al campului de joc }

for i:=0 to m+1 do A[i, 0]:=0; { marginea stanga }

for j:=0 to n+1 do A[0, j]:=0; { marginea de sus }

for j:=0 to n+1 do A[m+1, j]:=0; { marginea de jos }

for i:=0 to m+1 do A[i, n+1]:=0; { marginea dreapta }

{ citim patratelele din fisierul de intrare }

for i:=1 to m do

begin

for j:=1 to n do

read(Intrare, A[i, j]);

readln(Intrare);

end; { for }

close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'LUPTA.OUT');

rewrite(Iesire);

writeln(Iesire, t1, ' ', t2 , ' ', t3);

close(Iesire);

end; { Scrie }

procedure Corabie(x, y : integer);

{ Exploreaza patratelele unei corabii }

var i : integer;

begin

if (A[x, y] <> 0) then

21

begin

{ patratelul apartine corabiei }

if (A[x,y]=1) then k1:=k1+1

else k2:=k2+1;

A[x, y]:=0;

{ analizam patratelele vecine }

for i:=1 to 4 do

Corabie(x+dx[i], y+dy[i]);

end; { if }

end; { Corabie }

procedure NumaraCorabiile;

{ Numara corabiile de pe campul de joc }

var i, j : integer;

begin

t1:=0; t2:=0; t3:=0;

for i:=1 to m do

begin

for j:=1 to n do

if A[i,j]<>0 then

begin

k1:=0; k2:=0;

Corabie(i, j);

if (k2=0) then t1:=t1+1 else

if (k1=0) then t2:=t2+1 else t3:=t3+1;

end; { if }

end; { for }

end; { NumaraCorabiile }

begin

Citeste;

NumaraCorabiile;

Scrie;

end.

Din analiza textului procedurii NumaraCorabiile se observă că apelul procedurii

Corabie va fi efectuat de cel mult mn ori. În cel mai rău caz, în procedura Corabie vor fi

parcurse toate cel mn pătrăţele.

Prin urmare, numărul de operaţii cerut de program va fi de ordinul 2)(mn . Evident,

pentru 25, nm , numărul respectiv de operaţii va fi cu mult mai mic decât capacitatea de

prelucrare a calculatoarelor moderne.

22

Clasele 10 12

Denumirea

problemei

Numărul de

puncte alocat

problemei

Denumirea

fişierului sursă

Denumirea

fişierului de

intrare

Denumirea

fişierului de

ieşire

Vâslaşii 100 VASLASI.PAS

VASLASI.C

VASLASI.CPP

VASLASI.IN VASLASI.OUT

Iepuraşii 100 IEPURE.PAS

IEPURE.C

IEPURE.CPP


Segmente 100 SEGMENT.PAS

SEGMENT.C

SEGMENT.CPP


Şarpele 100 SARPE.PAS

SARPE.C

SARPE.CPP

SARPE.IN SARPE.OUT

Descompuneri 100 DESC.PAS

DESC.C

DESC.CPP

DESC.IN DESC.OUT

Radioul 100 RADIO.PAS

RADIO.C

RADIO.CPP

RADIO.IN RADIO.OUT

Total 600 - - -

23

Vâslaşii

În sfârşit, în anul 2009, informaticienii au putut rezolva problema, care de mult timp îi

chinuia pe vâslaşii-sportivi.

Se consideră o barcă lungă cu vâsle, în care sunt amplasaţi n vâslaşi. Fiecare vâslaş are

câte o vâslă, cu care el vâsleşte doar pe o singură parte a bărcii − partea stânga sau partea

dreapta. Evident, vâslind, fiecare sportiv comunică bărcii o accelerare nu doar strict în direcţia

mişcării bărcii, dar şi perpendicular pe ea. Apare întrebarea, cum trebuie să orientăm vâslele

sportivilor din barcă, pentru ca ea să nu aibă oscilaţii, perpendiculare pe direcţia mişcării.

Din punct de vedere matematic, soluţia problemei se reduce la amplasarea semnelor „+”

(vâsla pe partea stângă) şi „-” (vâsla pe partea dreaptă) în faţa numerelor de vâslaşi 1, 2, 3, ...n

în aşa mod, încât suma obţinută să fie egală cu zero.

De exemplu, pentru 4n , avem 04321 . Prin urmare, vâslaşii 1 şi 4 vor

vâsli pe partea stânga, iar vâslaşii 2 şi 3 − pe partea dreapta a bărcii.

Sarcină. Elaboraţi un program care amplasează semnele „+”, „-” în faţa numerelor din

şirul 1, 2, 3, ..., n în aşa mod, încât suma obţinută să fie egală cu zero.

Date de intrare. Fişierul text VASLASI.IN conţine pe o singură linie numărul întreg n.

Date de ieşire. Fişierul text VASLASI.OUT va conţine pe o singură linie un şir din n

caractere, format din semnele +, -. Dacă problema are mai multe soluţii, în fişierul de ieşire se

va scrie doar una, oricare din ele. Dacă problema nu are soluţii, în fişierul de ieşire se va scrie

un şir din n caractere, format din semnul ?.

Exemplul 1.


4 +--+

Exemplul 2.


5 ?????



VASLASI.PAS, VASLASI.C sau VASLASI.CPP.

Rezolvare

Problema poate fi rezolvată prin metoda trierii, examinând toate variantele posibile de

amplasare a semnelor „+”, „-” în faţa numerelor din şirul 1, 2, 3, ..., n.

Pentru a genera variantele de amplasare, vom folosi numărul binar Orientare, cifra i a

căruia ia valoarea 0 daca vâslaşul i are vâsla pe partea stângă a bărcii şi valoarea 1 în caz

contrar.

24

Iniţial, numărul binar Orientare are valoarea 00...000. În continuare, la fiecare iteraţie

vom aduna la acest număr valoarea binară “1”, operaţie cunoscută în informatică ca

incrementare. În programul ce urmează, numărul binar Orientare este reprezentat prin tabloul

cu acelaşi nume, iar operaţia de incrementare se realizează cu ajutorul procedurii Increment.

Program Vaslasii;

{ Clasele 10-12 }

const nmax=21;

var n : integer; { numarul de vaslasi }

S : string; { raspunsul }

Orientare : array [1..nmax] of integer; {orientarea vaslelor }

Transport : integer;

procedure Citeste;


var Intrare : text;

begin

assign(Intrare, 'VASLASI.IN');

reset(Intrare);

readln(Intrare, n);

close(Intrare);

end; { Citeste }

procedure Scrie;

{ srierea datelor de iesire }

var Iesire : text;

begin

assign(Iesire, 'VASLASI.OUT');

rewrite(Iesire);

writeln(Iesire, S);

close(iesire);

end; { Scrie }

procedure Increment;

{ incrementarea numarului binar Orientare }

var i : integer;

begin

Transport:=1;

for i:=1 to n do

begin

Orientare[i]:=Orientare[i]+Transport;

if Orientare[i]<=1 then Transport:=0

else

begin

Orientare[i]:=Orientare[i]-2;

Transport:=1;

end; { else }

end; { for }

end; { Increment }

function Suma : integer;

{ calculeaza suma numerelor ce reprezinta vaslasii, }

{ luand in considerare cifrele binare din Orientare }

var i : integer;

P : integer; { sumele intermediare }

begin

P:=0;

for i:=1 to n do

if Orientare[i]=0 then P:=P+i else P:=P-i;

Suma:=P;

end; { Suma }

25

procedure OrientareaVaslelor;

{ cauta orientarea vaslelor }

label 1;

var i : integer;

begin

{ initial toate vaslele sunt pe partea stanga }

for i:=1 to n do Orientare[i]:=0;

{ trierea tuturor variantelor posibile de orientare }

Transport:=0;

while Transport=0 do

begin

if Suma=0 then

begin

{ a fost gasita o solutie }

S:='';

for i:=1 to n do

if Orientare[i]=0 then S:=S+'+' else S:=S+'-';

goto 1;

end; { if }

{ urmatoare varianta de orientare a vaslelor }

Increment;

end; { while }

{ daca am ajuns aici, solutii nu exista }

S:='';

for i:=1 to n do S:=S+'?';

1: end; { OrientareaVaslelor }

begin

Citeste;

OrientareaVaslelor;

Scrie;

end.

În cel mai rău caz, când problema nu are soluţii, vor fi examinate toate cele n2 valori

posibile ale numărului binar Orientare. Prin urmare, numărul de operaţii, cerut de algoritm, va

fi proporţional cu nn2 . Conform restricţiilor problemei, 21n . Prin urmare, numărul de

operaţii va fi proporţional cu 821 105.0212 , mărime comparabilă cu capacitatea de

prelucrare a calculatoarelor personale moderne. Evident, pentru valori 21n , timpul de

execuţie al programului va fi mai mic decât 2 secunde.

26

Iepuraşii

În cartea sa Liber Abaci (Cartea Abacului), editată în anul 1202, marele matematician

Fibonacci (cunoscut şi sub numele Leonardo Pisano) a rezolvat „problema înmulţirii

iepuraşilor”, care constă în calcularea numărului de iepuraşi într-o populaţie ce evoluează

pornind de la o pereche iniţială. Conform acestei cărţi, dezvoltarea populaţiei de iepuraşi se

descrie cu ajutorul şirului 1, 1, 2, 3, 5, 8, 13, ... , denumit şirul lui Fibonacci. Formal, acest şir

se defineşte cu ajutorul următoarelor formule:

11 F , 12 F , 23 F , 34 F , ..., 11 iii FFF , ... ,

unde Fi reprezintă numărul de perechi de iepuraşi în luna i.

Sarcină. Elaboraţi un program care calculează suma S a primelor n numere din şirul lui

Fibonacci.

Date de intrare. Fişierul text IEPURE.IN conţine pe o singură linie numărul întreg n.

Date de ieşire. Fişierul text IEPURE.OUT va conţine pe singură linie numărul întreg S.

Exemplu.


4 7



IEPURE.PAS, IEPURE.C sau IEPURE.CPP.

Rezolvare

În general, problema nu prezintă dificultăţi de algoritmizare, întrucât suma S poate fi

calculată printr-o singură parcurgere a şirului lui Fibonacci. Mai mult ca atât, nu este necesară

nici memorarea întregului şir, întrucât numărul curent poate fi calculat prin însumarea doar a

celor două numere precedente din şir.

Prin F1, F2 şi F3 vom nota oricare trei numere consecutive din şirul lui Fibonacci.

Evident, suma S poate fi calculată cu ajutorul următoarei secvenţe de algoritm:

F1:=1;

F2:=1;

S:=F1;

i:=2;

repeat

S:=S+F2;

F3:=F1+F2;

F1:=F2;

F2:=F3;

i:=i+1;

until i>n;

Implementând această secvenţă cu ajutorul declaraţiilor de variabile

var S, F1, F2, F3 : integer;

27

prin experimente de calcul ne convingem, că începând cu 20n , la calcularea valorilor

variabilelor în studiu au loc erori de depăşire.

Cei care cunosc alte tipuri de date, ar putea să încerce declaraţia

var S, F1, F2, F3 : longint;

din Turbo Pascal sau tipurile de date Longword, Int64, Qword din Object Pascal. Însă şi în

astfel de cazuri, pentru valorile mari ale lui n apar erori de depăşire.

Pentru a evita erorile de depăşire, vom reprezenta numerele mari S, F1, F2 şi F3 prin

tablouri, formate din K elemente. Fiecare element al tabloului memorează câte o cifra a

numărului respectiv.

Dacă în procesul adunării a două numere mari A şi B, formate din câte K cifre,

transportul calculat în cazul însumării cifrelor A[1], B[1] şi transportului din rangul precedent

diferă de zero, are loc o depăşire şi programul va semnaliza o eroare.

În programul ce urmează, pentru a realiza experimentul de calcul, în componenţa

procedurii Adunare a fost inclusă următoarea secvenţă de instrucţiuni:

if Transport=1 then

begin


readln;

end;

Evident, în condiţiile problemei, această secvenţă de instrucţiuni nu va fi executată nici

o dată numai atunci, când valoarea lui K va fi stabilită suficient de mare. Această valoare

poate fi determinată cu ajutorul experimentelor de calcul, atribuindu-i lui n valoarea limită

300n , aşa cum este indicat în restricţiile problemei.

Program Iepurasii;

{ Clasele 10-12 }

const K = 70; { numarul de cifre ale numerelor foarte mari }

type Cifra = 0..9;

Numar = array[1..K] of Cifra;

var n : integer;

S : Numar;

procedure Citeste;

{ Citeste numarul n din fisierul de intrare }

var Intrare : text;

begin

assign(Intrare, 'IEPURE.IN');

reset(Intrare);

readln(Intrare, n);

close(Intrare);

end; { Citeste }

procedure Scrie;

{ Scrie suma S in fisierul de iesire }

var Iesire : text;

j : integer;

1 2 3 ... K

28

begin

assign(Iesire, 'IEPURE.OUT');

rewrite(Iesire);

j:=1;

while S[j]=0 do j:=j+1;

while j<=K do

begin

write(Iesire, S[j]);

j:=j+1;

end; { while }

writeln(Iesire);

close(Iesire);

end; { Scrie }

procedure Unu(var A : Numar);

{ Atribuie numarului A valoarea 1 }

var j : integer;

begin

for j:=1 to K-1 do A[j]:=0;

A[K]:=1;

end; { Unu }

procedure Adunare(A, B : Numar; var C : Numar);

{ Calculeaza suma C:=A+B }

var Transport : Cifra;

j : integer;

q : 0..19;

begin

Transport:=0;

for j:=K downto 1 do

begin

q:=A[j]+B[j]+Transport;

if q<=9 then Transport:=0

else

begin

Transport:=1;

q:=q-10;

end;

C[j]:=q;

end; { for }

if Transport=1 then

begin


readln;

end;

end; { Adunare }

procedure Suma;

var i : integer;

F1, F2, F3 : Numar;

begin

Unu(F1);

Unu(F2);

S:=F1;

i:=2;

repeat

Adunare(F2, S, S);

Adunare(F1, F2, F3);

F1:=F2;

F2:=F3;

i:=i+1;

until i>n;

end; { Suma }

29

begin

Citeste;

Suma;

Scrie;

end.

Întrucât suma S se calculează printr-o singură parcurgere a şirului lui Fibonacci,

complexitatea temporală a programului este )(nKO . Conform restricţiilor problemei,

300n , iar 70K . Evident, pentru astfel de valori, timpul de execuţie al programului va fi

cu mult mai mic decât 0,5 secunde.

30

Segmente

Se consideră mulţimea S, formată din n segmente distincte, notate prin S1, S2, ..., Si, ...,

Sn. Fiecare segment Si este definit prin coordonatele carteziene ),( ii yx , ),( ii yx ale

extremităţilor sale.


adiacente, dacă ele au o extremitate

comună.


conectate dacă există o succesiune

de segmente, care începe cu Si şi se

termină cu Sj şi în care oricare două

segmente consecutive sunt

adiacente.

De exemplu, segmentele S1, S5

de pe figura alăturată sunt conectate

întrucât există o succesiune de

segmente consecutiv adiacente: S1,

S3, S5.

Submulţimea de segmente Q, Q S, formează o reţea, dacă segmentele respective sunt

conectate între ele, fără a avea însă conexiuni cu segmentele din submulţimea S \ Q.

În general, mulţimea de segmente S poate avea mai multe reţele.

De exemplu, mulţimea de segmente de pe figura de mai sus conţine 3 reţele: {S1, S2, S3,

S5}, {S4} şi {S6, S7}.

Sarcină. Elaboraţi un program, care, cunoscând mulţimea de segmente S, calculează

numărul de reţele k.

Date de intrare. Fişierul text SEGMENT.IN conţine pe prima linie numărul întreg n.

Fiecare din următoarele n linii ale fişierului de intrare conţine numerele reale iiii yxyx ,,, ,

separate prin spaţiu. Linia 1i a fişierului de intrare conţine coordonatele extremităţilor

segmentului Si.

Date de ieşire. Fişierul text SEGMENT.OUT va conţine pe singură linie numărul întreg k.

Exemplu.


7

10.15 0.7 40.15 0.8

20.15 0.6 40.15 0.8

40.15 0.8 70.15 0.4

20.15 0.4 90.15 0.7

50.15 0.2 70.15 0.4

80.15 0.3 11.15 0.8

80.15 0.3 13.15 0.1

3

Restricţii. 0003003 n ; 00010,,,00010 iiii yxyx . Numerele reale din

fişierul de intrare vor conţin cel mult trei cifre semnificative după punctul zecimal. Timpul de

execuţie nu va depăşi 1,5 secunde. Programul va folosi cel mult 32 Megaocteţi de memorie

operativă. Fişierul sursă va avea denumirea SEGMENT.PAS, SEGMENT.C sau SEGMENT.CPP.

31

Rezolvare

Pentru început, vom încerca să construim consecutiv fiecare din eventualele reţele:

1. Iniţial, stabilim }{: 1SQ şi }{\: 1SSS .

2. Examinând fiecare segment din mulţimea S, le selectăm pe cele conectate cu

segmentele din Q şi le trecem din S în Q. Dacă astfel de segmente nu mai există,

s-a obţinut o reţea.

3. În continuare, stabilim }{: iSQ , unde Si este unul din segmentele rămase în

mulţimea S şi construim din nou o eventuală reţea.

4. Procesul de construire a reţelelor se termină atunci, când mulţimea S devine una

vidă.

Deşi complexitatea unui astfel de algoritm este de ordinul 2n , la implementarea lui într-

un limbaj de programare de nivel înalt va trebui să ţinem cont de faptul, că parcurgerea

elementelor unei mulţimi mai necesită încă cel puţin n operaţii. Prin urmare, complexitatea

temporală a programului respectiv va fi de ordinul 3n .

Conform restricţiilor problemei, 0003003 n . În consecinţă, numărul de operaţii

cerut de program va fi de ordinul 1410 , mărime ce depăşeşte capacitatea de prelucrare a

calculatoarelor personale instalate în laboratoarele de informatică. Evident, timpul de execuţie

a unui astfel de program va fi de ordinul 310 secunde.

Pentru a reduce complexitatea programului, vom implementa un algoritm ce conţine

două etape:

Etapa I preprocesarea datelor, fapt ce va facilita căutarea perechile de segmente

adiacente.

Etapa II construirea reţelelor propriu-zise. Însă, spre deosebire de algoritmul

precedent, în care reţelele erau construite consecutiv, una după alta, în algoritmul propus

reţelele respective sunt construite concomitent, informaţia despre fiecare din ele fiind stocată

într-o structură arborescentă de date.

În programul de mai jos, la prima etapă, se creează structura de date TPuncte. Această

structură, conţine informaţiile complete ),,,,( iyxyx iiii despre fiecare segment, ordonate în

ordinea creşterii coordonatelor x (primul criteriu de sortare) şi y (al doilea criteriu de sortare).

Întrucât după o astfel de sortare segmentele adiacente vor fi plasate pe poziţii vecine, găsirea

segmentelor adiacente necesită doar o singură parcurgere a tabloului TPuncte.

La etapa a doua sunt construite reţelele propriu-zise. Informaţia despre reţelele

respective se stochează într-un set de arbori inversaţi (rooted tree forest), care „cresc” de jos

în sus.

Fiecare nod al unui astfel de arbore conţine câmpurile tata şi sz. Câmpul tata conţine

identificatorul segmentului deja inclus în reţea, iar câmpul sz conţine numărul total de noduri

aflat in arbore sub nodul curent.

Iniţial, nodul care e singur (izolat), va avea în câmpul tata valoarea -1 (nu are tata), iar

în câmpul sz valoarea 1. În procesul execuţiei procedurii AflaComponenta(a), algoritmul

“urca” de-a lungul „taţilor” pana la nodul „din vârf”, care nu are tata. Identificatorul acelui

nod şi va fi identificatorul reţelei din care face parte segmentul a.

În procesul execuţiei procedurii Uneste(a, b), la început se identifica componenta lui

a si componenta lui b. In cazul in care acestea sunt identice, nu se face nimic. În cazul în care

componentele sunt diferite, se ataşează componenta mai mica la cea mai mare, astfel încât

arborele sa aibă adâncimea egala cu cel mult nlog .

32

Program Segmente;

{ Clasele 10-12 }

const MAXN = 320000; type TPunct = record x, y: longint; segment: longint; end;

type TPuncte = array[1..2 * MAXN] of TPunct; var capete: TPuncte; {punctele} var n: longint; {numarul de segmente}

procedure Citeste;

{ citeste fisierul de intrare si construieste tabloul cu puncte }

var f: text;

x1, y1, x2, y2: double;

i: longint;

begin

assign(f, 'SEGMENTE.IN');

reset(f);

readln(f, n);

for i := 1 to n do

begin

readln(f, x1, y1, x2, y2);

capete[2 * i - 1].x := round(x1 * 1000);

capete[2 * i - 1].y := round(y1 * 1000);

capete[2 * i - 1].segment := i;

capete[2 * i].x := round(x2 * 1000);

capete[2 * i].y := round(y2 * 1000);

capete[2 * i].segment := i;

end;

close(f);

end; { Citeste }

function ComparaPuncte(var a, b : TPunct) : integer;

{ Compara doua puncte } { returneaza -1 daca a e "mai mic" ca b, +1 daca e "mai mare", }

{ zero daca sunt "egale" } begin if a.x < b.x then exit(-1); if a.x > b.x then exit(1); {a.x = b.x} if a.y < b.y then exit(-1); if a.y > b.y then exit(1); exit(0); end; { ComparaPuncte }

procedure Qsort(var data : TPuncte; a, b : longint);

{ Sortarea rapida a subsirul a..b al sirului de puncte data } var left, right : longint; aux, pivot : TPunct; begin pivot := data[(a + b) div 2]; left := a; right := b; while left <= right do begin while ComparaPuncte(data[left], pivot) < 0 do left := left + 1; while ComparaPuncte(data[right], pivot) > 0 do right := right - 1; if left <= right then begin { schimbam cu locul Data[left] si Data[right] } aux := data[left]; data[left] := data[right];

33

data[right] := aux; left := left + 1; right:= right - 1; end; end; if right > a then qsort(data, a, right); { sortam subsirul STANGA } if b > left then qsort(data, left, b); { sortam subsirul DREAPTA } end; { Qsort }

var i: longint;

{ Nod - elementul de baza al Rooted Tree Forest } type TNod = record

tata: longint; sz: longint; end;

{ setul de arbori inversati: Rooted Tree Forest } var retele: array[1.. 2 * MAXN] of TNod;

function AflaComponenta(a : longint): longint;

{ Returneaza identificatorul retelei in care se afla elementul a } var pozitie, z, nextPos : longint; begin z := 1; pozitie := a; while retele[pozitie].tata > 0 do pozitie := retele[pozitie].tata; z := pozitie; {salvam id-ul retelei in z} pozitie := a; while pozitie <> z do

{ parcurgem arborele "de jos in sus" } begin nextPos := retele[pozitie].tata; retele[pozitie].tata := z; pozitie := nextPos; end; AflaComponenta := z; end; { AflaComponenta }

procedure Uneste(a, b : longint);

{ Proceseaza informatia ca a si b sunt in aceeasi componenta } var componentaA, componentaB : longint; begin componentaA := AflaComponenta(a); componentaB := AflaComponenta(b); if componentaA = componentaB then exit;

{ nu e nimic de facut, componentele sunt deja unite } if retele[componentaA].sz < retele[componentaB].sz then begin

{ componenta A e mai mica decat B, deci punem pe A sub B } retele[componentaA].tata := componentaB; inc(retele[componentaB].sz, retele[componentaA].sz); end else begin {invers; componenta B e mai mica decat A, deci punem pe B sub A} retele[componentaB].tata := componentaA; inc(retele[componentaA].sz, retele[componentaB].sz); end; end; { Uneste }

var capDeRetea : array[1..MAXN] of boolean; rezultat, componenta : longint; f : text;

34

begin { programul principal } { Etapa I } Citeste; Qsort(capete, 1, 2 * n); { Etapa II } for i := 1 to 2 * n do

{ initializam setul de arbori: fiecare segment e singur, }

{ neconectat cu nimeni } begin retele[i].tata := -1; { nu are tata, deci e singur } retele[i].sz := 1; { un singur element in set - segmentul insusi } end; for i := 2 to 2 * n do

{ procesam informatia despre conexiunile dintre segmente } begin if ComparaPuncte(capete[i-1], capete[i]) = 0 then Uneste(capete[i-1].segment, capete[i].segment); end; fillchar(capDeRetea, sizeof(capDeRetea), false); for i := 1 to n do begin componenta := AflaComponenta(i); capDeRetea[componenta] := true; end; rezultat := 0; for i := 1 to n do if capDeRetea[i] then inc(rezultat); assign(f, 'segmente.out'); rewrite(f); writeln(f, rezultat); close(f); end.

Din analiza operaţiilor efectuate în cadrul Etapelor I şi II rezultă, că complexitatea

temporală a programului este )log( nnO . Conform restricţiilor problemei, 0003003 n .

Prin urmare, numărul de operaţii va fi de ordinul 710 , mărime comparabilă cu capacitatea de

prelucrare a calculatoarelor personale din laboratorul de informatică.

Menţionăm, că numerele reale ce reprezintă coordonatele extremităţilor de segmente

conţin cel mult trei cifre după virgulă. Putem folosi acest fapt pentru a trece de la

coordonatele reale la cele întregi, care, evident, sunt procesate mult mai rapid. Anume din

aceste considerente, în procedura Citeste, numerele reale, citite din fişierul de intrare, sunt

înmulţite cu 0001 şi transformate în numere întregi.

35

Şarpele

Intr-o versiune simplificată a binecunoscutul joc clasic de calculator Snake (Şarpele), un

şarpe trebuie sa mănânce toate merele dintr-o livada. Regulile acestui joc sunt foarte simple:

1. În livada sunt împrăştiate pe pământ n mere, poziţia fiecărui mar i fiind definită prin

coordonatele carteziene întregi (xi, yi).

2. Originea sistemului de coordonate se află în colţul stânga-jos al livezii. Axa de

coordonate 0X este orientată de la stânga la dreapta, iar axa 0Y – de jos în sus.

3. La începutul jocului, în livada intra un şarpe, care are drept scop să mănânce toate

merele din livada.

4. Poziţia curentă a şarpelui este definită prin coordonatele carteziene întregi (xs, ys).

5. Poziţia iniţială a şarpelui este (1, 1).

6. Repertoriul de comenzi ale şarpelui include instrucţiunile de deplasare SUS, JOS,

STÂNGA, DREAPTA. Execuţia unei astfel de comenzi constă în deplasarea şarpelui

în direcţia respectivă exact cu o unitate de lungime.

7. Atunci când coordonatele şarpelui devin egale cu coordonatele unui măr, şarpele

mănâncă mărul respectiv.

Scopul jocului constă în deplasarea şarpelui în aşa mod, încât toate merele să fie

mâncate, iar drumul parcurs de şarpe să fie cât mai scurt.

Dorin este împătimit de jocul Snake. El îl joaca de multă vreme şi a stabilit mai multe

recorduri. Din păcate, pe consola lui de jocuri s-a defectat butonul comenzii JOS. În

consecinţă, şarpele, indiferent de poziţia în care se afla, poate executa doar comenzile SUS,

STÂNGA, DREAPTA.

Dorin insă nu s-a descurajat şi consideră această defecţiune o nouă provocare. Întrucât

Dorin a devenit foarte priceput la acest joc, el doreşte să stabilească un nou record. El nu se

îndoieşte deloc de abilităţile lui de a direcţiona şarpele pe orice drum posibil, dar vrea să ştie

lungimea celui mai scurt drum, deplasându-se pe care şarpele ar mânca toate merele.

Sarcină. Elaboraţi un program, care, cunoscând coordonatele celor n mere, calculează

lungimea L a celui mai scurt drum, deplasându-se pe care şarpele ar mânca toate merele.

Date de intrare. Fişierul text SARPE.IN conţine pe prima linie numărul întreg n.

Fiecare din următoarele n linii ale fişierului de intrare conţine numerele întregi xi, yi, separate

prin spaţiu. Linia 1i a fişierului de intrare conţine coordonatele mărului i.

Date de ieşire. Fişierul text SARPE.OUT va conţine pe singură linie numărul întreg L.

Exemplu.

SARPE.IN SARPE.OUT

5

2 2

5 3

7 3

8 4

4 6

16

Restricţii. 000101 n ; 00010,1 ii yx . Timpul de execuţie nu va depăşi 0,1

secunde. Programul va folosi cel mult 32 Megaocteţi de memorie operativă. Fişierul sursă va

avea denumirea SARPE.PAS, SARPE.C sau SARPE.CPP.

36

Rezolvare

Pentru a reduce numărul de cazuri particulare, vom include în mulţimea merelor încă

unul, aflat pe poziţia (1, 1).

În continuare, introducem în studiu un set de m linii drepte, paralele cu axa de

coordonate X, pe fiecare din care se află cel puţin câte un măr. Evident, fiecare din aceste linii

poate fi definită univoc prin coordonata yp, }...,,,{ 21 mp yyyy . Întrucît avem garantat un

măr pe poziţia (1, 1), rezultă că 11 y .

Prin px vom nota abcisa celui mai din stânga, iar prin px − abcisa celui mai din dreapta

măr de pe linia yp.

Deoarece repertoriul de comenzi ale

şarpelui nu mai conţine comanda JOS, odată

ajuns pe o linie cu mere, şarpele trebuie să

mănînce toate merele de pe această linie şi

abia apoi să se deplaseze în sus.

În aceste condiţii, lungimea celui mai

scurt drum poate fi calculată prin metoda

programării dinamice, pornind de la linia cea

de mai jos şi terminând cu linia cea de mai

sus. Pentru fiecare linie, şarpele poate termina

parcurgerea ei în una din două poziţii: la

capătul stâng sau la capătul drept al liniei.

Pentru a formaliza acest proces, introducem în studiu următoarele funcţii:

)( pyL − lungimea celui mai scurt drum, parcurgându-l pe care şarpele mănâncă toate

merele de pe liniile de mai jos şi de pe linia curentă, rămânând în poziţia celui mai din stânga

măr de pe linia curentă yp;

)( pyL − lungimea celui mai scurt drum, parcurgându-l pe care şarpele mănâncă toate

merele de pe liniile de mai jos şi de pe linia curentă, rămânând în poziţia celui mai din dreapta

măr de pe linia curentă yp.

Valorile acestor funcţii pot fi calculate după următoarele formule recurente:

1*2)1( pp xxL ; 1)1(

pxL ;

)(|]|)(|,|)(min[)()( 11111 ppppppppppp xxxxyLxxyLyyyL ;

)(|]|)(|,|)(min[)()( 11111 ppppppppppp xxxxyLxxyLyyyL .

Evident, lungimea celui mai scurt drum va fi:

)](),(min[ mm yLyLL .

unde ym este coordonata celei mai de sus linii.

Program Sarpele;

{ Clasele 10-12 }

const MAXPOZ = 10000;

var n:longint;

px, py, num, minx, maxx, costMinX, costMaxX

:array[1..MAXPOZ] of longint;

37

costMin:longint;

procedure Citeste;

var fin:text;

i:longint;

begin

assign(Intrare, 'SARPE.IN');

reset(Intrare);

readln(Intrare, n);

for i := 1 to n do

readln(Intrare, px[i], py[i]);

close(Intrare);

end; { Citeste }

procedure GruparePeLinii;

var i,x,y:longint;

begin

num[1] := 1;

minx[1] := 1;

maxx[1] := 1;

for i := 1 to n do

begin

x := px[i];

y := py[i];

inc(num[y]);

if (num[y] = 1) then

begin

minx[y] := x;

maxx[y] := x;

end

else

begin

if (x < minx[y]) then minx[y] := x;

if (maxx[y] < x) then maxx[y] := x;

end;

end;

end; { GruparePeLinii }

function min(a, b: longint):longint;

begin

if (a < b) then min := a

else min := b;

end;

procedure CalculCosturiMin;

var i, prevY, y, dy :longint;

var costMinInMin, costMaxInMin, costMinInMax, costMaxInMax: longint;

begin

costMinX[1] := 2 * maxx[1] - minx[1] - 1;

costMaxX[1] := maxx[1] - 1;

prevY := 1;

for i := 2 to MAXPOZ do

if (num[i] > 0) then

begin

y := i;

dy := y - prevY;

costMinInMin := costMinX[prevY] + abs(maxx[y]-minx[prevY]);

costMaxInMin := costMaxX[prevY] + abs(maxx[y]-maxx[prevY]);

costMinInMax := costMinX[prevY] + abs(minx[y]-minx[prevY]);

costMaxInMax := costMaxX[prevY] + abs(minx[y]-maxx[prevY]);

costMinX[y] := min(costMinInMin, costMaxInMin)

+ dy + (maxx[y] - minx[y]);

costMaxX[y] := min(costMinInMax, costMaxInMax)

38

+ dy + (maxx[y] - minx[y]);

prevY := y;

end;

costMin := min(costMinX[prevY], costMaxX[prevY]);

end; { CalculCosturiMin }

procedure Scrie;

var fout: text;

begin

assign(Iesire, 'SARPE.OUT');

rewrite(Iesire);

writeln(Iesire, costMin);

close(Iesire);

end;

begin

Citeste;

GruparePeLinii;

CalculCosturiMin;

Scrie;

end.

Dina analiza textului procedurii GruparePeLinii se observă că pentru determinarea

coordonatelor yp, px şi px este suficientă o singură parcurgere liniară a datelor de intrare,

deci complexitatea acestei proceduri este )(nO . În procedura CalculCosturiMin, valorile

)( pyL şi )( pyL se calculează de m ori. Întrucât nm , complexitatea acestei proceduri va fi,

de asemenea, )(nO . Conform restricţiilor din enunţul problemei, 00010n . Prin urmare,

numărul de operaţii cerut de algoritm va fi de ordinul 104, mărime cu mult mai mică decât

capacitatea de prelucrare a calculatoarelor din laboratorul de informatică.

39

Descompuneri

Numim k-descompunere a numărului natural nenul N reprezentarea acestuia ca o sumă

de exact k numere naturale nenule, scrise în ordine strict crescătoare. În general, în

dependenţă de valorile N şi k, numărul N poate să nu aibă nici una, să aibă doar una sau să

aibă mai multe k-descompuneri.

Exemple:

9 = 9 este o 1-descompunere a numărului 9;

9 = 4 + 5 este o 2-descompunere a numărului 9;

9 = 3 + 6 este o altă 2-descompunere a numărului 9;

9 = 1 + 3 + 5 este o 3-descompunere a numărului 9;

9 = 1 + 2 + 6 este o altă 3-descompunere a numărului 9.

Contraexemple:

9 = 3 + 1 + 5 nu este o 3-descompunere a numărului 9, întrucât în scrierea respectivă

termenii 3 şi 1 nu apar în ordine crescătoare;

9 = 1 + 1 + 7 nu este o 3-descompunere a numărului 9, întrucât în scrierea respectivă

termenii 1 şi 1 nu apar în ordine strict crescătoare;

9 = 0 + 9 nu este o 2-descompunere a numărului 9, întrucât în scrierea respectivă

apare numărul 0.

Sarcină. Elaboraţi un program, care, cunoscând numerele naturale N şi k, calculează

numărul T de k-descompuneri posibile ale lui N. Deoarece numărul T poate fi foarte mare, în

fişierul de ieşire se va scrie doar restul împărţirii lui T la 1 000 000 000 (un miliard).

Date de intrare. Fişierul text DESC.IN conţine pe singura linie numerele întregi N şi k,

separate prin spaţiu.

Date de ieşire. Fişierul text DESC.OUT va conţine pe singură linie restul împărţirii

numărului întreg T la 1 000 000 000 (un miliard).

Exemple:

1) DESC.IN DESC.OUT

12 3 7

2) DESC.IN DESC.OUT

90 1 1

3) DESC.IN DESC.OUT

300 9 382665027

Restricţii. 7001 Nk . Timpul de execuţie nu va depăşi 0,5 secunde. Programul va


DESC.PAS, DESC.C sau DESC.CPP.

Rezolvare

Problema poate fi rezolvată prin metoda programării dinamice. În acest scop,

introducem în studiu funcţia ),,( bakt . Această funcţie reprezintă numărul de k-descompuneri

ale numărului a, care au ca termen minim pe b.

Evident, 1),,1( bat dacă ba şi 0),,1( bat în caz contrar. În general, se poate

demonstra că funcţia în studiu poate fi scrisă într-o formă recurentă:

40

ba

bi

ibaktbakt1

),,1(),,( .

Prin urmare, numărul T poate fi calculat prin însumarea valorilor ),,( jNkt pentru

Nj ...,,2,1 :

N

j

jN

ji

N

j

ijNktjNktT1 11

),,1(),,( .

Complexitatea temporală a unui algoritm bazat pe formula recurentă de mai sus este

)( 3kNO . În cazul restricţiilor problemei, numărul de operaţii cerut de algoritm va fi de

ordinul 1410 , mărime cu mult mai mare decât capacitatea de prelucrare a calculatoarelor

personale din laboratorul de informatică.

Pentru a reduce complexitatea temporală a algoritmului vom lua în considerare faptul că

pentru valorile lui bai funcţia 0),,( bakt . În consecinţă, vom calcula doar sumele din

“dreapta” indicelui respectiv. În acest caz complexitatea algoritmului va fi )( 2 NNO , iar

numărul cerut de operaţii va fi de ordinul 810 , mărime comparabilă cu capacitatea de

prelucrare a calculatoarelor din laboratorul de informatica.

Menţionăm faptul, că în procesul de efectuare a calculelor nu se cere memorarea tuturor

valorilor ),,( bakt , fiind suficiente doar valorile iteraţiei curente şi termenii din „dreapta”, în

total circa 4 Megaocteţi de memorie operativă.

Program Descompuneri;

{ Clasele 10-12 }

const MAXN = 1000;

const MODULO = 1000 * 1000 * 1000;

type TMatrice = array[1..MAXN, 1..MAXN] of longint;

var f: text;

n, m: longint;

a: TMatrice;

sumaLaDreapta: TMatrice;

i, j, k: longint;

res: longint;

existaElementNenul: boolean;

procedure scrieRezultat(q: longint);

{ Scrie rezultatul în fişierul de ieşire şi termină programul }

var f: text;

begin

assign(f, 'DESC.OUT');

rewrite(f);

writeln(f, res);

close(f);

halt(0);

end; { Scrie }

begin

fillchar(a, sizeof(a), 0);

fillchar(sumaLaDreapta, sizeof(sumaLaDreapta), 0);

assign(f, 'DESC.IN');

reset(f);

readln(f, n, m);

41

close(f);

{ construim cazul de baza: t[1, x, y] }

for j := 1 to n do

for k := 1 to n do

begin

if (j = k) then a[j, k] := 1 else a[j, k] := 0;

end;

{ partea principală: calcularea t[k, x, y] pentru k > 1 }

for i := 2 to m do

begin

{ calculăm sumaLaDreapta }

for j := 1 to n do

for k := j downto 1 do

sumaLaDreapta[j, k] := (a[j, k] + sumaLaDreapta[j, k + 1]) mod

MODULO;

{ calculăm t[i, j, k], care e memorat în a[j, k] }

existaElementNenul := false; {detector de valori nenule in a}

for j := 1 to n do

for k := 1 to n do

begin

a[j, k] := sumaLaDreapta[j - k, k + 1];

if a[j, k] > 0 then existaElementNenul := true;

end;

{ in cazul in care existaElementNenul e false, toate elementele lui a

}

{ calculate ulterior vor fi nule. Prin urmare, terminam calculele }

if not existaElementNenul then scrieRezultat(0);

end;

{ calculam raspunsul }

res := 0;

for k := 1 to n do

begin

inc(res, a[n, k]);

res := res mod MODULO;

end;

scrieRezultat(res);

end.

42

Radioul

Postul de radio “Bitul Liber” are la dispoziţie n emiţătoare, amplasate în n localităţi

distincte. Poziţia fiecărui emiţător i, ni ...,,3,2,1 , este definită prin coordonatele carteziene

întregi ),( ii yx .

Fiecare emiţător are una şi aceiaşi putere de emisie R. Evident, cu cât emiţătorul este

mai puternic, cu atât este mai mare şi distanţa la care se propagă undele emise de el. În

scopuri didactice, se consideră, că undele unui emiţător de puterea R se propaga până la

distanţa de R kilometri.

Deşi emiţătoarele au una şi aceiaşi putere R, fiecare din ele poate fi acordat în mod

individual să emită pe una din frecvenţele disponibile frecvenţa F1 sau frecvenţa F2.

Este cunoscut faptul, că undele radio interferează şi, în consecinţă, dacă un receptor este

supus acţiunii concomitente a două unde de aceiaşi frecvenţă, calitatea recepţiei scade brusc.

În general, conform regulilor de radiodifuziune, calitatea recepţiei se consideră bună doar

atunci, când nu există nici un sector de arie nenulă, pe care ajung unde radio, emise de două

emiţătoare ce au aceiaşi frecvenţă de emisie.

Este evident faptul, că pentru a extinde aria pe care pot fi recepţionate emisiunile

postului de radio “Bitul Liber”, puterea de emisie R trebuie mărită. Concomitent, frecvenţele

de emisie F1, F2 pentru fiecare din emiţătoare trebuie alese în aşa mod, încât să se asigure

calitatea recepţiei emisiunilor respective.

Sarcină. Scrieţi un program, care, cunoscând coordonatele emiţătoarelor, calculează

puterea maximală de emisie R, ce mai permite încă alegerea pentru fiecare din emiţătoare a

unor astfel de frecvenţe, încât se asigură calitatea recepţiei.

Date de intrare. Fişierul text RADIO.IN conţine pe prima linie numărul întreg n.

Fiecare din următoarele n linii ale fişierului de intrare conţine numerele întregi xi, yi, separate

prin spaţiu. Linia 1i a fişierului de intrare conţine coordonatele emiţătorului i.

Date de ieşire. Fişierul text RADIO.OUT va conţine pe prima linie numărul real R, scris

cu o precizie nu mai mică de 10-8

. Linia a doua a fişierului de ieşire va conţine n numere

întregi, separate prin spaţiu. Numărul care apare pe locul i de pe această linie va fi egal cu 1,

dacă emiţătorul i trebuie să emită pe frecvenţa F1, şi egal cu 2, dacă emiţătorul respectiv

trebuie să emită pe frecvenţa F2. Dacă problema admite mai multe soluţii, în fişierul de ieşire

se va scrie doar una din ele.

Exemplu.

Restricţii. 20013 n ; 44 10,10 iyx . Timpul de execuţie nu va depăşi 2,0

secunde. Programul va folosi cel mult 64 Megaocteţi de memorie operativă Fişierul sursă va

avea denumirea RADIO.PAS, RADIO.C sau RADIO.CPP.

Rezolvare

Din enunţul problemei rezultă că puterea maximală nu poate depăşi jumătate din

distanţa dintre emiţătoarele aflate la cea mai mare distanţă unul de altul. Prin urmare, valoarea

RADIO.IN RADIO.OUT

4

0 0

0 1

1 0

1 1

0.70710678118654752

1 2 2 1

43

concretă a lui R trebuie căutată în intervalul ],0[ maxL , unde maxL poate fi calculat conform

unor formule evidente:

)...,,,min( 21min nxxxx ;

)...,,,min( 21min nyyyy ;

)...,,,max( 21max nxxxx ;

)...,,,max( 21max nyyyy .

12

)()( 2

minmax

2

minmax

max

yyxx

L .

Presupunem, că avem la dispoziţie o funcţie )(RTest , care ia valoarea 1, dacă pentru

puterea de emisie R putem stabili frecvenţele emiţătoarelor în aşa mod, încât să garantăm

calitatea recepţiei, şi 0 în caz contrar. Evident, având o astfel de funcţie, putem calcula puterea

maximală prin metoda înjumătăţirii, pornind de la intervalul iniţial ],0[ maxL şi 2/maxLR .

Pentru a construi funcţia )(RTest , reunim cu câte o linie emiţătoarele, distanţa dintre

care este strict mai mică de R2 . Evident, oricare două emiţătoare, ce sunt reunite printr-o

astfel de linie, trebuie să aibă frecvenţe de emisie diferite.

În continuare, vom încerca să partiţionăm mulţimea emiţătoarelor în două submulţimi,

notate prin A şi B. În cadrul fiecărei submulţimi, emiţătoarele respective nu trebuie să fie

reunite între ele. Dacă acest lucru ne reuşeşte, funcţia )(RTest va lua valoarea 1. În caz

contrar, adică a rămas cel puţin un emiţător, ce nu poate fi incluse nici în submulţimea A, nici

în submulţimea B, funcţia )(RTest va lua valoarea 0.

1)( RTest 0)( RTest

Formarea submulţimilor A şi B poate fi simulată prin „vopsirea” fiecărui emiţător în una

din cele două culori: albă sau neagră. Iniţial, vopsim un emiţător arbitrar în culoare albă sau,

prin alte cuvinte, îl includem în submulţimea A. În continuare, determinăm toate emiţătoarele,

reunite cu emiţătorul proaspăt vopsit, şi le vopsim în culoarea neagră sau, prin alte cuvinte, le

includem în submulţimea B. În general, la fiecare pas al algoritmului, ce încearcă vopsirea

vecinilor emiţătorului curent în culoarea „opusă”. În cazul tehnicii de programare Greedy,

complexitatea unui astfel de algoritm este )( 2nO .

44

Evident, după determinarea valorii maximale R, pentru care funcţia )(RTest mai ea încă

valoarea 1, tuturor emiţătoarelor din mulţimea A li se atribuie una din frecvenţe, de exemplu,

F1, iar celor din submulţimea B cealaltă frecvenţă, de exemplu, frecvenţa F2.

Program Radio;

{ Clasele 10-12 }

var n : Integer;

var x, y : Array[1..1200] of LongInt;

var Freq : Array [1..1200] of Byte;

{ Frecventa asociata fiecarui emitator radio }

var f : Text;

i, j : Integer;

Left, Right, Med : Longint;

MaxSQDist : Longint;

function SQDist(i,j:Integer) : LongInt;

{ Intoarce patratul distantei intre emitatoarele i si j }

begin

SQDist := (x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]);

end;

function Test(R_SQ_4: Longint) : boolean; {parametrul este 4*R*R}

{ verifica daca cu raza de emisie R se poate atribui }

{ frecvente emitatoarelor }

var List : Array [1..1200] of Integer;

var ListSize : Integer; { numarul de noduri in lista }

var i, j, t,curent : Integer;

begin

FillByte(Freq, n, 0);

for i := 1 to n do

begin

if Freq[i]<>0 then continue; { frecventa pentru emitatorul i a fost }

{ aleasa deja }

Freq[i] := 1; {alege frecventa 1 pentru emitatorul i}

{ Initializeaza lista cu un singur element : i }

List[1] := i;

ListSize := 1;

j:=1;

while j <= ListSize do begin

curent := List[j];

for t:=1 to n do

begin

if (t<>curent) and ( SQDist(curent,t) < R_SQ_4 ) then

begin

if (Freq[t] = 0) then

begin

{adauga pe t in lista}

Inc(ListSize);

List[ListSize] := t;

Freq[t] := 3-Freq[curent]; { seteaza frecventa opusa }

end

else

if Freq[t] = Freq[curent] then exit(false);

{ am obtinut o contradictie de frecvente, functia Test }

{ va intoarce imediat false }

end;

end;

Inc(j);

end;

end;

45

Test := true;

end;

begin

{ Citeste datele de intrare }

Assign(f, 'RADIO.IN');

Reset(f);

Readln(f, n);

for i:= 1 to n do Readln(f, x[i], y[i]);

Close(f);

{ Gaseste distanta maxima intre virfuri}

MaxSQDist := 0;

for i:= 1 to n-1 do

for j:= i+1 to n do

if MaxSQDist < SQDist(i, j) then MaxSQDist := SQDist(i, j);

Left := 0;

Right := MaxSQDist + 1;

while Right>Left+1 do

begin

Med := (Left + Right) div 2;

if Test(Med)

then Left:=Med

else Right:=Med;

end;

{ mai apeleaza inca o data pentru a seta Freq[...] }

Test(Left);

{ Scrie raspunsul }

Assign(f,'RADIO.OUT');

Rewrite(f);

writeln(f,(sqrt(Extended(Left))/2):0:18);

for i:=1 to n do Write(f, Freq[i],' ');

writeln(f);

Close(f);

end.

olimpiada republicană la informatică ediţia 2010 moldova

Documents