7/30/2019 Brosura ORI 2012

1/44

MINISTERUL EDUCAIEIAL REPUBLICII MOLDOVA

MHCTEPCTBO IIPOCBEEHPECJIK MO

Olimpiada Republican la Informatic

Ediia 2012

Chiinu 2012

7/30/2019 Brosura ORI 2012

2/44

2

Olimpiada Republican la Informatic. Ediia 2012.

Lucrarea conine problemele propuse la Olimpiada Republican la Informatic a elevilor, ediia2012. Pentru fiecare problem sunt descrise algoritmul i soluia respectiv n limbajul de

programare PASCAL.

Materialele Olimpiadei pot fi de un real folos la studierea Informaticii att elevilor, ct iprofesorilor de Informatic.

La elaborarea ediiei au contribuit:

Anatol Gremalschi, doctor habilitat, profesor universitar, Institutul de Politici Publice

Ion Bolun, doctor habilitat, profesor universitar, Academia de Studii Economice a Moldovei

Iurie Mocanu, ef de direcie, Ministerul Educaiei

Dumitru Ciubati, informatician

Bogdna Denis, informatician

Constantin Dolghieru, informatician

7/30/2019 Brosura ORI 2012

3/44

3

Cuprins

Clasele 7 9 ................................................................................................................. 4Triunghiul lui Pascal .............................................................................................. 5

Semntura digital.................................................................................................. 8Bioinformatic ..................................................................................................... 10Convertorul .......................................................................................................... 13

Roboii ................................................................................................................. 16Turitii ................................................................................................................. 20

Clasele 10 12 ........................................................................................................... 23Semnturadigital................................................................................................ 24Bioinformatic ..................................................................................................... 26Reele................................................................................................................... 29Convertorul .......................................................................................................... 35

Roboii ................................................................................................................. 38Turitii ................................................................................................................. 42

7/30/2019 Brosura ORI 2012

4/44

4

Clasele 7 9Denumirea

problemei

Numrul depuncte alocat

problemei

Denumirea

fiierului surs

Denumirea

fiierului deintrare

Denumirea

fiierului deieire

Triunghiul lui

Pascal100

TRIUNGHI.PAS

TRIUNGHI.C

TRIUNGHI.CPP

TRIUNGHI.IN TRIUNGHI.OUT

Semnturadigital

100SEMN.PAS

SEMN.C

SEMN.CPP

SEMN.IN SEMN.OUT

Bioinformatic 100BIO.PAS

BIO.C

BIO.CPP

BIO.IN BIO.OUT

Convertorul 100CONVERT.PAS

CONVERT.C

CONVERT.CPP

CONVERT.IN CONVERT.OUT

Roboii 100ROBOT.PAS

ROBOT.C

ROBOT.CPP

ROBOT.IN ROBOT.OUT

Turitii 100TURIST.PAS

TURIST.C

TURIST.CPP

TURIST.IN TURIST.OUT

Total 600 - - -

7/30/2019 Brosura ORI 2012

5/44

5

Triunghiul lui Pascal

Triunghiul lui Pascal este un aranjament geometric al unor numere, calculate conform

anumitor reguli. n figura de mai jos este prezentat un triunghi al lui Pascal, format din 6 linii.

11 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

Prima linie a triunghiului este , linia a doua a triunghiului este , linia a treia a

triunghiului este .a.m.d.Construcia triunghiului este condus de dou reguli:

prima linie are un singur numr: 1; linie ulterioar ncepe i se sfrete cu 1, numerele intermediare sunt suma celor dou

numere de pe linia anterioar deasupra i la stnga.

Sarcin. Scriei un program care calculeaz linia n a triunghiului lui Pascal.

Date de intrare.Fiierul text TRIUNGHI.INconine pe o singur linie numrul ntreg n.

Date de ieire.Fiierul text TRIUNGHI.OUT va conine pe o singur linie numerele din linian a triunghiului lui Pascal, separate prin spaiu.

Restricii. . Timpul de execuie nu va depi 0,5 secunde. Programul va folosi celmult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea TRIUNGHI.PAS,TRIUNGHI.C sau TRIUNGHI.CPP.

Exemplu. Pentru triunghiul lui Pascal din enunul problemei, fiierele de intrare i ieire sunt:

TRIUNGHI.IN TRIUNGHI.OUT

6 1 5 10 10 5 1

7/30/2019 Brosura ORI 2012

6/44

6

Rezolvare

Din regulile de calcul ale numerelor din componena triunghiului lui Pascal rezult c oricenumr din linia nnu va depi valoarea de . Conform restriciilor problemei, . Prinurmare, pentru memorarea numerelor respective, n programul n curs de elaborare va trebui sutilizm variabile de tipul longint, care permit memorarea numerelor ntregi cu valori de pn la .

Liniile din componena triunghiului lui Pascal pot fi construite consecutiv, una cte una,pstrnd n memorie doar ultimele dou din ele. n programul ce urmeaz linia n curs deconstrucie este memorat n tabloul , iar linia precedent n tabloul .

ProgramTriunghi;

{ Triunghiul lui Pascal. Clasele 07-09 }

const nmax=30;

var T : array [1..nmax] of longint; { linia curenta a triunghiului }

n : integer; { numarul de linii ale triunghiului }

Procedure Citeste;

var Intrare : text;

begin

assign(Intrare, 'TRIUNGHI.IN');

reset(Intrare);

readln(Intrare, n);

close(Intrare);

end; { Citeste }

procedure Scrie;var Iesire : text;

var i : integer;

begin

assign(Iesire, 'TRIUNGHI.OUT');

rewrite(Iesire);

for i:=1 to n-1 do

write(Iesire, T[i], ' ');

writeln(Iesire, T[n]);

close(Iesire);

end; { Scrie }

procedure ConstruiesteTriunghiul;

var S : array [1..nmax] of longint; { linia precedenta a triunghiului }

k : integer; { lungimea liniei precedente a triunghiului }

i, j : integer;

label 1;

begin

if n=1 thenbegin T[1]:=1; goto 1; end;

if n=2 thenbegin T[1]:=1; T[2]:=1; goto 1; end;

S[1]:=1; S[2]:=1; k:=2;

for i:=3 to n do

begin

T[1]:=1;

for j:=2 to k do T[j]:=S[j-1]+S[j];

T[k+1]:=1;

7/30/2019 Brosura ORI 2012

7/44

7

k:=k+1;

for j:=1 to k do S[j]:=T[j];

end; { for }

1: end; { ConstruiesteTriunghiul }

begin

Citeste;

ConstruiesteTriunghiul;

Scrie;

end.

Din analiza textului procedurii ConstruiesteTriunghiul rezult c aceast procedurconine dou cicluri imbricate for. Evident, numrul de execuii ale instruciunilor din componenaciclurilor imbricate nu va depi valoarea de , mrime cu mult mai mic dect capacitatea de

prelucrare a calculatoarelor personale din laboratorul de Informatic. Prin urmare, timpul de calculcerut de procedura ConstruiesteTriunghiulva fi cu mult mai mic dect 0,5 secunde.

7/30/2019 Brosura ORI 2012

8/44

8

Semntura digital

Fiind prieteni de nedesprit, Pcal i Tndal au elaborat o metod proprie de semnturdigital. Aceast metod const n urmtoarele.

Fie Sun ir de caractere ce reprezintconinutul documentului electronic ce trebuie semnat.

Fie Qun numr natural, denumit cheia secret, cunoscut doar de Pcal i Tndal.Evident, cheia secret nu poate fi inserat n documentul electronic n calitate de semntur

digital, ntruct orice persoana strin poate s o copie i, ulterior, s semneze el nsui n locullui Pcal sau Tndal.

n consecin, prietenii au convenit, ca n calitate de semntur digital, n documentulelectronic s fie inserat nu cheia secret Q, ci un numrul naturalN, valoarea cruia depinde attde cheia secret, ct i de coninutul documentului S.

Semntura digitalNse calculeaz conform urmtoarei formule secrete:

,

unde este caracterul idin irul S, iar funcia ce returneaz numrul de ordine alcaracterului conform tabelului de codificare al mediului de programare.

Pentru exemplificare, presupunem c cheia secret , iar irul de caractere cereprezint coninutul documentul electronic ce trebuie semnat este . Conform metodei luiPcal i Tndal, se calculeaz

,

numrul 1379 fiind inserat ndocumentul electronic n calitate de semntur digital.

Sarcin. Scriei un program, care, cunoscnd cheia secret Q i irul de caractere S,calculeaz semntura digitalN.

Date de intrare.Fiierul text SEMN.INconine pe prima linie numrul ntreg Q. Linia a douaa fiierului de intrare conine irul de caractere S.

Date de ieire.Fiierul text SEMN.OUT va conine pe o singur linie numrul ntregN.

Restricii. . irul Seste format din cel mult 255 caractere. Timpul de execuienu va depi 0,1 secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ.Fiierul surs va avea denumirea SEMN.PAS, SEMN.C sau SEMN.CPP.

Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

SEMN.IN SEMN.OUT

987

ABA

1379

7/30/2019 Brosura ORI 2012

9/44

9

Rezolvare

Conform restriciilor din enunul problemei, .Evident, pentru reprezentarea numruluiNtrebuie utilizat tipul de date longint, care permite prelucrareanumerelor naturale cu valori de pn la .

ProgramSemnaturaDigitala;

{ Clasele 07-09 }

var S : string;

Q : integer;

N : longint;

procedure Citeste;

var Intrare : text;

begin

assign(Intrare, 'SEMN.IN');

reset(Intrare);

readln(Intrare, Q);

readln(Intrare, S);close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'SEMN.OUT');

rewrite(Iesire);

writeln(Iesire, N);

close(iesire);

end; { Scrie }

procedure CalculeazaSemnatura;var i : integer;

begin

N:=Q;

for i:=1 to length(S) do N:=N+i*ord(S[i]);

end; { CalculeazaSemnatura }

begin

Citeste;

CalculeazaSemnatura;

Scrie;

end.

Din analiza textului procedurii CalculeazaSemnaturarezult c aceast procedur coninedoar un singur ciclu for. Evident, instruciunea din componena acestui ciclu va fi executat de celmult 255, mrime neglijabil n comparaie cu capacitatea de prelucrare a calculatoarelor p ersonaledin laboratorul de Informatic. Prin urmare, timpul de calcul cerut de proceduraCalculeazaSemnaturava fi cu mult mai mic dect 0,1 secunde.

7/30/2019 Brosura ORI 2012

10/44

10

Bioinformatic

Bioinformatica este o tiin, care utilizeaz metodele informaticii pentru a studiafenomenelor biologice.

Se consider o imagine digital, preluat cu ajutorul microscopului, pe care sunt reprezentatemai multe bacterii. Imaginea digital conine ptrelede culoare deschis, ce reprezint fundalul, i

ptrele de culoare nchis, ce reprezint bacteriile (vezidesenul).

Fiecare bacterie reprezint o figur conex. Amintim, c ofigura se numete conex, dac din orice ptrel al ei se poateajunge n oricare altul, traversnd doar laturile comune ale

ptrelelor vecine.

n memoria calculatorului imaginea digital estereprezentat printr-un tablou format din numere ntregi, cu n linii

i m coloane. Fiecare din elementele tabloului poate lua valoarea0 ptrel de culoare deschisa sau valoarea 1 ptrel deculoare nchisa.

Biologul este interesat de numrul de bacterii din imaginea digital.

Sarcin. Scriei un program, care calculeaz numrul de bacterii din imaginea digital.

Date de intrare.Fiierul text BIO.INconine pe prima linie numerele ntregi n, m separateprin spaiu.Fiecare din urmtoarele n linii ale fiierului de intrare conine cte mnumere ntregiseparate prin spaiu, care reprezint culorile ptrelelor respective ale imaginii digitale.

Date de ieire. Fiierul text BIO.OUT va conine pe o singur linie un numr ntreg

numrul de bacterii de pe imaginea digital.Restricii. . Timpul de execuie nu va depi o secund. Programul va folosi

cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea BIO.PAS, BIO.Csau BIO.CPP.

Exemplu. Pentru imaginea digital din enunul problemei, fiierele de intrare i ieire sunt:

BIO.IN BIO.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

6

7/30/2019 Brosura ORI 2012

11/44

11

Rezolvare

Numrul de bacterii kpoate fi calculatprin tergerea consecutiv din imaginea digital a cteo bacterie:

1) iniial stabilim ;2) parcurgnd imaginea de sus n jos, de la stnga la dreapta, selectm primul ptrel de

culoare nchis;3) stabilim i tergem din imaginea digital bacteria la care aparine ptrelul

selectat anterior;

4) repetm punctele 2 i 3 pn cnd vom parcurge toat imaginea.tergerea fiecrei bacterii poate fi realizat cu ajutorul unui subprogram recursiv dup cum

urmeaz.Presupunem cptrelul curent este de culoare nchis, adic conine valoarea 1.

Pentru nceput, tergemptrelul respectiv, nscriind n el valoarea 0. n continuare, analizm

fiecare din ptrelele de sus , de jos , din stnga i din dreapta . n cazul n care ptrelul analizat este de culoare nchis, adic conine valoarea 1,nscriem n el valoarea 0 i relum analiza recursiv.

Pentru a evita verificrile de la marginile imaginii digitale, n programul ce urmeaz imagineacitit din fiierul de intrareeste ncadratn zerouri.

ProgramBioinformatica;

{ Clasele 07-09 }

const nmax=100; mmax=100;

var

{ imaginea digitala }

A : array [0..nmax+1, 0..mmax+1] of integer;

n, m : integer;

{ numarul de bacterii }

k : integer;

procedure Citeste;

var i, j : integer;

Intrare : text;

begin

{ citim imaginea din fisierul de intrare }

assign (Intrare, 'BIO.IN');

reset (Intrare);

readln(Intrare, n, m);

for i:=1 to n do

begin

for j:=1 to m do read(Intrare, A[i, j]);

readln (Intrare);

end; {for i }

close(Intrare);

{ incadram imaginea intr-un chenar din zerouri }

for j:=0 to m+1 do A[0, j]:=0;

for j:=0 to m+1 do A[n+1, j]:=0;

for i:=0 to n+1 do A[i, 0]:=0;

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

end; { Citeste }

procedure Scrie;

var Iesire : text;begin

assign(Iesire, 'BIO.OUT');

7/30/2019 Brosura ORI 2012

12/44

12

rewrite(Iesire);

writeln(Iesire, k);

close(Iesire);

end; { Scrie }

procedure StergeBacteria(i, j : integer);

{ Sterge bacteria pornind de la patratelul A[i, j] }

begin

A[i, j]:=0;

if A[i-1, j]=1 then StergeBacteria(i-1, j);

if A[i+1, j]=1 then StergeBacteria(i+1, j);

if A[i, j-1]=1 then StergeBacteria(i, j-1);

if A[i, j+1]=1 then StergeBacteria(i, j+1);

end; { StergeBacteria }

procedure NumaraBacteriile;

{ Numara bacteriile din imagine }

var i, j : integer;

begin

k:=0;

for i:=1 to n do

for j:=1 to m do

if A[i, j]=1 then

begin

k:=k+1;

StergeBacteria(i, j);

end; {if }

end; { NumaraBacteriile }

begin

Citeste;

NumaraBacteriile;

Scrie;

end.

Din analiza textului procedurii NumaraBacteriile rezult c instruciunea if dincomponena ciclurilor imbricate forva fi efectuat de ori. La rndul su, numrul de apelurirecursive ale procedurii StergeBacterianu poate depi numrul de ptrele . Prin urmare,complexitatea temporala a programului este de ordinul . Conform restriciilor problemei, . Evident, n condiiile problemei, numrul de operaii cerut de program va fi

proporional cu , mrime mai mic dect capacitatea de prelucrare a calculatoarelor personale.Prin urmare, timpul de execuia a programului va fi mai mic ca o secund.

7/30/2019 Brosura ORI 2012

13/44

13

Convertorul

Fiind mptimit de informatic, Ion a construit un dispozitiv digital, pe care l-a denumitconvertor. Acest dispozitiv accepta la intrare numerele naturale ascrise n baza bi furnizeaz laieire numerele respective, scrise n baza 10 (vezi figura de mai jos).

De exemplu, dac la intrarea convertorului este aplicat numrul , iar , la ieireaconvertorului va aprea numrul zecimal .

Amintim, c n sistemele de numeraie n baza b, , se utilizeaz urmtoarele cifre: 0, 1,2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Ion a mprumutat convertorul prietenei sale Lenua, care, fiind i ea mptimit deinformatic, a decis s elaboreze un program ce simuleaz funcionarea convertorului.

Sarcin. Scriei un program, care, cunoscnd numrul ade la intrarea convertorului i baza bn care este scris acest numr, calculeaz numrul zecimalzde la ieirea convertorului.

Date de intrare. Fiierul text CONVERT.IN conine pe prima linie un ir de caractere cereprezint numrul a scris n baza b. Linia a doua a fiierului de intrare conine baza b, scris nsistemul zecimal.

Date de ieire. Fiierul text CONVERT.OUT va conine pe o singur linie numrul ntreg

zecimalz.

Restricii. . Numrul a este format din cel mult apte caractere. Timpul deexecuie nu va depi 0,1 secunde. Programul va folosi cel mult 32 Megaoctei de memorieoperativ. Fiierul surs va avea denumirea CONVERT.PAS, CONVERT.C sau CONVERT.CPP.

Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

CONVERT.IN CONVERT.OUT

121

3

16

ba z

7/30/2019 Brosura ORI 2012

14/44

14

Rezolvare

Admitem c numrul naturalNeste format din 1n cifre:

011... ccccN

nn .

Valoarea acestui numr se calculeaz n funcie de baza sistemului de numeraie bdup cum urmeaz:

0

0

1

1

1

1)( bcbcbcbcNn

n

n

nb

.

Prin urmare, pentru a transforma numrul adin fiierul de intrare n numrul zecimalz, parcurgem irulrespectiv de caractere de la dreapta la stnga, nmulim fiecare cifr cu semnificaia rangului respectiv insumm produsele obinute. ntruct numrul a conine cel mult apte cifre, valoarea lui maximal este

. n consecin, ]n cayul mediului de programare Turbo Pascal,variabilaz, care reprezint numrul zecimal de la ieirea convertorului, trebuie s fie de tipul longint.

Pentru a transforma cifrele din componena irului de caractere a de la intrarea convertorului n valorinumerice, n programul ce urmeaz este folosit funcia ord, care returneaz numerele de ordine alecaracterului conform tabelului de codificare utilizat mediul respectiv de programare. Valoarea numeric afiecrei cifre poate fi calculat cunoscnd numerele de ordine ale caracterelor0iA.

ProgramConvert;

{ Clasele 07-09 }

var a : string;

b : integer;

z : longint;

procedure Citeste;

var Intrare : text;

begin

assign(Intrare, 'CONVERT.IN');

reset(Intrare);readln(Intrare, a);

readln(Intrare, b);

close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'CONVERT.OUT');

rewrite(Iesire);

writeln(Iesire, z);

close(Iesire);

end; { Citeste }

procedure Convertor;

{ Transforma a in z }

var i : integer; { rangul cifrei }

c : integer; { valoarea cifrei curente }

p : longint; { semnificatia rangului }

begin

z:=0;

p:=1;

for i:=length(a) downto 1 do

begin

if a[i] in ['0'..'9'] then c:= ord(a[i])-ord(0)

else c:= ord(a[i])-ord(A)+10;

z:=z+c*p;

p:=p*b;

end;

7/30/2019 Brosura ORI 2012

15/44

15

end; { Convertor }

begin

Citeste;

Convertor;

Scrie;

end.

Din analiza textului procedurii Convertorrezult c aceast procedur conine doar un singurciclu for. Evident, instruciunile din componena acestui ciclu vor fi executate de cel mult apte ori,mrime neglijabil n comparaie cu capacitatea de prelucrare a calculatoarelor personale dinlaboratorul de Informatic. Prin urmare, timpul de calcul cerut de procedura Convertor va fi cumult mai mic dect 0,1 secunde.

7/30/2019 Brosura ORI 2012

16/44

16

Roboii

Se consider un cmp dreptunghiularde lucru, divizat n ptrele (vezi desenul). Ptrelelelibere sunt de culoare alb, iar cele cu obstacole de culoare nchis. Pe cmpul de lucru, n

ptrele libere, se afl doi roboi. Fiecare robot sepoate deplasa din ptrelul curent n ptrelulvecin doar prin latura comun a acestora. Evident, roboii se potdeplasa doar prin ptrelele libere.

Iniial, ambii roboi sunt n starea de repaus. Dup sosireacomenzii START, roboii ncep s se deplaseze, viteza de deplasarefiind de un ptrel n fiecare unitate de timp. Fiecare robot se poateopri ori de cte ori el consider c acest lucru este necesar. Numrulde roboi, care concomitent se pot afla ntr-un ptrel liber, nu estelimitat.

Sarcin. Scriei unprogram, care calculeaz timpul minim, necesar pentru ca ambii roboi s

se adune n unul din ptrelele libere ale cmpului de lucru. Date de intrare.n memoria calculatorului cmpul de lucru este reprezentat printr-un tablou

format din numere ntregi, cu nlinii i m coloane. Fiecare din elementele tabloului poate lua una dinurmtoarele valori: 0 ptrel liber; 1 ptrel ce conine un obstacol; 2 ptrel liber n carese afl un robot.

Fiierul text ROBOT.IN conine pe prima linie numerele ntregi n, m separate prin spaiu.Fiecare din urmtoarele n linii ale fiierului de intrare conine cte mnumere ntregi separate prinspaiu, care reprezint ptrelele respective ale cmpului de lucru.

Date de ieire. Fiierul text ROBOT.OUT va conine pe o singur linie un numr ntreg timpul minim, necesar pentru ca ambii roboii se adune n unul din ptrelele libere ale cmpuluide lucru.

Restricii. . Se garanteaz c ambii roboi se pot aduna nunul din ptrelelelibere ale cmpului de lucru.Timpul de execuie nu va depi o secund. Programul va folosi celmult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea ROBOT.PAS,ROBOT.C sau ROBOT.CPP.

Exemplu. Pentru desenul din enunul problemei, fiierele de intrare i ieire sunt:

ROBOT.IN ROBOT.OUT

5 6

1 2 0 0 0 0

1 0 1 1 1 00 0 0 0 0 0

0 1 1 1 0 1

0 0 0 0 2 0

4

Timpul minim se obine n cazul n care ambii roboi se adun, de exemplu, nptrelul aflat la intersecia rndului 3 i a coloanei 4. Pe desenul de mai sus acest ptrel estemarcat printr-un punct.

7/30/2019 Brosura ORI 2012

17/44

17

Rezolvare

Pentru a rezolva problema, vom cuta cel mai scurt drum, care leag ptrelele n care seafl roboii. n acest scop vom simula propagarea unei unde numerice, care pornete din ptreluln care se afl primul robot.

Vom nota prin kvaloarea undei numerice. Evident, n cazul ptrelului n care se afl primulrobot, . Pentru a propaga unda numeric, nscriem n toate ptrelele libere, care sunt vecinecu ptrelul n care se afl primul robot, valoarea . n continuare, parcurgemcmpul de lucru i nscriem n toateptrelele libere, vecine cu cele ce conin valoarea curentk,

valoarea . Repetm acest proces pentru .a.m.d.,pn cnd unda numeric va ajunge n ptrelul n care se aflrobotul al doilea. Pentru exemplificare, pe desenul alturat sunt

prezentate rezultatele propagrii undei numerice pentru roboii dinenunul problemei.

Din modul de propagare a undei numerice rezult c valoarea

k, nscris n ptrelul n care se afl robotul al doilea, reprezintlungimea celui mai scurt drum, mai exact numrul de ptreleminus doi, pe care trebuie s le parcurg primul robot pentru aajunge la robotul al doilea.

ntruct de-a lungul celui mai scurt drum roboii se pot mica unul n ntmpinarea celuilalt,timpul tcerut n enunul problemei poate fi gsit prin njumtirea lungimii celui mai scurt drum:

.

n cazul exemplului din enunul problemei, valoarea undei numerice nscrise n ptrelul ncare se afl robotul al doilea este . Prin urmare, timpul necesar pentru ca ambii roboi s seadune mpreun ntr-un singur ptrel este . Roboii se pot aduna fie n ptrelul , fie n

ptrelul , ambele din ele aflndu-se la mijlocul celui mai scurt drum.

n programul ce urmeaz cmpul de lucru al roboilor este memorat n tabloul bidimensionalC, iar coordonatele robotului al doilea sunt notate prin . Pentru a evita verificrile de lamargini, cmpurile de lucru sunt ncadrate n chenare formate din obstacole.

ProgramRobotii;

{ Clasele 07-09 }

const nmax=40; mmax=40;

var C : array[0..nmax+1, 0..mmax+1] of integer;

n, m : integer;

t : integer;x, y : integer; { coordonatele robotului doi }

procedure Citeste;

var i, j : integer;

Intrare : text;

begin

assign(Intrare, 'ROBOT.IN');

reset(Intrare);

readln(Intrare, n, m);

for i:=1 to n do

begin

for j:=1 to m-1 do read(Intrare, C[i, j]);

readln(Intrare, C[i, m]);end;

close(Intrare);

{ incadram campul intr-un chenar de obstacole }

7/30/2019 Brosura ORI 2012

18/44

18

for j:=0 to m+1 do C[0, j]:=1;

for j:=0 to m+1 do C[n+1, j]:=1;

for i:=0 to n+1 do C[i, 0]:=1;

for i:=0 to n+1 do C[i, m+1]:=1;

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'ROBOT.OUT');

rewrite(Iesire);

writeln(Iesire, t);

close(Iesire);

end; { Scrie }

procedure AflaCoordonateleRobotuluiDoi;

{ Inscrie in x, y coordonatele robotului doi }

{ Inscrie in patratelul respectiv valoarea 0 }

label 1;

var i, j : integer;

begin

for i:=n downto 1 do

for j:=m downto 1 do

if (C[i, j]=2) then

begin

C[i, j]:=0;

x:=i; y:=j;

goto 1;

end;

1: end; { AflaCoordonateleRobotuluiDoi }

procedure PropagaUndaNumerica;

{ Propaga unda numerica in campul C }

label 1;

var i, j : integer;

k : integer; { valoarea curenta a undei numerice }

Ind : boolean; { indicator }

begin

k:=1;

repeat

k:=k+1;

Ind:=true;

for i:=1 to n do

for j:=1 to m do

if C[i, j]=k then

begin

if (i=x) and(j=y) thengoto 1;

if C[i-1, j]=0 thenbegin C[i-1, j]:=k+1; Ind:=false; end;

if C[i+1, j]=0 then

begin C[i+1, j]:=k+1; Ind:=false; end;

if C[i, j-1]=0 then

begin C[i, j-1]:=k+1; Ind:=false; end;

if C[i, j+1]=0 then

begin C[i, j+1]:=k+1; Ind:=false; end;

end;

until Ind;

1: t:=(k-2) div 2 + (k-2)mod2;

end; { PropagaUndaNumerica }

beginCiteste;

AflaCoordonateleRobotuluiDoi;

PropagaUndaNumerica;

7/30/2019 Brosura ORI 2012

19/44

19

Scrie;

end.

Din analiza textelor procedurilor din programul de mai sus rezult c cel mai mare numr deoperaii se efectueaz n cazul propagrii undei numerice. Astfel, proceduraPropagaUndaNumerica conine trei cicluri imbricate: repeat ... for ... for ... .Instruciunile ifdin componena acestor cicluri vor fi efectuate de cel mult ori, unde keste

lungimea celui mai lung drum de pe cmpul de lucru. ntruct , timpul cerut de aceastprocedur va fi proporional cu . Conform restriciilor problemei, . Prin urmare,timpul cerut de programul Robotiiva fi proporional cu , mrime cu multmai mic dect capacitatea de prelucrare a calculatoarelor personale.

7/30/2019 Brosura ORI 2012

20/44

20

Turitii

Un grup de elevi a decis s fac o excursie de-a lungul rului Prut. Rul Prut are mai muliaflueni, care se vars n el att din partea stng, ct i din partea dreapt. Pe desenul alturat, rul

Prut este simbolizat printr-o dreapt vertical, iar afluenii lui

prin drepte orizontale mai subiri.Elevii intenioneaz s nceap excursia de la nord, din

punctulAde pe malul stng, i s o termine la sud, n punctulB de pe malul drept.

Elevii au studiat foarte atent harta i au ajuns laconcluzia c exist mai multe variante de a ajunge din

punctulA n punctulB, ns, indiferent de varianta aleas, eivor trebui s traverseze att rul, ct i unii aflueni aiacestuia. Pentru elevi, traversarea rului i a afluenilorreprezint o sarcin dificil i, evident, ei ar dori s aleag o

cale, pentru care numrul de traversri s fie ct mai mic. Pentru exemplificare, pe desenul alturat, o astfel de

cale este simbolizat printr-o linie ntrerupt.

Sarcin. Scriei un program, care calculeaz numrulminim de traversri, pe care elevii vor fi nevoii s le fac

pentru a ajunge din punctulAn punctulB.

Date de intrare.Fiierul text TURIST.INconine peo singur linie un ir de caractere, format din literele L,R,B.Acest ir descrie poriunea de ru, cuprins ntre punctele AiB. LiteraLsemnific faptul c afluentul curent se vars n rudin stnga, literaRfaptul c afluentul curentse vars n rudin dreapta, iar literaBfaptul c n ru, n acelai punct, sevars doi aflueni, cte unul din fiecare parte. Literele L,RiBapar n ir conform direciei preconizate a excursiei: de-alungul rului, de la nord la sud.

Date de ieire.Fiierul text TURIST.OUTva conine pe o singur linie un numr ntreg numrul minim de traversri.

Restricii.irul de caractere din fiierul de intrare va conine cel mult 1000 de litere. Timpulde execuie nu va depi o secund. Programul va folosi cel mult 32 Megaoctei de memorie

operativ. Fiierul surs va avea denumirea TURIST.PAS, TURIST.C sau TURIST.CPP.Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

TURIST.IN TURIST.OUT

LLBLRRBRL 5

7/30/2019 Brosura ORI 2012

21/44

21

Rezolvare

Problema poate fi rezolvat prin metoda programrii dinamice. n acest scop, vom nota prin irul de caractere din fiierul de intrare. Prin fiecare dreapt, ce simbolizeazun afluent, vom trasa cte o linie orizontal, care trece i de partea cealalt a rului.

Zonele formate de dreptele orizontale trasate de noi le vom numerota prin 0, 1, 2, 3 .a.m.d.,de sus n jos, ncepnd cu zona n care se afl punctul A.Evident, punctul B se va afla n zona n, pe malul drept alrului.

Introducem n studiu urmtoarele notaii:

numrul minim de traversri pe care trebuie s lefac elevii pentru a ajunge din punctul A ntr-un punct de pemalul drept al zonei ;

numrul minim de traversri pe care trebuie s lefac elevii pentru a ajunge din punctul A ntr-un punct de pe

malul stng al zonei .Evident, i .Presupunem c sunt deja cunoscute valorile minime

i se dorete calcularea valorilor minime .

Din zona elevii pot ajunge ntr-un punct de pemalul drept al zonei prin una din urmtoarele dou ci:

1)Fr ca s traverseze rul. n acest caz, numrul detraversri va fi dac pe malul drept, ntre zonele i , exist un afluent i n caz contrar.

2)Traversnd rul. n acest caz, numrul de traversri vafi ) dac pe malul stng, ntre zonele i ,

exist un afluent i n caz contrar.Prin urmare, numrul minim de traversri poate fi calculat cu ajutorul urmtoarei formule

recurente:

,

unde:

este o variabil care ia valoarea 1, dac pe malul drept, ntre zonele i , exist unafluent i 0 n caz contrar. Evident, un astfel de afluent exist doar atunci, cnd caracterul din

fiierul de intrare are valoareaR sauB;este o variabil care ia valoarea 1, dac pe malul stng, ntre zonele i , exist un

afluent i 0 n caz contrar. Evident, un astfel de afluent exist doar atunci, cnd caracterul dinfiierul de intrare are valoareaL sauB.

ntr-un mod similar se deduce i formula recurent pentru calcularea numrului minim detraversri :

Evident, valoarea reprezint numrul minim de traversri pe care trebuie s le fac eleviipentru a ajunge din punctulAn punctulB.

ProgramTuristii;

{ Clasele 07-09 }

const nmax=1000;

7/30/2019 Brosura ORI 2012

22/44

22

var S : array[1..nmax] of char;

n : longint;

p0, q0, p1, q1 : longint;

procedure Citeste;

var Intrare : text;

i : longint;

begin

assign(Intrare, 'TURIST.IN');

reset(Intrare);

i:=1;

repeat

read(Intrare, S[i]);

i:=i+1;

until eoln(Intrare);

n:=i-1;

close(intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'TURIST.OUT');

rewrite(Iesire);

writeln(Iesire, p1);

close(Iesire);

end; { Scrie }

procedure Calculeaza;

var g, h : integer;

i : longint;

begin

p0:=1; q0:=0;

for i:=1 to n do

beginif (S[i]='R') or (S[i]='B') then g:=1 else g:=0;

if (S[i]='L') or (S[i]='B') then h:=1 else h:=0;

if (p0+g) < (q0+h+1) then p1:=(p0+g) else p1:=(q0+h+1);

if (q0+h) < (p0+g+1) then q1:=(q0+h) else q1:=(p0+g+1);

p0:=p1; q0:=q1;

end;

end; { Cacluleaza }

begin

Citeste;

Calculeaza;

Scrie;

end.

Din analiza textului procedurii Calculeazase observ c instruciunile ifdin componenaciclului for vor fi executate de nori. Conform restriciilor problemei, . Evident, valoarealui neste cu mult mai mic dect capacitatea de prelucrare a calculatoarelor personale. Prin urmare,timpul cerut de program va fi cu mult mai mic dect o secund.

7/30/2019 Brosura ORI 2012

23/44

23

Clasele 10 12

Denumirea

problemei

Numrul depuncte alocat

problemei

Denumirea

fiierului surs

Denumirea

fiierului deintrare

Denumirea

fiierului deieire

Semnturadigital

100SEMN.PAS

SEMN.C

SEMN.CPP

SEMN.IN SEMN.OUT

Bioinformatic 100BIO.PAS

BIO.C

BIO.CPP

BIO.IN BIO.OUT

Reele 100RETEA.PAS

RETEA.C

RETEA.CPP

RETEA.IN RETEA.OUT

Convertorul 100CONVERT.PAS

CONVERT.C

CONVERT.CPP

CONVERT.IN CONVERT.OUT

Roboii 100ROBOT.PAS

ROBOT.C

ROBOT.CPP

ROBOT.IN ROBOT.OUT

Turitii 100TURIST.PAS

TURIST.C

TURIST.CPP

TURIST.IN TURIST.OUT

Total 600 - - -

7/30/2019 Brosura ORI 2012

24/44

24

Semntura digital

Fiind prieteni de nedesprit, Pcal i Tndal au elaborat o metod proprie de semnturdigital. Aceast metod const n urmtoarele.

Fie Sun ir de caractere ce reprezintconinutul documentului electronic ce trebuie semnat.

Fie Qun numr natural, denumit cheia secret, cunoscut doar de Pcal i Tndal.Evident, cheia secret nu poate fi inserat n documentul electronic n calitate de semntur

digital, ntruct orice persoana strin poate s o copie i, ulterior, s semneze el nsui n locullui Pcal sau Tndal.

n consecin, prietenii au convenit, ca n calitate de semntur digital, n documentulelectronic s fie inserat nu cheia secret Q, ci un numrul naturalN, valoarea cruia depinde attde cheia secret, ct i de coninutul documentului S.

Semntura digitalNse calculeaz conform urmtoarei formule secrete:

,

unde este caracterul idin irul S, iar funcia ce returneaz numrul de ordine alcaracterului conform tabelului de codificare al mediului de programare.

Pentru exemplificare, presupunem c cheia secret , iar irul de caractere cereprezint coninutul documentul electronic ce trebuie semnat este . Conform metodei luiPcal i Tndal, se calculeaz

numrul 1674479 fiind inserat ndocumentul electronic n calitate de semntur digital.

Sarcin. Scriei un program, care, cunoscnd cheia secret Q i irul de caractere S,calculeaz semntura digitalN.

Date de intrare.Fiierul text SEMN.INconine pe prima linie numrul ntreg Q. Linia a douaa fiierului de intrare conine irul de caractere S.

Date de ieire.Fiierul text SEMN.OUT va conine pe o singur linie numrul ntregN.

Restricii. . irul Seste format din cel mult 255 caractere. Timpul de execuienu va depi 0,1 secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ.

Fiierul surs va avea denumirea SEMN.PAS, SEMN.C sau SEMN.CPP.

Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

SEMN.IN SEMN.OUT

987

ABA

1674479

7/30/2019 Brosura ORI 2012

25/44

25

Rezolvare

Conform restriciilor din enunul problemei, = . Tipurile de date integerilongintnu permit memorarea i prelucrarea unornumere att de mari. Prin urmare, se va folosi tipul de date QWord din mediul de programare Free Pascal,

care permite prelucrarea numerelor naturale cu valori de pn la .

ProgramSemnaturaDigitala;

{ Clasele 10-12 }

var S : string;

Q : integer;

N : QWord;

procedure Citeste;

var Intrare : text;

begin

assign(Intrare, 'SEMN.IN');

reset(Intrare);

readln(Intrare, Q);

readln(Intrare, S);

close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'SEMN.OUT');

rewrite(Iesire);

writeln(Iesire, N);

close(iesire);end; { Scrie }

procedure CalculeazaSemnatura;

var i : integer;

begin

N:=Q;

for i:=1 to length(S) do N:=N+i*ord(S[i])*ord(S[i])*ord(S[i]);

end; { CalculeazaSemnatura }

begin

Citeste;

CalculeazaSemnatura;Scrie;

end.

Din analiza textului procedurii CalculeazaSemnatura rezult c aceast procedur coninedoar un singur ciclu for. Evident, instruciunea din componena acestui ciclu va fi executat de celmult 255 de ori, mrime neglijabil n comparaie cu capacitatea de prelucrare a calculatoarelor

personale din laboratorul de Informatic. Prin urmare, timpul de calcul cerut de proceduraCalculeazaSemnatura va fi cu mult mai mic dect 0,1 secunde.

7/30/2019 Brosura ORI 2012

26/44

26

Bioinformatic

Bioinformatica este o tiin, care utilizeaz metodele informaticii pentru a studiafenomenelor biologice.

Se consider o imagine digital, preluat cu ajutorulmicroscopului, pe care sunt reprezentate mai multe bacterii.

Imaginea digital conine ptrele de culoare alb, carereprezint fundalul, i ptrele de alte culori, care reprezint

bacteriile (vezi desenul).

n memoria calculatorului imaginea digital estereprezentat printr-un tablou format din numere ntregi, cu nlinii i m coloane. Fiecare din elementele tabloului poate luavaloarea 0 ptrel de culoare alb sau una din valorile 1, 2,3, , k, care reprezint culoarea ptrelului respectiv. Deexemplu, culoarea roie este reprezentat prin valoarea 1,

culoarea verde prin valoarea 2, culoarea galben prin valoarea 3 .a.m.d.

Fiecare bacterie reprezint o figur conex, format din ptrele de aceiai culoare. Amintim,c o figura se numete conex, dac din orice ptrel al ei se poate ajunge n oricare altul,traversnd doar laturile comune ale ptrelelor vecine.

Biologul este interesat de numrul de bacterii de fiecare culoare.

Sarcin. Scriei un program, care calculeaz numrul de bacterii de fiecare culoare depe imaginea digital.

Date de intrare. Fiierul text BIO.IN conine pe prima linie numerele ntregi n, m, kseparate prin spaiu. Fiecare din urmtoarele nlinii ale fiierului de intrare conine cte m numerentregi separate prin spaiu, care reprezintculorile ptrelelorrespective ale imaginii digitale.

Date de ieire. Fiierul text BIO.OUT va conine pe o singur linie numerele ntregi , separate prin spaiu.

Restricii. ; . Timpul de execuie nu va depi o secund. Programul vafolosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea BIO.PAS,BIO.C sau BIO.CPP.

Exemplu. Pentru imaginea digital din enunul problemei, fiierele de intrare i ieire sunt:

BIO.IN BIO.OUT7 8 3

0 0 2 0 3 3 0 1

1 0 0 0 0 0 0 0

1 0 3 3 3 3 2 0

1 0 3 0 0 0 2 0

0 0 3 3 3 3 2 0

3 0 0 0 0 0 0 0

2 3 0 0 0 0 0 0

2 3 4

7/30/2019 Brosura ORI 2012

27/44

27

Rezolvare

Numrul de bacterii de fiecare culoare poate fi calculat prin tergereaconsecutiv din imaginea digital a cte o bacterie:

5) iniial stabilim

;

6) parcurgnd imaginea de sus n jos, de la stnga la dreapta, selectm primul ptrelcolorat;

7) stabilim , unde qeste culoarea ptrelului selectat i tergem din imagineadigital bacteria la care aparine ptrelul selectat anterior;

8) repetm punctele 2 i 3 pn cnd vom parcurge toat imaginea.tergerea consecutiv a bacteriilorpoate fi realizat cu ajutorul unui subprogram recursiv

dup cum urmeaz.Presupunem c ptrelul curent este colorat, adic conine valoareaq, . Pentru

nceput, tergemptrelul respectiv, nscriind n el valoarea 0. n continuare, analizm fiecare

dinptrelele de sus , de jos , din stnga i din dreapta . ncazul n care culoarea ptrelului analizat este q, nscriem n el valoarea 0 i relum analizarecursiv.

Pentru a evita verificrile de la marginile imaginii digitale, n programul ce urmeaz imagineacitit din fiierul de intrareeste ncadratn zerouri.

ProgramBioinformatica;

{ Clasele 10-12 }

const nmax=100; mmax=100; kmax=9;

var

{ imaginea digitala }A : array [0..nmax+1, 0..mmax+1] of integer;

n, m : integer;

{ numarul de culori }

k : integer;

{ numarul de bacterii de fiecare culoare }

B : array [1..kmax] of integer;

procedure Citeste;

var i, j : integer;

Intrare : text;

begin

{ citim imaginea din fisierul de intrare }

assign (Intrare, 'BIO.IN');reset (Intrare);

readln(Intrare, n, m, k);

for i:=1 to n do

begin

for j:=1 to m do read(Intrare, A[i, j]);

readln (Intrare);

end; {for i }

close(Intrare);

{ incadram imaginea intr-un chenar din zerouri }

for j:=0 to m+1 do A[0, j]:=0;

for j:=0 to m+1 do A[n+1, j]:=0;

for i:=0 to n+1 do A[i, 0]:=0;

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

procedure Scrie;

7/30/2019 Brosura ORI 2012

28/44

28

var Iesire : text;

i : integer;

begin

assign(Iesire, 'BIO.OUT');

rewrite(Iesire);

for i:=1 to k-1 do write(Iesire, B[i], ' ');

writeln(Iesire, B[k]);

close(Iesire);

end; { Scrie }

procedure StergeBacteria(q, i, j : integer);

{ Sterge bacteria de culoarea q pornind de la patratelul A[i, j] }

begin

A[i, j]:=0;

if A[i-1, j]=q then StergeBacteria(q, i-1, j);

if A[i+1, j]=q then StergeBacteria(q, i+1, j);

if A[i, j-1]=q then StergeBacteria(q, i, j-1);

if A[i, j+1]=q then StergeBacteria(q, i, j+1);

end; { StergeBacteria }

procedure NumaraBacteriile;

{ Numara bacteriile din imagine }

var q, i, j : integer;

begin

for q:=1 to k do B[q]:=0;

for i:=1 to n do

for j:=1 to m do

if A[i, j]0 then

begin

q:=A[i, j];

B[q]:=B[q]+1;

StergeBacteria(q, i, j);

end; {if }

end; { NumaraBacteriile }

begin

Citeste;

NumaraBacteriile;

Scrie;

end.

Din analiza textului procedurii NumaraBacteriile rezult c instruciunea if dincomponena ciclurilor imbricate forva fi efectuat de ori. La rndul su, numrul de apelurirecursive ale procedurii StergeBacteria nu poate depi numrul de ptrele . Prinurmare, complexitatea temporala a programului este de ordinul . Conform restriciilor

problemei, . Evident, n condiiile problemei, numrul de operaii cerut de programva fi proporional cu , mrime mai mic dect capacitatea de prelucrare a calculatoarelor

personale. Prin urmare, timpul de execuia a programului va fi mai mic ca o secund.

7/30/2019 Brosura ORI 2012

29/44

29

Reele

Se consider reelele formate din triunghiuri echilaterale de forma prezentat pe desenul demai jos. Reelele sunt formate din vrfuri i muchii. Unele muchii au pe ele un cerc alb sau negru.

Fiecare vrf este descris prin coordonatele sale n sistemul de coordonate, axele cruia trec,respectiv, prin latura de sus i latura din stnga a reelei.

Unul din vrfuri este declarat ca vrf de intrare, iar altul ca vrf de ieire din reea. Pe desenulde mai sus vrful de intrare (0, 2) i cel de ieire (5, 2) sunt marcate cu cte o sgeat.

Deplasarea n cadrul reelei se efectueaz conform urmtoarelor reguli:

1. Deplasarea este permis doar prin muchiile care conin cercuri. 2. Deplasarea printr-o muchie cu cerc alb este permis doar atunci, cnd ultima muchie prin

care s-a trecut are cerc negru i invers. La prima deplasare este permis trecerea att prinmuchii cu cerc alb, ct i prin muchii cu cerc negru.

Prin alte cuvinte, la deplasarea prin reea, cercurile albe i cele negre trebuie s alterneze.

Sarcin. Scriei un program, care determin lungimea celui mai scurt drum de la vrful deintrarepn la vrfulde ieire din reea. Lungimea drumului este definit ca numrul de muchii (saude cercuri) pe care el le conine. n condiiile problemei, existena unui astfel de drum se garanteaz.

Date de intrare. Fiierul text RETEA.IN conine pe prima linie numerele ntregi W i H,separate prin spaiu, care reprezintlimea i nlimea reelei. Linia a doua a fiierului de intrare

conine numerele ntregi , separate prin spaiu. Numerele reprezint coordonatelevrfului de intrare, iar numerele coordonatele vrfului de ieire ale reelei.

Urmtoarele linii ale fiierului de intrare conin descrierea muchiilorreelei: liniileimpare (3, 5, 7 .a.m.d.) descriu muchiile orizontale, iar liniile pare (4, 6, 8 .a.m.d.) descriumuchiile nclinate. Fiecare din aceste linii reprezint un ir format din caracterele -, ai n.Caracterul -(minus) reprezint muchiile fr cerc, iarcaracterele ai nreprezint muchiilecu cerc, respectiv, alb sau negru. ntre caractere nu sunt spaii. Evident, liniile impare conin exactWcaractere, iar liniile pare conin exact caractere.

Date de ieire. Fiierul text RETEA.OUTtrebuie s coninpe o singur linie un numr ntreglungimea drumului minim de la vrful de intrarepn la vrfulde ieire.

7/30/2019 Brosura ORI 2012

30/44

30

Restricii. . Timpul de execuie nu va depi o secund. Programul va folosicel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea RETEA.PAS,RETEA.C sau RETEA.CPP.

Exemplul 1. n acest exemplu se consider urmtoarea reea:

Un drum posibil de lungime minim este:

(0, 0) (1, 0) (0, 1) (1, 1) (1, 0) (2, 0) (2, 1).

Pe desenul de mai sus acest drum este marcat cu sgei arcuite. Fiierele de intrare i ieire sunt:

RETEA.IN RETEA.OUT

2 1

0 0 2 1nn

-aa-a

n-

6

Exemplul 2. n acest exemplu se consider reeaua din desenul de pe pagina precedent.Drumul de lungime minim este:

(0, 2) (1, 2) (1, 1) (2, 1) (2, 0) (3, 0) (3, 1) (3, 2) (4, 1) (3, 1)

(3, 0) (2, 0) (2, 1) (1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4) (3,

3) (4, 3) (4, 2) (5, 2).

Fiierele de intrare i ieire sunt:

RETEA.IN RETEA.OUT

5 4

0 2 5 2

--n--

---aana----

-nnn-

--anaanaa--

naaaa

--nannaan--

-aaa-

----nann---

--a--

22

7/30/2019 Brosura ORI 2012

31/44

31

Rezolvare

Vom reprezenta reeaua iniial printr-un graf, fiecare din vrfurile cruia poate fi de culoarealb sau de culoare neagr. n graful n curs de construcie, fiecrui vrf din reeai corespunddou vrfuri, unul albi altul negru. Cele dou vrfuri ale grafului n curs de construcie, cecorespund vrfului de intrare ale reelei, evident, vor fi vrfurile de intrare ale grafului. ntr-un modsimilar, se definesc i vrfurile de ieire ale grafului.

nprocesul de citire a datelor de intrare, pentru orice cerc alb citit vom crea n graful n cursde construcie o muchie de la vrful negru la vrful alb ntr-o direcie si o muchie de la vrfulnegru la vrful alb in cealalt direcie. ntr-un mod similar vom crea cte dou muchii i ncazul citirii din fiierul de intrare a unui cerc negru.

Evident, n graful astfel construit, oricare dou vrfuri de aceeai culoare niciodat nu vor ficonectate direct. Prin urmare, deplasarea prin acest graf satisface regula alternrii cercurilor.

n continuare, pentru a gsi lungimea celui mai scurt drum, efectum o parcurgere n lime agrafului construit.

Amintim, c parcurgerea grafului n lime se realizeazconform urmtorului algoritm:

1. Iniial, n calitate de vrf curent se viziteaz vrful de start. 2. Se viziteaz n ordine fiecare din vecinii nevizitai ai vrfului de start. 3. Apoi se viziteaz n ordine toi vecinii nevizitai ai vecinilor vrfului de start i aa mai

departe, pn la epuizarea tuturor vrfurilor accesibile din vrful de intrare.

De obicei, n procesul parcurgerii grafului, pentru a memoriza vecinii nevizitai nc aivrfului curent, se folosete o structur dinamic de date, denumit coad.

Evident, n cazul grafului construit de noi, vrful de start va avea n calitate de vecini celedou vrfuri de intrare, unul de culoare alb i altul de culoare neagr. Prin urmare, anumeaceste vrfuri vor fi iniial nscrise n coada ce conine vecinii nevizitai ai vrfului curent.

ntruct n cazul parcurgerii grafului n lime, fiecare vrf este vizitat pe cel mai scurt drum,lungimea drumului de la unul din vrfurile de intrare pn la unul din cele dou vrfuri de ieire vareprezenta soluiaproblemei.

Pentru a memora graful construit n memoria calculatorului, vom utiliza listele de adiacen.n acest scop, pentru fiecare vrf nou creat vom memora doar numerele vrfurilor vecine. ntructorice vrf al reelei poate avea cel mult 6 vrfuri adiacente, memoria necesar pentru stocareagrafului va fi de ordinul . Conform restriciilor problemei, . Prinurmare, necesarul de memorie va fi de ordinul , fapt ce impune folosirea structurilordinamice de date.

ProgramRetea;

{ Clasele 10-12 }const MAXW : longint = 510;

MAXH : longint = 510;

ALB : longint = 0;

NEGRU : longint = 1;

INFINIT : longint = 1000000;

type varf = record

n : longint; { lungimea drumului pana la varf }

nMuchii : longint; { numarul de varfuri vecine (0..6) }

e: array[0..5] of longint; { varfuri vecine }

end;

pVarf = ^varf;

var coada: arrayof longint; { array[0 .. MAXW*MAXH*2 + 10] of longint }

posCoada : longint;i, j : longint;

q, v, k : longint;

graf : array of varf; { array [0 .. MAXH*MAXW*2] of varf }

7/30/2019 Brosura ORI 2012

32/44

32

W, H, Sx, Sy, Fx, Fy : longint;

function altaCuloare(c: longint) : longint;

begin

altaCuloare := c xor 1;

end;

function codVarf(x, y, c : longint) : longint;

begin

codVarf := ((y * MAXW + x) * 2 + c);

end;

procedure adaugaMuchie(v : pVarf; p : longint);

begin

v^.e[v^.nMuchii] := p;

inc(v^.nMuchii);

end;

procedure citire;

var i, j, t, culoare : longint;

x, y, x1, x2, y1, y2 : longint;

buff : AnsiString;

fin : text;

begin

assign (fin, 'RETEA.IN');

reset(fin);

readln(fin, W, H);

readln(fin, Sx,Sy,Fx,Fy);

for j := 0 to 2*H do

begin

y := j div 2;

if jmod2 = 0 then t := W else t := 2*W + 1;

readln(fin, buff);

for i := 0 to t-1 do

if (buff[i+1] '-')thenbegin

if (jmod2 = 0)then

begin { muchii orizontale }

x := i;

x1 := x;

x2 := x + 1;

y2 := y;

y1 := y;

end

else

if (imod2 = 0)then

begin { muchii ne-orizontale }

x := i div 2;x2 := x;

x1 := x;

y1 := y;

y2 := y + 1;

end

else

begin

x := i div 2 + 1;

x1 := x;

x2 := x - 1;

y1 := y;

y2 := y + 1;

end;if buff[i+1] = 'a' then culoare := ALB else culoare := NEGRU;

adaugaMuchie(@graf[codVarf(x1, y1, altaCuloare(culoare))],

codVarf(x2, y2, culoare));

7/30/2019 Brosura ORI 2012

33/44

33

adaugaMuchie(@graf[codVarf(x2, y2, altaCuloare(culoare))],

codVarf(x1, y1, culoare));

end;

end;

close(fin);

end;

procedure scriere;

var fout : text;

begin

assign(fout, 'RETEA.OUT');

rewrite(fout);

if graf[codVarf(Fx, Fy, ALB)].n < graf[codVarf(Fx, Fy, NEGRU)].n

then writeln(fout, graf[codVarf(Fx, Fy, ALB)].n)

else writeln(fout, graf[codVarf(Fx, Fy, NEGRU)].n);

close(fout);

end;

procedure adaugaInCoada(p : longint);

begin

coada[posCoada] := p;

inc(posCoada);

end;

begin

SetLength(coada, MAXW*MAXH*2 + 10);

SetLength(graf, MAXH*MAXW*2);

posCoada := 0;

citire();

for j := 0 to H do

for i := 0 to W do

begin

graf[codVarf(i, j, ALB)].n := INFINIT;

graf[codVarf(i, j, NEGRU)].n := INFINIT;

end;

{ parcurgerea in latime }

adaugaInCoada(codVarf(Sx, Sy, ALB));

adaugaInCoada(codVarf(Sx, Sy, NEGRU));

graf[codVarf(Sx, Sy, ALB)].n := 0;

graf[codVarf(Sx, Sy, NEGRU)].n := 0;

q := 0;

while q < posCoada do

begin { cat nu am ajuns la sfarsitul cozii }

v := coada[q];

for i := 0 to graf[v].nMuchii - 1 do

begin

k := graf[v].e[i];

if (graf[k].n = INFINIT) thenbegin

graf[k].n := graf[v].n + 1;

adaugaInCoada(k);

end;

end;

inc(q);

end;

scriere();

end.

Complexitatea temporal a algoritmului de parcurgere n lime a grafului reprezentat prinliste de adiacen este de ordinul , unde neste numrul de vrfuri ale grafului nou construit,iar m numrul maximal de vecini ai unui vrf. Evident, , iar .

7/30/2019 Brosura ORI 2012

34/44

34

Conform restriciilor problemei, . Prin urmare, timpul cerut de program va fi de ordinul , mrime cu mult mai mic dect capacitatea de prelucrare a calculatoarelor personale.

7/30/2019 Brosura ORI 2012

35/44

35

Convertorul

Fiind mptimit de informatic, Ion a construit un dispozitiv digital, pe care l-a denumitconvertor. Acest dispozitiv accepta la intrare numerele naturale scrise n sistemul de numeraie n

baza bi furnizeaz la ieire numerele respective, scrise n baza 10 (vezi figura de mai jos).

De exemplu, dac la intrarea convertorului este aplicat numrul , iar , la ieireaconvertorului va aprea numrul .

Amintim, c n sistemele de numeraie n baza b, , se utilizeaz urmtoarele cifre: 0, 1,2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

Ion a mprumutat convertorul prietenei sale Lenua, ns a uitat s-i spun care este bazasistemului de numeraie bn care funcioneaz dispozitivul.

Lenua, fiind i ea mptimit de informatic, a decis c poate afla acest lucru i singur, frajutorul lui Ion. n acest scop ea aplic la intrarea convertorului un numr arbitrara, format din cel

puin dou cifre, citete de ieirea convertorului numrul zecimalzi calculeaz baza b.

Sarcin. Scriei un program care calculeaz baza b n care funcioneaz convertorul,cunoscnd numerelede la intrarea i ieirea lui, respectiv, aiz.

Date de intrare. Fiierul text CONVERT.IN conine pe prima linie un ir de caractere cereprezint numrul ascris n baza b. Linia a doua a fiierului de intrare conine numrul zscris n

baza 10.

Date de ieire.Fiierul text CONVERT.OUT va conine pe o singur linie numrul ntreg b.

Restricii. . Numrul a este format din cel puin dou i cel mult 15 caractere.Timpul de execuie nu va depi 0,1 secunde. Programul va folosi cel mult 32 Megaoctei dememorie operativ. Fiierul surs va avea denumirea CONVERT.PAS, CONVERT.C sauCONVERT.CPP.

Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

CONVERT.IN CONVERT.OUT

121

16

3

ba z

7/30/2019 Brosura ORI 2012

36/44

36

Rezolvare

Pentru a gsi baza bn care este scris numrul a vom folosi metoda trierii: 1) atribuim bazei b valoarea maximal posibil 16;2) efectumconversia numrului a din baza bn baza 10;3) dac numrul obinut n rezultatul conversiei este egal cu numrulz, baza cutat a fost gsit;4) n caz contrar, micorm valoarea bazei bcu o unitate i trecem la punctul 2.

Amintim, c valoarea zecimal a unui numrului naturalNformat din 1n cifre,011

... ccccNnn

, se

calculeaz n funcie de baza sistemului de numeraie bdup cum urmeaz:

0

0

1

1

1

1)( bcbcbcbcNn

n

n

nb

.

Prin urmare, pentru a transforma numrul adin fiierul de intrare, parcurgem irul respectiv de caracterede la dreapta la stnga, nmulim fiecare cifr cu semnificaia rangului respectiv i nsumm produseleobinute.

Pentru a transforma cifrele din componena irului de caractere a de la intrarea convertorului n valori

numerice, n programul ce urmeaz este folosit funcia ord, care returneaz numerele de ordine alecaracterului conform tabelului de codificare utilizat de mediul respectiv de programare. Valoarea numeric afiecrei cifre poate fi calculat cunoscnd numerele de ordine ale caracterelor0iA.

ProgramConvert;

{ Clasele 10-12 }

var a : string;

b : integer;

z : QWord;

procedure Citeste;

var Intrare : text;

begin

assign(Intrare, 'CONVERT.IN');

reset(Intrare);

readln(Intrare, a);

readln(Intrare, z);

close(Intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'CONVERT.OUT');

rewrite(Iesire);

writeln(Iesire, b);

close(Iesire);

end; { Citeste }

function IesireaConvertorului : QWord;

{ Returneaza valoarea lui a in sistemul zecimal }

var i : integer; { rangul cifrei }

c : integer; { valoarea cifrei curente }

p : QWord; { semnificatia rangului }

q : QWord; { rezultatul conversiei }

begin

q:=0;

p:=1;

for i:=length(a) downto 1 do

beginif a[i] in ['0'..'9'] then c:= ord(a[i])-ord('0')

else c:= ord(a[i])-ord('A')+10;

q:=q+c*p;

7/30/2019 Brosura ORI 2012

37/44

37

p:=p*b;

end;

IesireaConvertorului:=q;

end; { IesireaConvertorului }

procedure CalculeazaBaza;

{ Caluleaza baza b }

begin

b:=16;

while zIesireaConvertorului do b:=b-1;

end; { CalculeazaBaza }

begin

Citeste;

CalculeazaBaza;

Scrie;

end.

Conform restriciilor problemei, numrul apoate s conin pn la 15 cifre hexazecimale. Prin urmare,variabila zpoate lua valori pn la . Tipurile de date integer i longint nu permit

memorarea i prelucrarea unor numere att de mari. Prin urmare, variabilaz, care reprezint numrul zecimalde la ieirea convertorului, trebuie s fie de tipul QWord, tip care este implementat n mediul de programareFree Pascal. Dac elevul nu cunoate acest mediu de programare, el va fi nevoit s elaboreze subprogramepentru prelucrarea numerelor de ordinul .

Din analiza textului procedurii CalculeazaBaza rezult c aceast procedur conine doarun singur cicluwhile. Evident, instruciunile din componena acestui ciclu vor fi executate de celmult 15 ori, iar instruciunile din cilul foral funciei apelate IesireaConvertorului tot decel mult 15 ori. ntruct este o mrime neglijabil n comparaie cu capacitatea de

prelucrare a calculatoarelor personale din laboratorul de Informatic, timpul de calcul cerut deprocedura CalculeazaBazava fi cu mult mai mic dect 0,1 secunde.

7/30/2019 Brosura ORI 2012

38/44

38

Roboii

Se consider un cmp dreptunghiularde lucru, divizat n ptrele (vezi desenul). Ptrelelelibere sunt de culoare alb, iar cele cu obstacole de culoare nchis. Pe cmpul de lucru, n

ptrele libere, se afl mai muli roboi. Fiecare robot sepoate deplasa din ptrelul curent n ptrelul vecin doarprin latura comun a acestora. Evident, roboii se potdeplasa doar prin ptrelele libere.

Iniial, toi roboii sunt n starea de repaus. Dupsosirea comenzii START, roboii ncep s se deplaseze,viteza de deplasare fiind de un ptrel n fiecare unitatede timp. Fiecare robot se poate opri ori de cte ori elconsider c acest lucru este necesar. Numrul de roboi,care concomitent se pot afla ntr-un ptrel liber, nu estelimitat.

Sarcin. Scriei un program, care calculeaz timpul minim, necesar pentru ca toi roboii seadune n unul din ptrelele libere ale cmpului de lucru.

Date de intrare.n memoria calculatorului cmpul de lucru este reprezentat printr-un tablouformat din numere ntregi, cu nlinii i m coloane. Fiecare din elementele tabloului poate lua una dinurmtoarele valori: 0 ptrel liber; 1 ptrel ce conine un obstacol; 2 ptrel liber n carese afl un robot.

Fiierul text ROBOT.IN conine pe prima linie numerele ntregi n, m separate prin spaiu.Fiecare din urmtoarele n linii ale fiierului de intrare conine cte mnumere ntregi separate prinspaiu, care reprezint ptrelele respective ale cmpului de lucru.

Date de ieire. Fiierul text ROBOT.OUT va conine pe o singur linie un numr ntreg timpul minim, necesar pentru ca toi roboii se adune n unul din ptrelele libere ale cmpului delucru.

Restricii. . Pe cmpul de lucru se pot afla cel mult 10 roboi. Se garanteazctoi roboii se pot aduna nunul din ptrelele libere ale cmpului de lucru.Timpul de execuie nuva depi o secund. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierulsurs va avea denumirea ROBOT.PAS, ROBOT.C sau ROBOT.CPP.

Exemplu. Pentru desenul din enunul problemei, fiierele de intrare i ieire sunt:

ROBOT.IN ROBOT.OUT

7 80 0 0 0 0 0 0 0

2 0 1 1 1 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 1 0

1 1 1 1 0 0 1 0

0 0 2 1 0 0 1 0

0 0 0 0 0 0 1 2

12

Timpul minim se obine n cazul n care toi roboii se adun n ptrelul aflat laintersecia rndului 1 i a coloanei 2. Pe desenul de mai sus acest ptrel este marcat printr-un

punct.

7/30/2019 Brosura ORI 2012

39/44

39

Rezolvare

Pentru a rezolva problema, vom simula deplasarea fiecrui robot cu ajutorul unei undenumerice. Pentru a nu confunda undele numerice ale fiecruia din roboi, vom crea cte un cmp delucru pentru fiecare din ei.

Presupunem c se dorete simularea undei numerice a unuia din roboi. Vom nota prin kvaloarea undei numerice. Evident, n cazul ptrelului n care se afl robotul, . Pentru apropaga unda numeric, nscriem n toate ptrelele libere, care sunt vecine cu ptrelul n care seafl robotul, valoarea . n continuare, parcurgem cmpul de lucru i nscriem ntoate ptrelele libere, vecine cu cele ce conin valoarea curentk, valoarea Repetm acest

proces pentru .a.m.d. pn cnd unda numeric nu mai avanseaz. Pentru exemplificare,pe desenele de mai jos sunt reprezentate rezultatele propagrii undelor numerice pentru fiecare dinroboii din enunul problemei.

Din modul de propagare a undei numerice rezult c valorile nscrise n ptrelele cmpuluide lucru reprezint lungimea celui mai scurt drum, mai exact numrul de ptrele minus doi, pecare trebuie s le parcurg robotul pentru a ajunge din poziia iniial n fiecare din ptrelelerespective.

De exemplu, pentru a ajunge n ptrelul cu coordonatele , adic n ptrelul de laintersecia rndului 1 cu coloana 1, primul robot trebuie s parcurg ptrel, robotul aldoilea trebuie s parcurg ptrele, iar robotul al treilea ptrele. Prinurmare, dac toi cei trei roboi s-ar aduna n ptrelul cu coordonatele , timpul necesar ar fiegal cu 13. ntr-un mod similar, ne convingem, c dac roboii s-ar aduna n ptrelul , timpulnecesar ar fi egal cu 18; n ptrelul cu 25 .a.m.d.

Evident, timpul cerut n enunul problemei poate fi gsit prin parcurgerea cmpurilor n caresunt nscrise valorile undelor numerice ale fiecruia din roboi, selectarea pentru fiecare din

ptrelele omonime a valorilor maximale i alegerea din valorile astfel calculate a valorii minimale.n cazul exemplului de mai sus, valoarea minimal este obinut n cazul ptrelului ,

pentru care valorile undelor numerice sunt 4, 14 i 14, timpul respectiv fiind egal cu 12.

n programul ce urmeaz, pentru a evita verificrile de la margini, cmpul de lucru al fiecruirobot este ncadrat ntr-un chenar format din obstacole.

ProgramRobotii;

{ Clasele 10-12 }

const nmax=40; mmax=40; rmax=10;

type CampDeLucru = array[0..nmax+1, 0..mmax+1] of integer;

var C : array[1..rmax] of CampDeLucru;n, m, r : integer;

t : longint;

7/30/2019 Brosura ORI 2012

40/44

40

procedure Citeste;

var i, j : integer;

Intrare : text;

begin

assign(Intrare, 'ROBOT.IN');

reset(Intrare);

readln(Intrare, n, m);

for i:=1 to n do

begin

for j:=1 to m-1 do read(Intrare, C[1][i, j]);

readln(Intrare, C[1][i, m]);

end;

close(Intrare);

{ incadram campul intr-un chenar din obstacole }

for j:=0 to m+1 do C[1][0, j]:=1;

for j:=0 to m+1 do C[1][n+1, j]:=1;

for i:=0 to n+1 do C[1][i, 0]:=1;

for i:=0 to n+1 do C[1][i, m+1]:=1;

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'ROBOT.OUT');

rewrite(Iesire);

writeln(Iesire, t);

close(Iesire);

end; { Scrie }

procedure NumaraRobotii;

{ Inscrie in r numarul de roboti }

var i, j : integer;

begin

r:=0;

for i:=1 to n dofor j:=1 to m do

if C[1][i, j]=2 then r:=r+1;

end; { NumaraRobotii }

procedure InitializeazaCampurile;

var i, j, p, q : integer;

begin

{ cream r exemplare ale campului de lucru }

for p:=2 to r do C[p]:=C[1];

{ lasam pe fiecare camp cate un singur robot }

for p:=1 to r do

begin

q:=0;for i:=1 to n do

for j:=1 to m do

if (C[p][i, j]=2) then

begin

q:=q+1;

if (pq) then C[p][i, j]:=0;

end;

end;

end; { InitializeazaCampurile }

procedure PropagaUndaNumerica(var A : CampDeLucru);

{ Propaga unda numerica in campul A }

var i, j : integer;k : integer; { valoarea curenta a undei numerice }

Ind : boolean; { indicator }

begin

7/30/2019 Brosura ORI 2012

41/44

41

k:=1;

repeat

k:=k+1;

Ind:=true;

for i:=1 to n do

for j:=1 to m do

if A[i, j]=k then

begin

if A[i-1, j]=0 then

begin A[i-1, j]:=k+1; Ind:=false; end;

if A[i+1, j]=0 then

begin A[i+1, j]:=k+1; Ind:=false; end;

if A[i, j-1]=0 then

begin A[i, j-1]:=k+1; Ind:=false; end;

if A[i, j+1]=0 then

begin A[i, j+1]:=k+1; Ind:=false; end;

end;

until Ind;

end; { PropagaUndaNumerica }

procedure CalculeazaTimpulMinim;

{ Calculeaza timpul minim }

var i, j, p, k : integer;

Ind : boolean; { indicator }

begin

for p:=1 to r do

PropagaUndaNumerica(C[p]);

t:=MaxInt;

for i:=1 to n do

for j:=1 to m do

if C[1][i, j]>1 then

begin

k:=2;

for p:=1 to r do

if C[p][i, j]>k then k:=C[p][i, j];if k

7/30/2019 Brosura ORI 2012

42/44

42

Turitii

Un grup de elevi a decis s fac o excursie de-a lungul rului Prut. Rul Prut are mai muliaflueni, care se vars n el att din partea stng, ct i din partea dreapt. Pe desenul alturat, rul

Prut este simbolizat printr-o dreapt vertical, iar afluenii lui

prin drepte orizontale mai subiri.Elevii intenioneaz s nceap excursia de la nord, din

punctulAde pe malul stng, i s o termine la sud, n punctulB de pe malul drept.

Elevii au studiat foarte atent harta i au ajuns laconcluzia c exist mai multe variante de a ajunge din

punctulA n punctulB, ns, indiferent de varianta aleas, eivor trebui s traverseze att rul, ct i unii aflueni aiacestuia. Pentru elevi, traversarea rului i a afluenilorreprezint o sarcin dificil i, evident, ei ar dori s aleag o

cale, pentru care numrul de traversri s fie ct mai mic. Pentru exemplificare, pe desenul alturat, o astfel de

cale este simbolizat printr-o linie ntrerupt.

Sarcin. Scriei un program, care calculeaz numrulminim de traversri, pe care elevii vor fi nevoii s le fac

pentru a ajunge din punctulAn punctulB.

Date de intrare.Fiierul text TURIST.INconine peo singur linie un ir de caractere, format din literele L,R,B.Acest ir descrie poriunea de ru, cuprins ntre punctele AiB. LiteraL semnific faptul c afluentul curent se vars n ru

din stnga, literaRfaptul c afluentul curentse vars n rudin dreapta, iar literaBfaptul c n ru, n acelai punct, sevars doi aflueni, cte unul din fiecare parte. Literele L,RiBapar nir conform direciei preconizate a excursiei: de-alungul rului, de la nord la sud.

Date de ieire.Fiierul text TURIST.OUTva conine pe o singur linie un numr ntreg numrul minim de traversri.

Restricii.irul de caractere din fiierul de intrare va conine cel mult litere. Timpul deexecuie nu va depi o secund. Programul va folosi cel mult 32 Megaoctei de memorie operativ.

Fiierul surs va avea denumirea TURIST.PAS, TURIST.C sau TURIST.CPP.Exemplu. Pentru exemplul din enunul problemei, fiierele de intrare i ieire sunt:

TURIST.IN TURIST.OUT

LLBLRRBRL 5

7/30/2019 Brosura ORI 2012

43/44

43

Rezolvare

Problema poate fi rezolvat prin metoda programrii dinamice. n acest scop, vom nota prin irul de caractere din fiierul de intrare. Prin fiecare dreapt, ce simbolizeaz

un afluent, vom trasa cte o linie orizontal, care trece i departea cealalt a rului.

Zonele formate de dreptele orizontale trasate de noi le

vom numerota prin 0, 1, 2, 3 .a.m.d., de sus n jos, ncepndcu zona n care se afl punctulA. Evident, punctulB se va aflan zona n, pe malul drept al rului.

Introducem n studiu urmtoarele notaii:

numrul minim de traversri pe care trebuie s lefac elevii pentru a ajunge din punctul A ntr-un punct de pemalul drept al zonei ;

numrul minim de traversri pe care trebuie s le

fac elevii pentru a ajunge din punctul A ntr-un punct de pemalul stng al zonei .

Evident, i .Presupunem c sunt deja cunoscute valorile minime

i se dorete calcularea valorilor minime .

Din zona elevii pot ajunge ntr-un punct de pemalul drept al zonei prin una din urmtoarele dou ci:

3)Fr ca s traverseze rul. n acest caz, numrul detraversri va fi dac pe malul drept, ntre zonele i , exist un afluent i

n caz contrar.4)Traversnd rul. n acest caz, numrul de traversri va fi ) dac pe malul

stng, ntre zonele i , exist un afluent i n caz contrar.Prin urmare, numrul minim de traversri poate fi calculat cu ajutorul urmtoarei formule

recurente:

,

unde:

este o variabil care ia valoarea 1, dac pe malul drept, ntre zonele i , exist unafluent i 0 n caz contrar. Evident, un astfel de afluent exist doar atunci, cnd caracterul din

fiierul de intrare are valoareaR sauB;este o variabil care ia valoarea 1, dac pe malul stng, ntre zonele i , exist un

afluent i 0 n caz contrar. Evident, un astfel de afluent exist doar atunci, cnd caracterul dinfiierul de intrare are valoareaL sauB.

ntr-un mod similar se deduce i formula recurent pentru calcularea numrului minim detraversri :

Evident, valoarea reprezint numrul minim de traversri pe care trebuie s le fac elevi ipentru a ajunge din punctulAn punctulB.

ProgramTuristii;

{ Clasele 10-12 }

const nmax=100000;

7/30/2019 Brosura ORI 2012

44/44

var S : array[1..nmax] of char;

n : longint;

p0, q0, p1, q1 : longint;

procedure Citeste;

var Intrare : text;

i : longint;

begin

assign(Intrare, 'TURIST.IN');

reset(Intrare);

i:=1;

repeat

read(Intrare, S[i]);

i:=i+1;

until eoln(Intrare);

n:=i-1;

close(intrare);

end; { Citeste }

procedure Scrie;

var Iesire : text;

begin

assign(Iesire, 'TURIST.OUT');

rewrite(Iesire);

writeln(Iesire, p1);

close(Iesire);

end; { Scrie }

procedure Calculeaza;

var g, h : integer;

i : longint;

begin

p0:=1; q0:=0;

for i:=1 to n do

beginif (S[i]='R') or (S[i]='B') then g:=1 else g:=0;

if (S[i]='L') or (S[i]='B') then h:=1 else h:=0;

if (p0+g) < (q0+h+1) then p1:=(p0+g) else p1:=(q0+h+1);

if (q0+h) < (p0+g+1) then q1:=(q0+h) else q1:=(p0+g+1);

p0:=p1; q0:=q1;

end;

end; { Cacluleaza }

begin

Citeste;

Calculeaza;

Scrie;

end.

Din analiza textului procedurii Calculeazase observ c instruciunile ifdin componenaciclului for vor fi executate de nori. Conform restriciilor problemei, . Evident, valoarealui neste cu mult mai mic dect capacitatea de prelucrare a calculatoarelor personale. Prin urmare,timpul cerut de program va fi cu mult mai mic dect o secund.