brosura ori 2013

Upload: lilian-ciobanu

Post on 14-Apr-2018

224 views

Category:

Documents


0 download

TRANSCRIPT

  • 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: [email protected] }

    { 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