Post on 14-Apr-2018
7/30/2019 Brosura ORI 2013
1/53
MINISTERUL EDUCAIEIAL REPUBLICII MOLDOVA
MHCTEPCTBO IIPOCBEEHPECJIK MO
Olimpiada Republican la InformaticEdiia 2013
Chiinu 2013
7/30/2019 Brosura ORI 2013
2/53
2
Olimpiada Republican la Informatic. Ediia 2013.
Lucrarea conine problemele propuse la Olimpiada Republican la Informatic a elevilor, ediia2013. 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 StudiiEconomice a Moldovei.
Iurie Mocanu ef de direcie, Ministerul Educaiei.
Angela Priscaru consultant, Ministerul Educaiei.
Dumitru Ciubati informatician.
Constantin Dolghieru informatician.
7/30/2019 Brosura ORI 2013
3/53
3
Cuprins
CLASELE 7 9 ...................................................................................................... 4
CEASUL ........................................................................................................... 5
IMAGINI ........................................................................................................... 8
BLOCURI DE PIATR....................................................................................... 11
FORMULE....................................................................................................... 15
FERESTRE ...................................................................................................... 17
PARCARE AUTO.............................................................................................. 21
PUNCTAJUL TOTAL ACUMULAT DE FIECARE COMPETITOR.............................. 26
CLASELE 10 12 ................................................................................................ 27
CEASUL ......................................................................................................... 28
IMAGINI ......................................................................................................... 31
BLOCURI DE PIATR....................................................................................... 34
FORMULE....................................................................................................... 40
FERESTRE ...................................................................................................... 43
PARCARE AUTO.............................................................................................. 47
PUNCTAJUL TOTAL ACUMULAT DE FIECARE COMPETITOR.............................. 53
7/30/2019 Brosura ORI 2013
4/53
4
Clasele 7 9
Denumirea
problemei
Numrul depuncte alocat
problemei
Denumirea
fiierului surs
Denumirea
fiierului deintrare
Denumirea
fiierului de
ieire
Ceasul 100CEAS.PAS
CEAS.C
CEAS.CPP
CEAS.IN CEAS.OUT
Imagini 100IMAGINI.PAS
IMAGINI.C
IMAGINI.CPP
IMAGINI.IN IMAGINI.OUT
Blocuri depiatr
100BLOCURI.PAS
BLOCURI.C
BLOCURI.CPP
BLOCURI.IN BLOCURI.OUT
Formule 100FORMULE.PAS
FORMULE.C
FORMULE.CPP
FORMULE.IN FORMULE.OUT
Ferestre 100FERESTRE.PAS
FERESTRE.C
FERESTRE.CPP
FERESTRE.IN FERESTRE.OUT
Parcare auto 100PARCARE.PAS
PARCARE.C
PARCARE.CPP
PARCARE.IN PARCARE.OUT
Total 600 - - -
7/30/2019 Brosura ORI 2013
5/53
5
Ceasul
Ana a primit un cadou special un ceas digital, care indic timpul curent n formatul HH:MM,unde HHreprezint ora, iarMM minutele. Specificul acestui ceas const n faptul c n momentul ncare timpul indicat de el reprezint unpalindrom, ceasul reproduce o melodie din renumitul film In
Time.Ana iubete att de mult aceast melodie, nct de fiecare dat cum se uit la ce as, imediat
dorete s tie, cnd din nou va fi redat melodia respectiv.
Amintim, c un ir de caractere este un palindrom, dac el se citete n acelai fel att de lastnga la dreapta, ct i de la dreapta la stnga. De exemplu, irul de caractere 12:21 este un
palindrom.
Sarcin.Elaborai un program, care, cunoscnd timpul curent n formatul HH:MM, determincel mai apropiat momentul de timp n care din nou va fi redat melodia din filmul In Time.
Date de intrare: Fiierul text CEAS.IN conine pe o singur linie un ir de caracteretimpul curent scris n formatul HH:MM.
Date de ieire: Fiierul text CEAS.OUTva conine pe o singur linie un ir de caractere celmai apropiat moment de timp n care din nou va fi redat melodia din renumitul film In Time .Momentul de timp va fi scris n formatul HH:MM.
Restricii: 00 HH < 24; 00 MM < 60. Timpul de execuie nu va depi 0,1 secunde.Programul va folosi cel mult 32 Megaoctei de memorie operativ.Fiierul surs va avea denumireaCEAS.PAS, CEAS.C sau CEAS.CPP.
Exemplu 1.
CEAS.IN CEAS.OUT14:53 15:51
Exemplu 2.
CEAS.IN CEAS.OUT
23:45 00:00
Rezolvare
Din enunul problemei, rezult c melodia va fi redat n momentele de timp: 00:00,01:10, 02:20, 03:30, 04:40, 05:50, 10:01, 11:11, 12:21, ..., 22:22, 23:32, n total,16 valori. Prin urmare, este suficient s comparm timpul curent, citit din fiierul de intrare, cuvalorile de mai sus i s o alegem pe cea potrivit.
ProgramCeasul;
{ Clasele 07-09 }
var HH, MM : array [1..16] of string; { palindromurile: ore, minute }
TCH, TCM : string; { timpul curent din fisierul de intrare }TRMH, TRMM : string; { timpul de redare a melodiei }
procedure Initializare;
7/30/2019 Brosura ORI 2013
6/53
6
var i : integer;
begin
HH[1] :='00'; MM[1] :='00';
HH[2] :='01'; MM[2] :='10';
HH[3] :='02'; MM[3] :='20';
HH[4] :='03'; MM[4] :='30';
HH[5] :='04'; MM[5] :='40';
HH[6] :='05'; MM[6] :='50';
HH[7] :='10'; MM[7] :='01';
HH[8] :='11'; MM[8] :='11';
HH[9] :='12'; MM[9] :='21';
HH[10]:='13'; MM[10]:='31';
HH[11]:='14'; MM[11]:='41';
HH[12]:='15'; MM[12]:='51';
HH[13]:='20'; MM[13]:='02';
HH[14]:='21'; MM[14]:='12';
HH[15]:='22'; MM[15]:='22';
HH[16]:='23'; MM[16]:='32';
end; { Initializare }
procedure Citeste;
var Intrare : text;
S : string;
begin
assign(Intrare, 'CEASUL.IN');
reset(Intrare);
readln(Intrare, S);
close(Intrare);
TCH:=S[1]; TCH:=TCH+S[2];
TCM:=S[4]; TCM:=TCM+S[5];
end; { Citeste }
procedure Calculeaza;{ Calculeaza momentul redarii melodii }
var i : integer;
begin
i:=0;
repeat
i:=i+1;
until TCH=MM[i]) then i:=i+1;
if i>16 then i:=1;
TRMH:=HH[i]; TRMM:=MM[i];
end; { Calculeaza }
procedure Scrie;var Iesire : text;
begin
assign(Iesire, 'CEASUL.OUT');
rewrite(Iesire);
writeln(Iesire, TRMH+':'+TRMM);
close(Iesire);
end; { Scrie }
begin
Initializare;
Citeste;
Calculeaza;
Scrie;end.
7/30/2019 Brosura ORI 2013
7/53
7
ntruct instruciunile din unicul ciclu repeat se vor executa cel mult de 16 ori, timpul deexecuie al programului va fi cu mult mai mic dect o secund.
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Ceasul, 07-09
7/30/2019 Brosura ORI 2013
8/53
8
Imagini
Imaginile color (vezi desenul) pot fi codificate cu ajutorul unui tablou bidimensional cu n linii
i m coloanemnij
bB . Elementul bij indic printr-un numr natural culoarea microzonei
respective, folosind n acest scop un sistem prestabilit de codificare a culorilor, de exemplu: alb (bij= 0), neagr (bij = 1), roie (bij = 2) etc. Pentru a colora imaginile editoarele grafice ofer un
instrument special denumit Umple-cu-culoare, aplicarea cruia imit procesul de scurgere avopselei din borcan n microzona curent, din ea n microzonele adiacente de aceeai culoare.a.m.d. Evident, vopseaua poate curge dintr-o microzon n alta numai atunci cnd ele au o laturcomun.
Sarcin.Elaborai un program pentru realizarea instrumentului Umple-cu-culoare.
Aplicarea instrumentului Umple-cu-culoare:a - imaginea iniial; b - imaginea final; c - codificarea culorilor
Date de intrare. Fiierul text IMAGINI.INconine pe prima linie numerele naturale n, m
separate prin spaiu. Fiecare din urmtoarele nlinii conine cte mnumere separate prin spaiu. Liniai +1 a fiierului de intrare conine numerele bi1, bi2, ..., bim ale imaginii iniiale. Ultima linie afiierului conine trei numere naturalep, q, kseparate prin spaiu. Numerelep, qindic coordonatelezonei asupra creia trebuie aplicat instrumentul Umple-cu-culoare, iar numrul k indic codulculorii din borcan.
Date de ieire. Fiierul text IMAGINI.OUT va conine pe fiecare din cele n linii cte mnumere separate prin spaiu. Linia i a fiierului de ieire conine numerele bi1, bi2, ..., bim aleimaginii finale.
Restricii. 1 n, m 20, 0 bij, k 10, bij k. Timpul de execuie nu va depi 0,1 secunde.Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumireaIMAGINI.PAS, IMAGINI.C sau IMAGINI.CPP.
Exemplu. Pentru desenul de mai sus avem:
IMAGINI.IN IMAGINI.OUT
7 7
1 0 0 0 1 0 1
0 1 1 1 1 0 0
0 0 1 0 1 1 0
0 1 0 0 1 0 0
0 1 0 0 0 1 1
1 1 1 1 0 0 0
0 1 0 0 0 1 1
2 3 2
1 0 0 0 2 0 1
0 2 2 2 2 0 0
0 0 2 0 2 2 0
0 1 0 0 2 0 0
0 1 0 0 0 1 1
1 1 1 1 0 0 0
0 1 0 0 0 1 1
7/30/2019 Brosura ORI 2013
9/53
9
Rezolvare
Vom nota prin s culoarea microzonei asupra creia trebuie aplicat instrumentul Umple-cu-culoare. Evident,s = bpq. Pentru a imita procesul de scurgere a vopselei din borcan n microzona (p,q), iar din ea n microzonele adiacente de aceeai culoare .a.m.d., vom elabora o procedurrecursiv, denumit Vopsea, care efectueaz urmtoarele operaii:
dac culoarea microzonei curente nu coincide cu s, atunci n procedura Vopsea nu seefectueaz nici o operaie;dac culoarea microzonei curente coincide cu s, atunci microzona n studiu este vopsit n
culoarea k, iar procedura Vopseaeste apelat recursiv pentru cele patru microzonele adiacente: ceade sus (p-1, q), cea din dreapta (p, q+1), cea de jos (p+1, q) i cea din stnga (p, q-1).
ntruct k bpq, laexecuia apelurilor recursive Vopsea(p,q)microzona deja colorat numai este examinat a doua oar, fapt ce exclude ciclarea programului. De asemenea, pentru a evitaverificrile necesare n cazul microzonelor de la margini, vom ncadra imaginea ntru-un chenar,nscriind n celulele respective ale tablouluiBvaloarea -1.
ProgramImagini;
{ Clasele 07-09 }
const nmax=21;
mmax=21;
var n, m, p, q, k, i, j : integer;
B : array[0..nmax, 0..mmax] of -1..255;
Finput, Foutput : text;
procedure UmpleCuCuloare(p, q, k : integer);
var i, j, s : integer;
{ s - culoarea initiala a microzonei (i, j) }
procedure Vopsea(p, q : integer);
{ Simulam scurgerea vopselei }
beginif B[p, q]=s then
begin
{ vopsim microzona (p, q) }
B[p, q]:=k;
{ vopsim microzona de sus }
Vopsea(p-1, q);
{ vopsim microzona din dreapta }
Vopsea(p, q+1);
{ vopsim microzona de jos }
Vopsea(p+1, q);
{ vopsim microzona din stinga }
Vopsea(p, q-1);
end; { then }end; { Vopsea }
begin
{ memoram in s culoarea microzonei (p, q) }
s:=B[p, q];
{ bordam tabloul B cu -1 }
for i:=0 to n+1 do
begin B[i, 0]:=-1; B[i, m+1]:=-1; end;
for j:=0 to m+1 do
begin B[0, j]:=-1; B[n+1, j]:=-1; end;
Vopsea(p, q);
end; { UmpleCuCuloare }
begin
assign(Finput, 'IMAGINI.IN');
assign(Foutput, 'IMAGINI.OUT');
7/30/2019 Brosura ORI 2013
10/53
10
reset(Finput);
rewrite(Foutput);
readln(Finput, n, m);
for i:=1 to n do
begin
for j:=1 to m do read(Finput, B[i, j]);
readln(Finput);
end;
readln(Finput, p, q, k);
close(Finput);
UmpleCuCuloare(p, q, k);
for i:=1 to n do
begin
for j:=1 to m do write(Foutput, B[i, j], ' ');
writeln(Foutput);
end;
close(Foutput);
end.
Evident, numrul de apeluri recursive ale procedurii Vopsea nu poate depi numrul de
microzone ale imaginii. Prin urmare, timpul de execuie T n m, iar spaiul necesar de memorie nstiv Vs n m. Conform restriciilor problemei, dimensiunile imaginii n, m 20, deci timpul deexecuie T
7/30/2019 Brosura ORI 2013
11/53
11
Blocuri de piatr
InfoCityeste un ora modern i foarte frumos. Oraul este n permanent extindere i a ajunsdeja la marginea rului InfoRiver. Primarul oraului dorete s extind InfoCitype cellalt mal alrului, intenionnd s construiasc n acest scop un pod. Pentru a se integra organic n arhitectura
oraului, podul va avea exact doi piloni, ce vor fi construii din blocuri de piatr.Pentru construciaunui pilon sunt necesarepblocuri de piatr.
Primria oraului dispune de n seturi de blocuri de piatr, numerotate prin 1, 2, 3, ..., i, ..., n.Setul iconine ai blocuri de piatr.
Evident, exist mai multe variante distribuire a seturilor de blocuri de piatr ntre cei doipiloni n curs de construcie.
Sarcin. Elaborai un program, care calculeaz numrul de variante posibile de distribuire aseturilor respective ntre cei doi piloni ai podului n aa mod, nct fiecrui a din piloni s-i revincel puinp blocuri de piatr.
Date de intrare: Fiierul text BLOCURI.INconine dou linii. Prima linie a fiierului deintrare conine numerele ntregi n i p, separate prin spaiu. Linia a doua a fiierului de intrareconine numerele ntregi a1, a2, ..., ai, ..., an, separate prin spaiu, unde ai reprezint numrul de
blocuri de piatr din setuli.
Date de ieire: Fiierul text BLOCURI.OUTva conine pe o singur linie un numr ntregnumrul de variante posibile de distribuire a seturilor de blocuri de piatr.
Restricii: 1 n 14; 1 p 10000; 1 ai 109. Timpul de execuie nu va depi 1
secund. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va aveadenumirea BLOCURI.PAS, BLOCURI.C sau BLOCURI.CPP.
Exemplu 1.BLOCURI.IN BLOCURI.OUT
4 6 6
3 1 4 6
Explicaie. Seturile de blocuri i = 1, 2, 3, 4, pot fi distribuite dup cum urmeaz:
Varianta Pilonul 1 Pilonul 2
1 1, 2, 3 4
2 1, 3 2, 4
3 2, 4 1, 3
4 4 1, 2, 35 1, 3 4
6 4 1, 3
Exemplu 2.
BLOCURI.IN BLOCURI.OUT
3 7 0
5 3 6
Explicaie. ntruct avem doar trei seturi, pentru oricare din variantele de distribuire, unuia din
piloni i va reveni doar un singur set. ntruct nici unul din seturi nu conine cel puin 7 blocuri depiatr, nu exist nici o variant de distribuire a seturilor de blocuri, ce ar corespunde enunuluiproblemei.
7/30/2019 Brosura ORI 2013
12/53
12
Rezolvare
Vom genera toate variante posibile de distribuire a seturilor de blocuri de piatr ntre cei doipiloni. Din variantele generate le vom contabiliza doar pe acelea n care fiecruia din cei doi pilonii revin cte cel puinp blocuri de piatr.
Pentru a genera toate variante posibile de distribuire a seturilor de blocuri ntre cei doi piloni
ai podului vom utiliza tabloul V[1..n], fiecare din componentele cruia poate lua valorile 0, 1, 2.Valoarea 0 a componentei V[i] indic faptul, c blocul i nu a fost alocat nici unuia din piloni,valoarea 1 c blocul i a fost alocat pilonului 1, iar valoarea 2 c blocul i a fost alocat pilonului 2.
Componentele tabloului Vpot fi tratate ca cifre ale unui numr natural, scris n sistemul ternarde numeraie. Evident, fiecrei valori distincte a acestui numr ternar i corespunde o variant dedistribuire a seturilor de blocuri ntre cei doi piloni.
Pentru a genera toate variantele posibile, iniial i atribuim lui Vvaloarea 0. Presupunem c Vare deja o anumit valoare ternar. n continuare, mrim numrul Vcu o unitate ternar .a.m.d.,
pn cnd ajungem la valoarea 3n1.
ProgramBlocuri;
{ Clasele 07-09 }
const nmax=15; { numarul maximal de seturi }
var V : array[1..nmax] of integer;
A : array[1..nmax] of longint;
n : integer;
p : integer;
K : longint; { numarul de variante posibile }
D : integer; { indicatorul de depasire la incrementarea lui V }
procedure Citeste;
var Intrare : text;
i : integer;begin
assign(Intrare, 'BLOCURI.IN');
reset(Intrare);
readln(Intrare, n, p);
for i:=1 to n do
read(Intrare, A[i]);
close(intrare);
end; { Citeste }
procedure Scrie;
var Iesire : text;
begin
assign(iesire, 'BLOCURI.OUT');rewrite(Iesire);
writeln(Iesire, K);
close(Iesire);
end; { Scrie }
procedure Initializare;
{ Initializeaza V in zero }
var i : integer;
begin
for i:=1 to n do V[i]:=0;
end; { initializare }
procedure Incrementare;{ Mareste V cu o unitate in sistemul ternar }
var i : integer;
begin
7/30/2019 Brosura ORI 2013
13/53
13
D:=1;
for i:= 1 to n do
begin
V[i]:=V[i]+D;
D:=0;
if V[i]=3 thenbegin V[i]:=0; D:=1; end;
end;
end; { Incrementare }
procedure Contabilizeaza;
var i : integer;
p1, p2 : longint; {numarul de pietre per pilon }
begin
p1:=0; p2:=0;
for i:=1 to n do
begin
if V[i]=1 then p1:=p1+A[i];
if V[i]=2 then p2:=p2+A[i];
end;
if (p1>=p) and(p2>=p) then K:=K+1;
end; { Contabilizeaza }
procedure Calculeaza;
var i : integer;
begin
Initializare;
K:=0;
repeat
Contabilizeaza;
Incrementare;
until D=1;
end; { Calculeaza }
begin
Citeste;Calculeaza;
Scrie;
end.
Timpul cerut de procedura Calculeaza este proprional cu numrul de apeluri aleprocedurilorContabilizeaza i Incrementare din ciclul repeat. Evident, acest numreste egal cu 3n. Fiecare din procedurile Contabilizeazai Incrementareconine cte unciclu, care se va executa de cel mult nori. Prin urmare, timpul cerut de program va fi proporionalcu 3nn.
Conform restriciilor problemei, n 14. Evident, pentru n = 14, timpul cerut de program va fiproporional cu 314 14 6,7 107. ntruct aceast valoare mai mic dect capacitatea deprelucrarea calculatoarelor personale, timpul de execuie nu va depi o secund.
7/30/2019 Brosura ORI 2013
14/53
14
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Blocuri, 07-09
7/30/2019 Brosura ORI 2013
15/53
15
Formule
Se consider urmtoarele formule metalingvistice:
Cifr :: = 0 1 2 3 4 5 6 7 8 9
Numr :: = Cifr Cifr Semn ::= + - * /
Expresie :: = Numr Expresie Semn Expresie
Sarcin. Scriei un program care returneaz valoarea DA dac irul de caractere S esteconform definiiei unitii lexicale Expresie i NU n caz contrar.
Date de intrare. Fiierul text FORMULE.IN conine pe fiecare linie cte un ir decaractere S.
Date de ieire. Fiierul text FORMULE.OUTva conine pe fiecare din linii valoarea DAdac
irul de caractere din linia respectiv a fiierului de intrare corespunde definiiei i NU n cazcontrar.
Restricii. irul nevid Sconine cel mult 250 de caractere. Fiierul de intrare conine cel mult200 de linii. Timpul de execuie nu va depi 0,2 secunde. Programul va folosi cel mult 32Megaoctei de memorie operativ.Fiierul surs va avea denumirea FORMULE.PAS, FORMULE.Csau FORMULE.CPP.
Exemplu.
FORMULE.IN FORMULE.OUT
1+3014-4+629/1235-3*2
+1+34694509/293+1
DA
NUDA
Rezolvare
Din analiza formulelor metalingvistice se observ c irul nevid S este conform definiieiunitii lexicale Expresie atunci i numai atunci cnd se respect urmtoarele condiii:
1) n ir apar numai caracterele 0,1, ..., 9, +, -, *, /;2) primul i ultimul caracter ale irului sunt cifre;3) dup fiecare din caracterele +, -, *, / urmeaz cel puin o cifr.n programul ce urmeaz verificarea condiiilor respective se efectueaz cu ajutorul funciei
Corespunde prin cel mult trei parcurgeri ale irului S. Evident, timpul de execuie T(n) ~ 3n,unde neste lungimea irului S. Pentru n 250 timpul de execuie T(n)
7/30/2019 Brosura ORI 2013
16/53
16
Corespunde:='DA';
n:=length(S);
for i:=1 to n do
ifnot (S[i] in ['0'..'9', '+', '-', '*', '/']) then
begin Corespunde:='NU'; goto 1; end;
ifnot ((S[1] in ['0'..'9'] ) and(S[n] in ['0'..'9'])) then
begin Corespunde:='NU'; goto 1; end;
for i:=1 to n-1 do
if (S[i] in ['+', '-', '*', '/']) andnot (S[i+1] in ['0'..'9']) then
begin Corespunde:='NU'; goto 1; end;
1: end; { Corespunde }
begin
assign(Finput, 'FORMULE.IN');
reset(Finput);
assign(Foutput, 'FORMULE.OUT');
rewrite(Foutput);
whilenot eof(Finput) do
begin
readln(Finput, S);
writeln(Foutput, Corespunde(S));
end;
close(Finput);
close(Foutput);
end.
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Formule, 07-09
7/30/2019 Brosura ORI 2013
17/53
17
Ferestre
Trecerea la interfeele grafice a simplificat cu mult interaciunea om-calculator. Amintim, cn cazul interfeelor grafice ecranul monitorului simbolizeaz o mas de lucru, pe care apar ferestre.Concomitent, trecerea la interfeele grafice a pus nceputul unui ir interminabil de glume, una din
ele referindu-se la faptul c, n sfrit, calculatoarele ne oferposibilitatea s avem pe mas virtualde lucru aceiai dezordine,pe care o avem i pe mas propriu-zis.
Vasile folosete un sistem de operare, care deschide pe ecran numeroase ferestre. n acestsistem de operare ecranul monitorului este mprit n ptrate elementare cu dimensiunile 11, careformeaz un rastru. Liniile rastrului sunt numerotate de la 1 de sus n jos, iar coloanele suntnumerotate de la 1 de la stnga la dreapta. Astfel, fiecare ptrat elementar de pe ecran poate fiidentificat specificnd numrul liniei i numrul coloanei pe care se afl.
Fiecare fereastr este un dreptunghi format din unul sau mai multe ptrate elementare. Ofereastr nou deschis poate s se suprapun parial sau total peste alte ferestre, deschise n
prealabil. Evident, ptrelele ferestrelor deschise anterior, ce au fost acoperite de fereastra numai ce
deschis, devin invizibile.Putem nchide o fereastr dac executm un clic n ptratul elementar ce constituie colul din
dreapta sus al ferestrei, cu condiia c acesta este vizibil.
Sarcin. Scriei un program care s determine numrul minim de click-uri necesare pentru anchide fereastr pe care am deschis-o prima.
Date de intrare. Fiierul text FERESTRE.IN conine pe prima linie un numr natural n,reprezentnd numrul de ferestre deschise pe ecran.Fiecare dintre urmtoarele n linii ale fiieruluide intrare conine ctepatru numere naturale ls, cs, ld, cd,separate prin spaiu, cu semnificaia "amdeschis o fereastr care are colul din stnga sus pe linia lsi coloana cs, respectiv colul din dreapta
jos pe linia ldi coloana cd". Ferestrele au fost deschise n ordinea n care apar n fiierul de intrare.Date de ieire. Fiierul text FERESTRE.OUTva conine o singur linie pe care va fi scris
numrul minim de click-uri, necesare pentru a nchide prima fereastr deschis.
Restricii. 1000 n ; 000101 ldls ; 000101 cdcs . Timpul de execuie nu vadepi 0,2 secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierulsurs va avea denumirea FERESTRE.PAS, FERESTRE.C sau FERESTRE.CPP.
Exemplul 1. Exemplul 2.
FERESTRE.IN FERESTRE.OUT FERESTRE.IN FERESTRE.OUT
3 3 3 33 1 6 4 4 1 6 3
1 2 4 6 2 2 5 5
2 3 5 5 1 4 3 6
Exemplul 3.
FERESTRE.IN FERESTRE.OUT
3 1
3 3 4 4
1 1 2 2
5 5 6 6
7/30/2019 Brosura ORI 2013
18/53
18
Rezolvare
Vom calcula numrul minim de click-uri necesare pentru a nchide prima fereastr pe care amdeschis-o prin metoda recursiei. Vom elabora n acest scop procedura InchideFereastra(j),unde j va comunica procedurii numrul ferestrei ce trebuie nchise. Prin c vom nota numrul
minimal de click-uri, necesare pentru a nchide fereastra j.Este cunoscut faptul, c pentru o definire corect a unui algoritm recursiv trebuie s existe:
cazuri elementare, care se rezolv direct;cazuri care nu se rezolv direct, ns procesul de calcul n mod obligatoriu progreseazctre un caz elementar.
Conform condiiilor problemei, elementar va fi cazul n care fereastra j este deschis, iarcolul dreapta sus al acestei ferestre este vizibil. n astfel de cazuri nchidem fereastra j, adicfacem un click (stabilim c:=c+1) i marcm fereastra respectivca fiind una nchis.
Cazul care nu se rezolv direct apare atunci cnd fereastra j este deschis, ns colul dreaptasus al acestei ferestre nu este vizibil. n astfel de cazuri apelm recursiv procedura pentru ultima dinferestrele deschise ce acoper colul dreapta sus al ferestrei curente j.
n programul ce urmeazcazurile elementare i cele ce nu se rezolv direct sunt identificatecu ajutorul funciei booleene EstePestei tabloului de indicatori EsteInchisa.
ProgramFerestre;
{ Clasele 10-12 }
const
nmax=100; { numarul maximal de ferestre }
type
Window = recordls: integer; { linia coltului stanga sus }
cs: integer; { coloana coltului stanga sus }
ld: integer; { linia coltului dreapta jos }
cd: integer; { coloana coltului dreapta jos }
end;
var
n: integer; { numarul de ferestre deschise }
F: array [1..nmax] of Window; { ferestrele deschise }
c: integer; { numarul necesar de click-uri }
EsteInchisa: array[1..nmax] of boolean; { indicatorul ferestrelor inchise }
procedure Citeste;
vari: integer;
Intrare: text;
begin
assign(Intrare, 'FERESTRE.IN');
reset(Intrare);
readln(Intrare, n);
for i:=1 to n do
readln(Intrare, F[i].ls, F[i].cs, F[i].ld, F[i].cd);
close(Intrare);
end; { Citire }
procedure Scrie;
varIesire: text;
begin
assign(Iesire, 'FERESTRE.OUT');
7/30/2019 Brosura ORI 2013
19/53
19
rewrite(Iesire);
writeln(Iesire, c);
close(Iesire);
end; { Scrie }
function EstePeste(a: integer; b: integer): boolean;
{ Retutneaza TRUE daca fereastra a acopera coltul }
{ dreapta sus al ferestrei b si FALSE in caz contrar }
begin
EstePeste:=FALSE;
if (F[b].ls>=F[a].ls) and
(F[b].ls=F[a].cs) and
(F[b].cd
7/30/2019 Brosura ORI 2013
20/53
20
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Ferestre, 07-09
7/30/2019 Brosura ORI 2013
21/53
21
Parcare auto
O parcare auto este format dintr-un ir (rnd) lung de locuri de parcare. Locurile de parcaresunt numerotate de la stnga la dreapta prin 1, 2, 3, ...,N. Toate locurile de parcare sunt ocupate deautomobile.
Fiecare automobil este de un anumit tip, iar unele automobile din ir pot avea tipuri identice.Tipurile sunt simbolizate prin numerele ntregi 1, 2, 3, ...,M.
Un grup format din doi muncitori au decis s ordoneze automobilele parcate astfel, ncttipurile respective s fie n ordine cresctoare de la stnga la dreapta. Pentru a ordona automobilele,muncitorii folosesc urmtoarea metod.
Prin definiie, o rundconst din urmtoarele operaii consecutive:
1)mai nti, fiecare din muncitori se urc n cte o main;2) n continuare, muncitorii scot simultan din ir mainile n care se afl;3)dup aceasta, muncitorii parcheaz mainile scoase n locurile disponibile i se coboar din
ele.
S considermurmtorul exemplu. Parcarea are 5 locuri, toate fiind ocupate de automobile.Automobilele parcate sunt de tipurile 1, 2, 3 i 4.Plasarea iniial a automobilelor, de la stnga ladreapta, redat prin tipul lor, este (1, 3, 2, 4, 3).
Runda 1. Schimbm cu locul automobilele de pe poziiile 2 i 3. Obinem plasarea(1, 2, 3, 4, 3).
Runda 2. Schimbm cu locul automobilele de pe poziiile 4 i 5. Obinem plasarea(1, 2, 3, 3, 4).
Sarcin.Scriei unprogram care calculeaz o secven de runde, ce ordoneaz automobileleparcate n aa mod, nct tipurile lor s fie n ordine cresctoare de la stnga la dreapta.
Date de intrare. Fiierul text PARCARE.INconine pe prima linie numerele ntregi NiM,separate prin spaiu. Linia a doua a fiierului de intrare conine N numere ntregi, separate prinspaiu, unde al i-lea numr reprezint tipul automobilului de pe locul de parcare i.
Date de ieire. Prima linie a fiierului textPARCARE.OUT va conine un numr ntreg Rnumrul de runde. Fiecare din urmtoarele R linii ale fiierului de ieire va conine cte dounumere ntregi, separate prin spaiu. Numerele de pe linia ja fiierului de ieire reprezint locurilede parcare, automobilele de pe care au fost reamplasate n runda 1j . Rundele apar n fiierul deieire n ordine efecturii lor. Dac problema admite mai multe soluii, n fiierul de ieire se vascrie doar una, oricare din ele.
Restricii. 1 N 20000; 2 M 50. Exist cel puin cte un automobil de fiecare tip. Nu seadmit soluiile ce conin mai mult de 1N de runde. Timpul de execuie nu va depi 1,0 secunde.Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumireaPARCARE.PAS, PARCARE.C sau PARCARE.CPP.
Exemplu.
PARCARE.IN PARCARE.OUT
5 4 2
1 3 2 4 3 2 3
4 5
7/30/2019 Brosura ORI 2013
22/53
22
Rezolvare
Pentru a gsi una din soluiile problemei, vom simula procesul de lucru al celor doi muncitori.
Fie Sun tablou format din numere ntregi, ce reprezint starea iniial a parcrii, iarF untablou formar din numere ntregi, ce reprezint starea final a parcrii. Evident, tabloul Fpoate fi
obinut din tabloul Sprin sortarea acestuia n ordine cresctoare.Presupunem c la un anumit pas al algoritmului, tabloul Sreprezint starea curent a parcrii.
Pentru a simula o rund ce reamplaseaz automobilele conform cerinelor din enunul problemeiexecutm urmtorii pai:
1)parcurgnd tablourile S i F, identificm n S prima din poziiile pe care se afl unautomobil nepotrivit i memorm aceast poziie n variabila a;
2)examinnd poziiile 1a , 2a .a.m.d. din tabloul S, identificm n el prima din poziiilece conine un automobil potrivit i memorm aceast poziie n variabila b;
3)reamplasm automobilele din poziiile ai b, schimbnd cu locul elementele respectiveale tabloului S.
Evident, procesul de calcul se va termina dup parcurgerea complet a tablourilor SiF, iarnumrul de runde nu va depi valoarea de 1N , stabilit n restriciile problemei.
n programul ce urmeaz, sortarea tabloului Fse efectueaz prin metoda bulelor. Amintim cn aceast metod se compar elementele vecine ]1[],[ jFjF ale tabloului F, parcurgereatabloului efectundu-se de cel mult )1(N ori. Dac ]1[][ jFjF , elementele vecine seschimb cu locul.
ProgramParcare;
{ Clasele 07-09. Metoda BubleSort }
constNmax = 20000;
Mmax = 50;
var
S, F: array[1..Nmax] of integer;
A, B: array[1..Nmax] of integer;
N: integer;
M: integer;
R: integer;
procedure Input;
var
InputFile: text;
i: integer;begin
assign(InputFile, 'PARCARE.IN');
reset(InputFile);
readln(InputFile, N, M);
for i:=1 to N do
read(InputFile, S[i]);
close(InputFile);
end; { Input }
procedure Output;
var
OutputFile: text;
j: integer;begin
assign(OutputFile, 'PARCARE.OUT');
rewrite(OutputFile);
7/30/2019 Brosura ORI 2013
23/53
23
writeln(OutputFile, R);
if R0 then
for j:=1 to R do
writeln(OutputFile, A[j], ' ', B[j]);
close(OutputFile);
end; { Output }
procedure Sort;
{ Sortarea prin metoda bulelor }
var
i, j, k: integer;
begin
for i:=1 to N-1 do
for j:=1 to N-1 do
if F[j]>F[j+1] then
begin k:=F[j]; F[j]:=F[j+1]; F[j+1]:=k; end;
end; { Sort }
procedure Process;
var
i, j, k: integer;
begin
F:=S;
Sort;
R:=0;
for i:=1 to N-1 do
if S[i]F[i] then
for j:=i+1 to N do
if F[i]=S[j] then
begin
k:=S[i]; S[i]:=S[j]; S[j]:=k;
R:=R+1; A[R]:=i; B[R]:=j;
break;
end; { if }
end; { Process }
begin
Input;
Process;
Output;
end.
Din analiza textului procedurii Sort rezult c complexitatea temporal a acesteia este deordinul O )( 2N . Complexitatea temporal a procedurii Process este, de asemenea, de ordinul O
)( 2N . Prin urmare, timpul cerut de program va fi de ordinul O )( 2N .
Conform restriciilor problemei, N 20000. Evident, n cel mai dificil caz, timpul de calculva fi proporional cu 982 10108000202 . ntruct aceast mrime este comparabil cucapacitatea de prelucrare a calculatoarelor personale, exist riscul ca programul de mai sus s nu sencadreze n limita de 2 secunde, stabilit n restriciile problemei.
O reducere a timpului de calcul poate fi obinut prin alegerea unei metode mai rapide desortare a tabloului F. Una din soluiile posibile ar fi utilizarea algoritmului QuickSort (sortarearapid), bazat pe utilizarea tehnicii mparte i stpnete. Ideea acestei tehnici const n divizareatabloului iniial n dou sub-tablouri, care sunt sortate separat. La rndul lor, pentru a fi sortate,fiecare din aceste sub-tablouri sunt din nou divizate n cte dou sub-tablouri .a.m.d. De obicei,
algoritmul QuickSortse implementeaz prin metoda recursiei.
7/30/2019 Brosura ORI 2013
24/53
24
n general, de la competitorii din clasele a 7-a a 9-a nu se cere cunoaterea acestor metode,ntruct procedura respectiv este deja implementat n mediului de dezvoltare a programelor FreePascal. Este suficient ca ei s o poat apela din bibliotecile standard.
Pentru informare, prezentm mai jos o nou versiune a procedurii Sort, bazat pe utilizareaalgoritmului QuickSort.
ProgramParcare;{ Clasele 07-09. Metoda QuickSort }
const
Nmax = 20000;
Mmax = 50;
var
S, F: array[1..Nmax] of integer;
A, B: array[1..Nmax] of integer;
N: integer;
M: integer;
R: integer;
procedure Input;
varInputFile: text;
i: integer;
begin
assign(InputFile, 'PARCARE.IN');
reset(InputFile);
readln(InputFile, N, M);
for i:=1 to N do
read(InputFile, S[i]);
close(InputFile);
end; { Input }
procedure Output;
var
OutputFile: text;
j: integer;
begin
assign(OutputFile, 'PARCARE.OUT');
rewrite(OutputFile);
writeln(OutputFile, R);
if R0 then
for j:=1 to R do
writeln(OutputFile, A[j], ' ', B[j]);
close(OutputFile);
end; { Output }
type Stare = array[1..Nmax] of integer;
Procedure Sort(var G: Stare);
{ Sortare prin metoda QuickSort }
var
x, t: byte;
Procedure Qs(l, r: integer);
{ Algoritmul QuickSort }
var i, j: integer;
begin
i:=l; j:=r;
x:=G[(longint(l)+r)div 2];
while i
7/30/2019 Brosura ORI 2013
25/53
25
begin
t:=G[i]; G[i]:=G[j]; G[j]:=t;
inc(i); dec(j);
end;
end;
if i
7/30/2019 Brosura ORI 2013
26/53
26
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
Punctajul total acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Parcare, 07-09
0
50
100
150
200
250
300
350
400
450
500
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41
Total, 07-09
7/30/2019 Brosura ORI 2013
27/53
27
Clasele 10 12
Denumirea
problemei
Numrul depuncte alocat
problemei
Denumirea
fiierului surs
Denumirea
fiierului deintrare
Denumirea
fiierului deieire
Ceasul 100CEAS.PAS
CEAS.C
CEAS.CPP
CEAS.IN CEAS.OUT
Imagini 100IMAGINI.PAS
IMAGINI.C
IMAGINI.CPP
IMAGINI.IN IMAGINI.OUT
Blocuri depiatr
100BLOCURI.PAS
BLOCURI.C
BLOCURI.CPP
BLOCURI.IN BLOCURI.OUT
Formule 100FORMULE.PAS
FORMULE.C
FORMULE.CPP
FORMULE.IN FORMULE.OUT
Ferestre 100FERESTRE.PAS
FERESTRE.C
FERESTRE.CPP
FERESTRE.IN FERESTRE.OUT
Parcare auto 100PARCARE.PAS
PARCARE.C
PARCARE.CPP
PARCARE.IN PARCARE.OUT
Total 600 - - -
7/30/2019 Brosura ORI 2013
28/53
28
Ceasul
Ana a primit un cadou special un ceas digital, care indic timpul curent n formatulHH:MM:SS, unde HHreprezint ora, MM minutele, iarSSsecundele. Specificul acestui ceas constn faptul c n momentul n care timpul indicat de el reprezint un palindrom, ceasul reproduce o
melodie din renumitul film In Time.Ana iubete att de mult melodia din filmul In Time, nct de fiecare dat cum se uit la
ceas, imediat dorete s tie, cnd din nou va fi redat melodia respectiv.
Prin definiie, timpul indicat de ceas este un palindrom, dac indicaiile ceasului se citesc nacelai fel att de la stnga la dreapta, ct i de la dreapta la stnga. De exemplu, timpul 15:22:51este un palindrom.
Sarcin.Elaborai un program, care, cunoscnd indicaiile curente ale ceasului, determin celmai apropiat momentul de timp n care din nou va fi redat melodia din filmul In Time.
Date de intrare: Fiierul text CEAS.IN conine pe o singur linie un ir de caractere
timpul curent scris n formatul HH:MM:SS.
Date de ieire: Fiierul text CEAS.OUTva conine pe o singur linie un ir de caractere celmai apropiat moment de timp n care din nou va fi redat melodia din filmul In Time. Momentulde timp va fi scris n formatul HH:MM:SS.
Restricii: 00 HH< 24; 00 MM< 60, 00 SS < 60.Timpul de execuie nu va depi 0,1secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va aveadenumirea CEAS.C, CEAS.CPP sau CEAS.PAS.
Exemplu 1.
CEAS.IN CEAS.OUT
15:11:52 15:22:51
Exemplu 2.
CEAS.IN CEAS.OUT
23:56:32 00:00:00
Rezolvare
Vom rezolva problema prin metoda forei brute, gsind palindromul din enunul problemeiprin trierea secundelor, pornind de la timpul curent.
Conform restriciilor problemei, timpul curent poate lua valori de pn la 24 de ore s au, nbaza unor calcule elementare, pn la 86400 de secunde. Prin urmare, pentru memorarea timpuluivom folosi variabile de tipul longint.
ProgramCeasul;
{ Clasele 10-12 }uses Sysutils; { unitatea Free Pascal ce contine functia IntToStr }
var TC : longint; { timpul curent in secunde }
7/30/2019 Brosura ORI 2013
29/53
29
TM : string; { timpul de redare a melodii in formatul HH:MM:SS }
procedure Citeste;
var i : integer;
Intrare : text;
C : string; { indicatiile curente ale ceasului }
H, M, S : longint; { indicatiile curente: ore, minute, secunde }
R : string;
begin
assign(Intrare, 'CEASUL.IN');
reset(Intrare);
readln(Intrare, C);
close(Intrare);
R:=C[1]; R:=R+C[2];
H:=StrToInt(R);
R:=C[4]; R:=R+C[5];
M:=StrToInt(R);
R:=C[7]; R:=R+C[8];
S:=StrToInt(R);
TC:= H*3600+M*60+S;
end; { Citeste }
function Format(T : longint) : string;
{ Transforma timpul T din secunde in formatul HH:MM:SS }
var HH, MM, SS : string;
R : string;
begin
HH:=IntToStr(T div 3600);
if length(HH)=1 then HH:='0'+HH;
T:=Tmod3600;
MM:=IntToStr(T div 60);
if length(MM)=1 then MM:='0'+MM;
T:=Tmod60;
SS:=IntToStr(T);
if length(SS)=1 then SS:='0'+SS;Format:=HH+':'+MM+':'+SS;
end; { Format }
function EstePalindrom(Q : string) : boolean;
{ Returneaza TRUE daca Q este un palindrom si FALSE in caz contrar }
var i : integer;
L : integer;
begin
L:=length(Q);
EstePalindrom:=TRUE;
for i:=1 to (L div 2) do
if Q[i]Q[L-i+1] then EstePalindrom:=FALSE;end; { EstePalindrom }
procedure Calculeaza;
{ Calculeaza momentul redarii melodii }
var T : longint;
begin
T:=TC;
repeat
T:=T+1;
if T>=24*3600 then T:=0;
TM:=Format(T);
until EstePalindrom(TM);
end; { Calculeaza }
procedure Scrie;
var Iesire : text;
7/30/2019 Brosura ORI 2013
30/53
30
begin
assign(Iesire, 'CEASUL.OUT');
rewrite(Iesire);
writeln(Iesire, TM);
close(Iesire);
end; { Scrie }
begin
repeat
Citeste;
Calculeaza;
Scrie;
until false;
end.
Instruciunile din ciclul repeat al procedurii Calculeaza se va executa de cel mult86400 106 ori. n procedura Calculeaza sunt apelate funciile Format iEstePqalindrom, complexitatea temporal a crora este de ordinul 101. Prin urmare,
complexitatea temporal a programului elaborat este de ordinul 107
, mrime cu mult mai mic dectcapacitatea de prelucrare a calculatoarelor personale. Evident, timpul de execuie va fi mai mic ca osecund.
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
Ceasul, 10-12
7/30/2019 Brosura ORI 2013
31/53
31
Imagini
Imaginile color (vezi desenul) pot fi codificate cu ajutorul unui tablou bidimensional cu n linii
i m coloanemnij
bB . Elementul bij indic printr-un numr natural culoarea microzonei
respective, folosind n acest scop un sistem prestabilit de codificare a culorilor, de exemplu: alb (bij
= 0), neagr (bij = 1), roie (bij = 2) etc. Pentru a colora imaginile editoarele grafice ofer uninstrument special denumit Umple-cu-culoare, aplicarea cruia imit procesul de scurgere avopselei din borcan n microzona curent, din ea n microzonele adiacente de aceeai culoare.a.m.d. Evident, vopseaua poate curge dintr-o microzon n alta numai atunci cnd ele au o laturcomun.
Sarcin.Elaborai un program pentru realizarea instrumentului Umple-cu-culoare.
Aplicarea instrumentului Umple-cu-culoare:a - imaginea iniial; b - imaginea final; c - codificarea culorilor
Date de intrare. Fiierul text IMAGINI.INconine pe prima linie numerele naturale n, mseparateprin spaiu. Fiecare din urmtoarele nlinii conine cte mnumere separate prin spaiu. Liniai +1 a fiierului de intrare conine numerele bi1, bi2, ..., bim ale imaginii iniiale. Ultima linie afiierului conine trei numere naturalep, q, kseparate prin spaiu. Numerelep, qindic coordonatelezonei asupra creia trebuie aplicat instrumentul Umple-cu-culoare, iar numrul k indic codulculorii din borcan.
Date de ieire. Fiierul text IMAGINI.OUT va conine pe fiecare din cele n linii cte mnumere separate prin spaiu. Linia i a fiierului de ieire conine numerele bi1, bi2, ..., bim aleimaginii finale.
Restricii. 1 n, m 20, 0 bij, k 10, bij k. Timpul de execuie nu va depi 0,1 secunde.Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va avea denumirea
IMAGINI.PAS, IMAGINI.C sau IMAGINI.CPP.Exemplu. Pentru desenul de mai sus avem:
IMAGINI.IN IMAGINI.OUT
7 7
1 0 0 0 1 0 1
0 1 1 1 1 0 0
0 0 1 0 1 1 0
0 1 0 0 1 0 0
0 1 0 0 0 1 1
1 1 1 1 0 0 0
0 1 0 0 0 1 1
2 3 2
1 0 0 0 2 0 1
0 2 2 2 2 0 0
0 0 2 0 2 2 0
0 1 0 0 2 0 0
0 1 0 0 0 1 1
1 1 1 1 0 0 0
0 1 0 0 0 1 1
7/30/2019 Brosura ORI 2013
32/53
32
Rezolvare
Vom nota prin s culoarea microzonei asupra creia trebuie aplicat instrumentul Umple-cu-culoare. Evident,s = bpq. Pentru a imita procesul de scurgere a vopselei din borcan n microzona (p,q), iar din ea n microzonele adiacente de aceeai culoare .a.m.d., vom elabora o procedurrecursiv, denumit Vopsea, care efectueaz urmtoarele operaii:
dac culoarea microzonei curente nu coincide cu s, atunci n procedura Vopsea nu seefectueaz nici o operaie;dac culoarea microzonei curente coincide cu s, atunci microzona n studiu este vopsit n
culoarea k, iar procedura Vopseaeste apelat recursiv pentru cele patru microzonele adiacente: ceade sus (p-1, q), cea din dreapta (p, q+1), cea de jos (p+1, q) i cea din stnga (p, q-1).
ntruct k bpq, laexecuia apelurilor recursive Vopsea(p,q)microzona deja colorat numai este examinat a doua oar, fapt ce exclude ciclarea programului. De asemenea, pentru a evitaverificrile necesare n cazul microzonelor de la margini, vom ncadra imaginea ntru-un chenar,nscriind n celulele respective ale tablouluiBvaloarea -1.
ProgramImagini;
{ Clasele 10-12 }
const nmax=21;
mmax=21;
var n, m, p, q, k, i, j : integer;
B : array[0..nmax, 0..mmax] of -1..255;
Finput, Foutput : text;
procedure UmpleCuCuloare(p, q, k : integer);
var i, j, s : integer;
{ s - culoarea initiala a microzonei (i, j) }
procedure Vopsea(p, q : integer);
{ Simulam scurgerea vopselei }
begin
if B[p, q]=s then
begin
{ vopsim microzona (p, q) }
B[p, q]:=k;
{ vopsim microzona de sus }
Vopsea(p-1, q);
{ vopsim microzona din dreapta }
Vopsea(p, q+1);
{ vopsim microzona de jos }
Vopsea(p+1, q);
{ vopsim microzona din stinga }
Vopsea(p, q-1);
end; { then }end; { Vopsea }
begin
{ memoram in s culoarea microzonei (p, q) }
s:=B[p, q];
{ bordam tabloul B cu -1 }
for i:=0 to n+1 do
begin B[i, 0]:=-1; B[i, m+1]:=-1; end;
for j:=0 to m+1 do
begin B[0, j]:=-1; B[n+1, j]:=-1; end;
Vopsea(p, q);
end; { UmpleCuCuloare }
begin
assign(Finput, 'IMAGINI.IN');
assign(Foutput, 'IMAGINI.OUT');
7/30/2019 Brosura ORI 2013
33/53
33
reset(Finput);
rewrite(Foutput);
readln(Finput, n, m);
for i:=1 to n do
begin
for j:=1 to m do read(Finput, B[i, j]);
readln(Finput);
end;
readln(Finput, p, q, k);
close(Finput);
UmpleCuCuloare(p, q, k);
for i:=1 to n do
begin
for j:=1 to m do write(Foutput, B[i, j], ' ');
writeln(Foutput);
end;
close(Foutput);
end.
Evident, numrul de apeluri recursive ale procedurii Vopsea nu poate depi numrul de
microzone ale imaginii. Prin urmare, timpul de execuie T n m, iar spaiul necesar de memorie nstiv Vs n m. Conform restriciilor problemei, dimensiunile imaginii n, m 20, deci timpul deexecuie T
7/30/2019 Brosura ORI 2013
34/53
34
Blocuri de piatr
InfoCityeste un ora modern i foarte frumos. Oraul este n permanent dezvoltare i a ajunsdeja la marginea rului InfoRiver. Primarul oraului dorete s extind InfoCitype cellalt mal alrului, intenionnd s construiasc n acest scop un pod. Pentru a se integra organic n arhitecturaoraului, podul va avea exact doi piloni, ce vor fi construii din blocuri de piatr. Pentru construciaunui pilon sunt necesarepblocuri de piatr.
Primria oraului dispune de nseturi de blocuri de piatr, numerotate prin 1, 2, 3, ..., i, ..., n,setul i coninnd aiblocuri. Pentru construcia fiecruia din cei doi piloni sunt necesare cte p
blocuri de piatr. Toate seturile de blocuri de piatr trebuie distribuite ntre cei doi piloni n curs deconstrucie.
Evident, exist mai multe modaliti de a distribui seturile de blocuri de piatr ntre cei doipiloni.
Sarcin. Elaborai un program, care calculeaz numrul de variante posibile de distribuire aseturilor respective ntre cei doi piloni ai podului n aa mod, nct toate seturile s fie distribuite,iarfiecruia din piloni s-i revin cel puinp blocuri de piatr.
Date de intrare: Fiierul text BLOCURI.INconine dou linii. Prima linie a fiierului deintrare conine numerele ntregi n i p, separate prin spaiu. Linia a doua a fiierului de intrareconine numerele ntregi a1, a2, ..., ai, ..., an, separate prin spaiu, unde ai reprezint numrul de
blocuri de piatr din setul i.
Date de ieire: Fiierul text BLOCURI.OUTva conine pe o singur linie un numr ntregnumrul de variante posibile de distribuire a seturilor de blocuri.
Restricii: 1 n 50; 1 p 10000; 1 ai 109. Timpul de execuie nu va depi 1
secund. Programul va folosi cel mult 32 Megaoctei de memorie operativ. Fiierul surs va aveadenumirea BLOCURI.PAS, BLOCURI.C sau BLOCURI.CPP.
Exemplu 1.
BLOCURI.IN BLOCURI.OUT
4 6 4
3 1 4 6
Explicaie. Seturile de blocuri i = 1, 2, 3, 4,pot fi distribuite dup cum urmeaz:
Varianta Pilonul 1 Pilonul 2
1 1, 2, 3 4
2 1, 3 2, 4
3 2, 4 1, 3
4 4 1, 2, 3
Exemplu 2.
BLOCURI.IN BLOCURI.OUT
3 7 0
5 3 6
Explicaie. ntruct avem doar trei seturi, pentru oricare din variantele de distribuire, unuia dinpiloni i va reveni doar un singur set. ntruct nici unul din seturi nu conine cel puin 7 blocuri de
piatr, nu exist nici o variant de distribuire a seturilor de blocuri, ce ar corespunde enunuluiproblemei.
7/30/2019 Brosura ORI 2013
35/53
35
Rezolvare
Vom ncerca mai nti s rezolvm problema prin metoda trierii. n acest scop, vom generatoate variante posibile de distribuire a seturilor de blocuri de piatr ntre cei doi piloni. Dinvariantele generate le vom contabiliza doar pe acelea n care fiecruia din cei doi piloni i revin ctecel puinp blocuri de piatr.
Pentru a genera toate variante posibile de distribuire a seturilor de blocuri ntre cei doi piloniai podului vom utiliza tabloul V[1..n], fiecare din componentele cruia poate lua valorile 0, 1.Valoarea 0 a componentei V[i]indic faptul, c blocul i a fost alocat a fost alocat pilonului 1, iarvaloarea 1 c blocul i a fost alocat pilonului 2.
Componentele tabloului Vpot fi tratate ca cifre ale unui numr natural, scris n sistemul binarde numeraie. Evident, fiecrei valori distincte a acestui numr binar i corespunde o variant dedistribuire a seturilor de blocuri ntre cei doi piloni.
Pentru a genera toate variantele posibile, iniial i atribuim lui V valoarea 0. Presupunem c Vare deja o anumit valoare binar. n continuare, mrim numrul Vcu o unitate binar .a.m.d., pn
cnd ajungem la valoarea 2
n
1.
ProgramBlocuriMetodaTrierii;
{ Clasele 10-12 }
const nmax=50; { numarul maximal de seturi }
var V : array[1..nmax] of integer;
A : array[1..nmax] of longint;
n : integer;
p : integer;
K : longint; { numarul de variante posibile }
D : integer; { indicatorul de depasire la incrementarea lui V }
procedure Citeste;
var Intrare : text;
i : integer;
begin
assign(Intrare, 'BLOCURI.IN');
reset(Intrare);
readln(Intrare, n, p);
for i:=1 to n do
read(Intrare, A[i]);
close(intrare);
end; { Citeste }
procedure Scrie;
var Iesire : text;
begin
assign(iesire, 'BLOCURI.OUT');
rewrite(Iesire);
writeln(Iesire, K);
close(Iesire);
end; { Scrie }
procedure Initializare;
{ Initializeaza V in zero }
var i : integer;
begin
for i:=1 to n do V[i]:=0;
end; { initializare }
7/30/2019 Brosura ORI 2013
36/53
36
procedure Incrementare;
{ Mareste V cu o unitate in sistemul binar }
var i : integer;
begin
D:=1;
for i:= 1 to n do
begin
V[i]:=V[i]+D;
D:=0;
if V[i]=2 thenbegin V[i]:=0; D:=1; end;
end;
end; { Incrementare }
procedure Contabilizeaza;
var i : integer;
p1, p2 : longint; {numarul de pietre per pilon }
begin
p1:=0; p2:=0;
for i:=1 to n do
begin
if V[i]=0 then p1:=p1+A[i];
if V[i]=1 then p2:=p2+A[i];
end;
if (p1>=p) and(p2>=p) then K:=K+1;
end; { Contabilizeaza }
procedure Calculeaza;
var i : integer;
begin
Initializare;
K:=0;
repeat
Contabilizeaza;
Incrementare;
until D=1;end; { Calculeaza }
begin
Citeste;
Calculeaza;
Scrie;
end.
Timpul cerut de procedura Calculeaza este proprional cu numrul de apeluri aleprocedurilorContabilizeaza i Incrementare din ciclul repeat. Evident, acest numr
este egal cu 2n
. Fiecare din procedurile Contabilizeazai Incrementareconine cte unciclu, care se va executa de cel mult nori. Prin urmare, timpul cerut de program va fi proporionalcu 2nn.
Conform restriciilor problemei, n 50. Evident, pentru n = 50, timpul cerut de program va fiproporional cu 250 50 5,7 1016. ntruct aceast valoare este cu mult mai mare dect capacitateade prelucrare a calculatoarelor personale ( 109 operaii pe secund), timpul de execuie va fi deordinul 108secunde, adic de circa trei ani.
Prin urmare, metoda trierii poate fi aplicat doar n cazul unor valori mici ale lui n. Prinexperimente pe calculator ne putem convinge c programul de mai sus se ncadreaz n dousecunde doar pentru valorile n 20.
Pentru a reduce timpul de calcul, vom soluiona problema prin metoda programrii dinamice.Amintim c aceast metod se bazeaz pe utilizarea formulelor recurente, care, n cazul nostru,
7/30/2019 Brosura ORI 2013
37/53
37
trebuie s ne permit calcularea numrului variantelor de distribuire a q seturi de blocuri ncondiiile n care numrul variantelor respective pentru 0, 1, 2, ..., )1(q seturi de blocuri este dejacunoscut.
Pentru a deduce formula de care avem nevoie, vom nota prin mqj numrul variantelor dedistribuire a qseturi de blocuri ntre cei doi piloni n aa mod, nct primului pilon s -i revin exact
jblocuri de piatr. Evident, condiiilor problemei vor corespunde doar variantele de distribuirepentru care )( pj i )( pjtq , unde tqreprezint numrul total de blocuri de piatr din seturile
n studiu.
Numrul de variante posibile de distribuire a celor q seturi de blocuri, astfel nct fiecruipilon s-i revin cel puin p blocuri de piatr, poate fi calculat cu ajutorul urmtoarei formulerecurente:
j
jqqj mm ,1 pentru pj i pjtq )( .
n programul ce urmeaz, variabilele mqj sunt memorate n tabloul Modes.
ProgramBlocuriProgramareaDinamica;
{ Clasele 10-12 }
const
MaxN = 50;
MaxP = 10000;
var
Modes: array[0..1, 0..MaxN*MaxP] of Int64;
Blocuri: array[1..MaxN] of LongInt;
N, P: LongInt;
Res: Int64;
procedure InputData;
var
f: Text;
i: LongInt;
begin
Assign(f, 'BLOCURI.IN');
Reset(f);
Readln(f, N, P);
for i := 1 to N do Read(f, Blocuri[i]);
Close(f);
end;
procedure ProcessData;
var
i, j, k, Total: LongInt;
begin
for i := 1 to N do
if Blocuri[i] > P then Blocuri[i] := P;
Total := 0;
for i := 1 to N do Total := Total + Blocuri[i];
for i := 0 to N * P do Modes[0, i] := 0;
for i := 0 to N * P do Modes[0, i] := 0;
Modes[0, 0] := 1;
k := 0;for i := 1 to N do
begin
for j := 0 to N * P do
7/30/2019 Brosura ORI 2013
38/53
38
if Modes[k, j] > 0 then
begin
Modes[1 - k, j] := Modes[1 - k, j] + Modes[k, j];
Modes[1 - k, j + Blocuri[i]] := Modes[1 - k, j + Blocuri[i]] + Modes[k,
j];
end;
k := 1 - k;
for j := 0 to N * P do Modes[1 - k, j] := 0;
end;
for i := P to N * P do
if (Total - i >= P) then Res := Res + Modes[k, i];
end;
procedure OutputData;
var
f: Text;
begin
Assign(f, 'BLOCURI.OUT');
ReWrite(f);
Writeln(f, Res);
Close(f);
end;
begin
InputData;
ProcessData;
OutputData;
end.
Din analiza textului programului de mai sus rezult c soluia propus are complexitateaO(n2p). Conform restriciilor problemei, 1 n 50 i1 p 10000. Prin urmare, n cazul celui mai
complicat test, numrul de operaii va fi de ordinul 2,5 107
, mrime comparabil cu capacitatea deprelucrare a calculatoarelor personale.
Menionm faptul, c la fiecare pas q sunt necesare doar valorile mqj, fapt ce permitereducerea volumului de memorie alocat tabloului Modes de la O(n2p) pn la doar O(np).
7/30/2019 Brosura ORI 2013
39/53
39
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
Blocuri, 10-12
7/30/2019 Brosura ORI 2013
40/53
40
Formule
Se consider urmtoarele formule metalingvistice:
Cifr :: = 0 1 2 3 4 5 6 7 8 9
Numr :: = Cifr Cifr Semn ::= + - * /
Expresie :: = Numr ( Expresie ) Expresie Semn Expresie
Sarcin. Scriei un program care returneaz valoarea DA dac irul de caractere S esteconform definiiei unitii lexicale Expresie i NU n caz contrar.
Date de intrare. Fiierul text FORMULE.IN conine pe fiecare linie cte un ir decaractere S.
Date de ieire.Fiierul text FORMULE.OUTva conine pe fiecare linie valoarea DAdac irul
de caractere din linia respectiv a fiierului de intrare corespunde definiiei i NU n caz contrar.Restricii. irul nevid Sconine cel mult 250 de caractere. Fiierul de intrare conine cel mult
200 de linii. Timpul de execuie nu va depi 0,2 secunde. Programul va folosi cel mult 32Megaoctei de memorie operativ.Fiierul surs va avea denumirea FORMULE.PAS, FORMULE.Csau FORMULE.CPP.
Exemplu.
FORMULE.IN FORMULE.OUT
1+(3-4)+6/12-3*2
+1+
4/(3435+(684-2)*11)
DA
NU
DA
Rezolvare
Conform formulelor metalingvistice din enunul problemei, orice secven de cifre dincomponena irului Sdelimitat de caracterele +, -, *, / sau (, )este un numr care, la rndul su,
poate fi tratat ca o expresie. Prin urmare, prin una sau dou parcurgeri ale irului Sputem nlocuifiecare numr cu un simbol ce ar reprezenta unitatea lexical , de exemplu, E. n
particular, pentru irul 4/(3435+(684-2)*11)obinem: E/(E+(E-E)*E). Din aceleai
considerente, orice caracter +, -, *, / poate fi nlocuit cu un simbol ce ar reprezenta unitatealexical , de exemplu #. n cazul irului de mai sus obinem E#(E#(E#E)#E). ncontinuare, conform formulelor metalingvistice din enunul problemei, vom nlocui fiecare secvenE#Ei (E) prin E. Evident, irul de caractere Seste conform definiiei unitii lexical numai atunci cnd n rezultatul tuturor substituirilor vom obine un ir ce conine un singur caracter,i anume, simbolul E. n programul ce urmeaz substituirile se efectueaz iterativ, iar numruliteraiilor nu depete valoarea n, unde neste lungimea irului S. Prin urmare, timpul de execuieT(n) n3. Evident, pentru n 250, timpul de execuie T(n) 3 s.
ProgramFormule;
{ Clasele 10-12 }
var S : string;
Finput, Foutput : text;
7/30/2019 Brosura ORI 2013
41/53
41
function Substituire(S : string) : string;
{ Inlocuieste semnele +, -, *, / cu caracterul #, }
{ iar numerele cu caracterul E }
var i : integer;
begin
{ din fiecare numar lasam numai prima cifra }
i:=1;
while i
7/30/2019 Brosura ORI 2013
42/53
42
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
Formule, 10-12
7/30/2019 Brosura ORI 2013
43/53
43
Ferestre
Trecerea la interfeele grafice a simplificat cu mult interaciunea om-calculator. Amintim, cn cazul interfeelor grafice ecranul monitorului simbolizeaz o mas de lucru, pe care apar ferestre.Concomitent, trecerea la interfeele grafice a pus nceputul unui ir interminabil de glume, una din
ele referindu-se la faptul c, n sfrit, calculatoarele ne ofer posibilitatea s avem pe mas virtualde lucru aceiai dezordine,pe care o avem i pe mas propriu-zis.
Vasile folosete un sistem de operare, care deschide pe ecran numeroase ferestre. n acestsistem de operare ecranul monitorului este mprit n ptrate elementare cu dimensiunile 11, careformeaz un rastru. Liniile rastrului sunt numerotate de la 1 de sus n jos, iar coloanele suntnumerotate de la 1 de la stnga la dreapta. Astfel, fiecare ptrat elementar de pe ecran poate fiidentificat specificnd numrul liniei i numrul coloanei pe care se afl.
Fiecare fereastr este un dreptunghi format din unul sau mai multe ptrate elementare. Ofereastr nou deschis poate s se suprapun parial sau total peste alte ferestre, deschise n
prealabil. Evident, ptrelele ferestrelor deschise anterior, ce au fost acoperite de fereastra numai ce
deschis, devin invizibile.Putem nchide o fereastr dac executm un clic n ptratul elementar ce constituie colul din
dreapta sus al ferestrei, cu condiia c acesta este vizibil.
Sarcin. Scriei un program care s determine numrul minim de click-uri necesare pentru anchide fereastr pe care am deschis-o prima.
Date de intrare. Fiierul text FERESTRE.IN conine pe prima linie un numr natural n,reprezentnd numrul de ferestre deschise pe ecran.Fiecare dintre urmtoarele n linii ale fiieruluide intrare conine ctepatru numere naturale ls, cs, ld, cd,separate prin spaiu, cu semnificaia "amdeschis o fereastr care are colul din stnga sus pe linia lsi coloana cs, respectiv colul din dreapta
jos pe linia ldi coloana cd". Ferestrele au fost deschise n ordinea n care apar n fiierul de intrare.Date de ieire. Fiierul text FERESTRE.OUTva conine o singur linie pe care va fi scris
numrul minim de click-uri, necesare pentru a nchide prima fereastr deschis.
Restricii. 1000 n ; 000101 ldls ; 000101 cdcs . Timpul de execuie nu va
depi 0,2 secunde. Programul va folosi cel mult 32 Megaoctei de memorie operativ.Fiierul surs va avea
denumirea FERESTRE.PAS, FERESTRE.C sau FERESTRE.CPP.
Exemplul 1. Exemplul 2.
FERESTRE.IN FERESTRE.OUT FERESTRE.IN FERESTRE.OUT
3 3 3 33 1 6 4 4 1 6 3
1 2 4 6 2 2 5 5
2 3 5 5 1 4 3 6
Exemplul 3.
FERESTRE.IN FERESTRE.OUT
3 1
3 3 4 4
1 1 2 2
5 5 6 6
7/30/2019 Brosura ORI 2013
44/53
44
Rezolvare
Vom calcula numrul minim de click-uri necesare pentru a nchide prima fereastr pe care amdeschis-o prin metoda recursiei. Vom elabora n acest scop procedura InchideFereastra(j),unde j va comunica procedurii numrul ferestrei ce trebuie nchise. Prin c vom nota numrul
minimal de click-uri, necesare pentru a nchide fereastra j.Este cunoscut faptul, c pentru o definire corect a unui algoritm recursivtrebuie s existe:
cazuri elementare, care se rezolv direct;cazuri care nu se rezolv direct, ns procesul de calcul n mod obligatoriu progreseazctre un caz elementar.
Conform condiiilor problemei, elementar va fi cazul n care fereastra j este deschis, iarcolul dreapta sus al acestei ferestre este vizibil. n astfel de cazuri nchidem fereastra j, adicfacem un click (stabilim c:=c+1) i marcm fereastra respectivca fiind una nchis.
Cazul care nu se rezolv direct apare atunci cnd fereastra j este deschis, ns colul dreaptasus al acestei ferestre nu este vizibil. n astfel de cazuri apelm recursiv procedura pentru ultima dinferestrele deschise ce acoper colul dreapta sus al ferestrei curente j.
n programul ce urmeaz cazurile elementare i cele ce nu se rezolv direct sunt identificatecu ajutorul funciei booleene EstePestei tabloului de indicatori EsteInchisa.
ProgramFerestre;
{ Clasele 10-12 }
const
nmax=100; { numarul maximal de ferestre }
type
Window = recordls: integer; { linia coltului stanga sus }
cs: integer; { coloana coltului stanga sus }
ld: integer; { linia coltului dreapta jos }
cd: integer; { coloana coltului dreapta jos }
end;
var
n: integer; { numarul de ferestre deschise }
F: array [1..nmax] of Window; { ferestrele deschise }
c: integer; { numarul necesar de click-uri }
EsteInchisa: array[1..nmax] of boolean; { indicatorul ferestrelor inchise }
procedure Citeste;
vari: integer;
Intrare: text;
begin
assign(Intrare, 'FERESTRE.IN');
reset(Intrare);
readln(Intrare, n);
for i:=1 to n do
readln(Intrare, F[i].ls, F[i].cs, F[i].ld, F[i].cd);
close(Intrare);
end; { Citire }
procedure Scrie;
varIesire: text;
begin
assign(Iesire, 'FERESTRE.OUT');
7/30/2019 Brosura ORI 2013
45/53
45
rewrite(Iesire);
writeln(Iesire, c);
close(Iesire);
end; { Scrie }
function EstePeste(a: integer; b: integer): boolean;
{ Retutneaza TRUE daca fereastra a acopera coltul }
{ dreapta sus al ferestrei b si FALSE in caz contrar }
begin
EstePeste:=FALSE;
if (F[b].ls>=F[a].ls) and
(F[b].ls=F[a].cs) and
(F[b].cd
7/30/2019 Brosura ORI 2013
46/53
46
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
Ferestre, 10-12
7/30/2019 Brosura ORI 2013
47/53
47
Parcare auto
O parcare auto este format dintr-un ir (rnd) lung de locuri de parcare. Locurile de parcaresunt numerotate de la stnga la dreapta prin 1, 2, 3, ...,N. Toate locurile de parcare sunt ocupate deautomobile.
Fiecare automobil este de un anumit tip, iar unele automobile din ir pot avea tipuri identice.Tipurile sunt simbolizate prin numerele ntregi 1, 2, 3, ...,M.
Un grup format din Wmuncitori a decis s ordoneze automobilele parcate astfel, nct tipurilerespective s fie n ordine cresctoare de la stnga la dreapta. Pentru a ordona automobilele,muncitorii folosesc urmtoarea metod.
Prin definiie, o rundconst din urmtoarele operaii consecutive:4)mai nti, fiecare din muncitori se urc n cte o main;5) n continuare, muncitorii scot simultan din ir mainile n care se afl;6)dup aceasta, muncitorii parcheaz mainile scoase n locurile disponibile i se coboar din
ele.
Pentru eficien, se cere ca ordonarea s se realizeze ntr-un numr ct mai mic de runde. Nueste obligatoriu ca n fiecare din runde s participe toi muncitorii din grup.
S considermurmtorul exemplu. Parcarea are 10 locuri, toate fiind ocupate de automobile.Automobilele parcate sunt de tipurile 1, 2, 3 i 4. Sunt disponibili 4 muncitori. Plasarea iniial aautomobilelor, redat prin tipul lor de la stnga la dreapta, este:
2 3 3 4 4 2 1 1 3 1.
n acest exemplu numrul minim de runde este trei. Dup fiecare din runde, amplasareaautomobilelor ar putea fi, de exemplu, urmtoarea:
1 3 3 4 2 2 1 3 4 1dup runda 1;
1 2 1 4 2 3 3 3 4 1dup runda 2;
1 1 1 2 2 3 3 3 4 4dup runda 3.
Sarcin.Scriei un program care calculeaz o secven care ar include un numr ct mai micde runde i care ordoneaz automobilele parcate n aa mod, nct tipurile lor s fie n ordinecresctoare de la stnga la dreapta.
Date de intrare. Fiierul text PARCARE.INconine pe prima linie numerele ntregi N,MiW, separate prin spaiu. Linia a doua a fiierului de intrare conine Nnumere ntregi, separate prinspaiu, unde al i-lea numr reprezint tipul automobilului de pe locul de parcare i.
Date de ieire. Fiierul text PARCARE.OUTconine peprima linie numrul ntregR numrulde runde. UrmtoareleR linii descriu rundele n ordinea efecturii lor. Pe fiecare din aceste linii,
primul numr ntreg este C numrul automobilelor mutate n runda respectiv. Urmeaz C2 numere ntregi, formnd C perechi, corespunztoare reamplasrilor mainilor, utiliznd numerelelocurilor de parcare. Prima pereche descrie reamplasarea unui automobil: primul ntreg reprezintnumrul locului de parcare de la nceputul rundei, iar al doilea numrul locului de parcare de lasfritul rundei. Urmtorii doi ntregi formeaz o pereche care descrie cum este mutat un altautomobil .a.m.d. Numerele de pe liniile respective sunt separate prin spaiu. ntruct pentrunumrulRpot exista mai multe soluii distincte, programul va scrie n fiierul de ieire numai una ,oricare din ele.
Restricii. 1 N 20000; 2 M 50; 2 W M. Exist cel puin cte un automobil defiecare tip. Timpul de execuie nu va depi 1,0 secunde. Programul va folosi cel mult 32Megaoctei de memorie operativ. Fiierul surs va avea denumirea PARCARE.PAS, PARCARE.Csau PARCARE.CPP.
7/30/2019 Brosura ORI 2013
48/53
48
Exemplu.
PARCARE.IN PARCARE.OUT
10 4 4 3
2 3 3 4 4 2 1 1 3 1 4 9 8 5 9 1 5 8 1
4 3 6 7 3 2 7 6 2
3 4 10 2 4 10 2
Punctaj. Presupunem c dup o executare, n fiierul de ieire a fost scris numrulR. Dac nfiierul de ieire cel puin una din cele R runde nu este descris corect sau secvena respectiv derunde nu realizeaz amplasarea automobilelor n ordinea cerut, vi se acord 0 puncte. n cazcontrar, punctajul pentru fiecare test va fi calculat astfel:
QR ................................10 puncte (punctajul maximal), unde )1/(WNQ .
QRQ 25,1 ..................7 puncte.
QRQ 50,125,1 ..........5 puncte.QRQ 75,150,1 ..........2 puncte.
QR 75,1 ..........................0 puncte.
Rezolvare1
ntruct n enunul problemei nu se cere gsirea secvenelor de lungime minim, pentru acalcula o secvena de runde ce reamplaseaz automobilele vom folosi metoda Greedy. Aceast
metod este aplicabil, ntruct avnd Wmuncitori, n fiecare rund putem muta pe locurile corectecel puin )1(W automobile. Evident, dup )1/(WD runde, undeDeste numrul automobilelor
ce iniial se afl pe poziiile nepotrivite, toate automobilele vor fi parcate corect. ntructND , pentru fiecare test vom lua numrul maximal de puncte.
Evident, un program ce implementeaz metoda Greedy va avea complexitatea O )( 2N .
Competitorii, care nu cunosc metoda Greedy, ar putea s implementeze
Fie Sun tablou format din numere ntregi, ce reprezint starea iniial a parcrii, iarF untablou formar din numere ntregi, ce reprezint starea final a parcrii.
TabloulFpoate fi obinut din tabloul Sprin sortarea acestuia n ordine cresctoare. n funciede metoda de sortare aleas, acest lucru poate fi fcut cu ajutorul unor proceduri de complexitateaO )( 2N metoda bulelor, O )log( NN metoda QuickSort sau O )( NM sortarea binar.Evident, n condiiile restriciilor din enunul problemei, metoda bulelor ar fi prea lent.
Presupunem c tabloul Sconine starea curent a parcrii, iar muncitorii sunt numerotai prin1, 2, 3, ..., W. Algoritmul de calcul al rundei ce mut pe locuri corecte cel puin ( 1W ) automobileinclude urmtoarele operaii:
1. Parcurgnd tablourile S i F, gsim primul din locurile de parcare pe care se afl unautomobil nepotrivit. Memorm acest loc n variabilaA[1] i-l desemnm pe muncitorulnumrul 1 ca fiind responsabil de mutarea acestui automobil. Deocamdat el nc nu tie
pe care loc trebuie s mute automobilul respectiv.
1 Programator Shao Zheng, IOI 2000.
7/30/2019 Brosura ORI 2013
49/53
49
2. Presupunem c la o anumit etap, n variabilaA[i] se pstreaz poziia curent pe care seafl un automobil nepotrivit, pentru care a fost desemnat deja muncitorul i.
3. Parcurgnd n continuare tabloul S, gsim unul din locurile de parcare pe care se afl unautomobil nepotrivit i tipul cruia permite ca el s fie reamplasat pe locul A[i].Memorm acest loc n variabila ]1[iA i desemnm muncitorul )1(i din grup ca fiindresponsabil de mutarea automobilului de pe locul ]1[iA pe loculA[i].
4. Continum acest proces pn cnd sunt repartizai toi muncitorii din grup sau pn cndnu mai sunt automobile care sunt parcate pe locuri nepotrivite.
5. Comunicm primului muncitor, c el trebuie s mute automobilul de pe loculA[1] pe loculA[k], unde keste numrul de muncitori din grup, desemnai n aceast rund pentru a mutaautomobile. Evident, Wk , iar loculA[k] ar putea s fie nepotrivit pentru automobilul
A[1].
Prin urmare, o rund va include urmtoarele reamplasri de automobile: A[1] A[k],A[2] A[1],A[3] A[2], A[k] ]1[kA .
ProgramParcare;
{ Clasele 10-12 }
{ Programmer: Shao Zheng }
{ Email: shaoz@sina.com }
{ Date: 2000.09.23 }
{ Algorithm: Simple Greedy }
const
fin='PARCARE.IN'; {Input File Name}
fon='PARCARE.OUT'; {Output File Name}
MaxCarCount=20010; {Data Boundary}
MaxModeCount=120; {Data Boundary}
MaxWorkerCount=120; {Data Boundary}
Type
TState=array[1..MaxCarCount]of byte; {To Store the cars' state}
var
fi,fo:text; {Input and Output File}
CarCount,ModeCount,WorkerCount:integer;
{The Number of Cars, Modes and Workers}
Original,Final:TState; {Original and Final State}
NeedPrint:Boolean;
Procedure Sort(var A:TState); {QuickSort Algorithm}
var
x,t:byte;
Procedure qs(l,r:integer);
var i,j:integer;
begin
i:=l;j:=r;
x:=a[(longint(l)+r)div 2];
while i
7/30/2019 Brosura ORI 2013
50/53
50
if i
7/30/2019 Brosura ORI 2013
51/53
51
var
ChangeList:array[1..MaxWorkerCount,1..2]of integer;
ChangeCount:integer;
Procedure Change(var Now:TState;const Final:TState;var
rest:integer;dif:integer);
var
workers:array[1..MaxWorkerCount]of integer;
j,w,nextcar:integer;
begin
fillchar(usedslot,sizeof(usedslot),false);
w:=1;
workers[w]:=dif;
usedslot[dif]:=true;
while (w=2)and(dif-1) do
begin
Change(Now,Final,rest,dif);
dif:=GetFirstDif(Now,Final);
end;
inc(result);if needprint then
begin
write(fo,ChangeCount);
7/30/2019 Brosura ORI 2013
52/53
52
for i:=1 to ChangeCount do
write(fo,' ',ChangeList[i,1],' ',ChangeList[i,2]);
writeln(fo);
end;
end;
Process:=result;
end;
Type
TAnswer=Integer;
Var
Answer,Best,Need:TAnswer; {Answers}
t:Integer;
difcount:integer;
time:Longint;
begin
Init; {Initialization}
{Calculate the limits}
difcount:=0;
for t:=1 to CarCount do
if Original[t]Final[t] then inc(DifCount);
Best:=(DifCount-1) div WorkerCount+1;
Need:=(DifCount-1) div (WorkerCount-1)+1;
{Simple Greedy Algorithm}
NeedPrint:=false;
Answer:=Process;
{Output Answer}
rewrite(fo);
writeln(fo,Answer);
NeedPrint:=true;
Answer:=Process;close(fo);
end.
Prin experimente de calcul ne putem convinge c programul de mai sus se ncadreaz nlimitele temporale indicate n restriciile din enunul problemei.
n literatura de specialitate se menioneaz c calcularea unei o secvene ce conine un numrminimal de runde este o problem de complexitate non-polinomial. n consecin, n enunul
problemei o astfel de sarcinnu a fost inclus.
Accentum faptul, c elevii care nu cunosc metoda Greedy trebuie s ncerce s obin unanumit numr de puncte prin implementarea unor abordri euristice. Faptul c astfel de soluii suntacceptabile rezult din algoritmul de acordare a punctelor, inclus n enunul problemei.
7/30/2019 Brosura ORI 2013
53/53
Punctajul acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
Punctajul total acumulat de fiecare competitor
Not: Pe orizontal sunt competitorii, simbolizai prin numerele 1, 2, 3, ... .a.m.d., iarpe vertical punctajul fiecruia din ei
0
10
20
30
40
50
60
70
80
90
100
Parcare, 10-12
0
50
100
150
200
250
300
350
400
450
500
Total, 10-12