Īncercati-va puterile!

Probleme propuse pentru REZOLVARE

La īnceputul lunii ianuarie s-a desfaurat la Poiana Pinului (Buzau) o tabara de pregatire si odihna a elevilor olimpici. Acestia s-au odihnit rezolvānd si propunānd probleme. Prin amabilitatea d-lui prof. Emil Onea (Focsani) avem posibilitatea sa va oferim cāteva dintre ele. Asteptam rezolvari. Succes!

P019801: Constelatii 

Propusa de Cristian Cadar, elev la Colegiul National Sf. Sava”, Bucuresti.

Enunt:

Īntr-o seara petrecuta la Poiana Pinului”, un informatician admira cerul si compune urmatoarea problema:

Se dau m constelatii cu minimum 3 si maximum n stele fiecare. Se defineste bordura” unei constelatii ca fiind acoperitoarea convexa a stelelor din respectiva constelatie. Fiecare stea este data prin coordonatele sale (x, y) din planul stelar”. De asemenea, se da pozitia Lunii tot prin cele doua coordonate ale sale.

Se cere:

a) sa se afle care constelatii contin Luna īn interiorul bordurii sau pe bordura acestora;

b) sa se determine (daca exista) o constelatie īn a carei bordura se īncadreaza toate celelalte borduri de constelatii.

Limite: 1 <= m <= 100 si 1 <= n <= 1000

Datele de intrare se citesc din fisierul STELE.IN īn urmatorul format:

  • X Y ® coordonatele Lunii
  • m ® nr. de constelatii
  • N1 ® nr. de stele din prima constelatie
  • x11 y11 ® coordonatele primei stele din prima constelatie
  • ......
  • x1n y1n ® coordonatele ultimei stele din prima constelatie
  • ........
  • Nm ® nr. de stele din ultima constelatie
  • xm1 ym1 ® coordonatele primei stele din ultima constelatie
  • ......
  • xmn ymn ® coordonatele ultimei stele din ultima constelatie

Datele de iesire se vor scrie īn fisierul STELE.OUT īn urmatorul format:

  • Linia 1: numarul de constelatii care contin Luna;
  • Linia 2: se vor afisa īn ordine crescatoare numerele de ordine ale constelatiilor care contin Luna; daca pe prima linie s-a afisat '0' atunci aceasta linie va fi goala;
  • Linia 3: se va afisa 'DA' daca exista constelatia ceruta la punctul b) si 'NU' īn caz contrar;
  • Linia 4: se va afisa numarul de ordine al constelatiei gasite la punctul b); daca o astfel de constelatie nu exista, linia va fi lasata goala.

Exemplu:

Pentru fisierul STELE.IN:

3 9 6 7 11
4 1 9 -4 2
8 3 12 17 6
-1 7 5 12 15 10
-1 4 8 10 3 14
0 11 5 9 -2 12
4 11 9 6 -4 10
-2 9 4 5 12 2
-3 6 4 9 4
1 8 10 6 11 11
4 6 12 8 7 13
9 12 6 11 14
3 3 10 8 (eof)

se va genera fisierul STELE.OUT cu urmatorul continut:

3

1 2 4

DA

4

Comentariu la exemplu:

Pentru o mai buna īntelegere a problemei voi preciza si care sunt bordurile fiecarei constelatii:

Bordura constelatiei 1:

(-1,4);(4,6);(4,11);(0,11);(-2,9);(-3,6).

Bordura constelatiei 2:

(3,3);(9,6);(8,10);(5,12);(3,12);(1,9).

Bordura constelatiei 3:

(10,6);(10,8);(12,8);(12,6).

Bordura constelatiei 4:

(-4,2);(12,2);(17,6);(15,10);(11,14);(3,14);

(-2,12);(-4,10).

Timp de implementare: 1 ora si 15 minute

Timp de executare: 2 secunde pe Pentium/133

Observatie (care nu tine de testul problemei):

Atentie la complexitate! Trebuie sa fie O(m*n*log n).

PR019802: LEMMINGS

Problema propusa de Cristian Cibu, elev,  Liceul Teoretic Al. Lahovari”, Rāmnicu Vālcea.

Enunt:

Niste omuleti foarte simpatici trebuie sa scape dintr-un labirint. Ei sunt foarte bine instruiti si stiu cum sa treaca prin fiecare perete care le iese īn fata, dar acest lucru īl īntārzie pe primul cu o unitate de timp, timp īn care ceilalti se apropie de el cu o patratica, existānd pericolul ca doi lemmingsi sa se afle pe aceeasi patratica, ceea ce duce la moartea lor.

Lemmingsii sunt foarte devotati si se sacrifica, ramānānd īn urma si aratānd celorlalti de fiecare data cānd se schimba directia de mers. Astfel ei sunt pierduti (deci nu mai pot iesi din labirint), dar nici nu ocupa patratica īn care se afla, asa ca ceilalti trec lesne pe lānga el.

Lemmingsii intra pe rānd īn labirint, prin coltul din stānga jos, mergānd de la dreapta la stānga si trebuie sa iasa prin coltul opus, mergānd tot de la stānga la dreapta.

Ajutati-i voi sa se salveze cāt mai multi īntr-un timp cāt mai scurt.

Date de intrare:

Fisierul LEMMINGS.IN are structura:

nr ® numarul de lemmingsi

n ® dimensiunea labirintului (patratic)

(L sau C)+i a1 b1;a2 b2;....;an bn

    ® linie/coloana urmat de nr. ei de ordine, coloana/linia de īnceput si de sfārsit īntre care se afla peretele.

......

Date de iesire:

Fisierul LEMMINGS.OUT are structura:

nr    ® numarul de lemmingsi salvati

op1 ® operatia efectuata la primul pas:

  • inainte;
  • spre dreapta;
  • spre stanga;
  • sparge zidul;

op2

...

Exemplu:

lemmings.in:                         lemmings.out:

5                                    3

4                                    inainte

C1 3 4;0 1;4 5                       te

L3 0 1;3 4;4 5                       inainte

L4 4 5                               spre dreapta

                                     inainte

                                     sparge zidul

                                     inainte

                                     inainte

Timp maxim de executare: 5 secunde/test.

P019803: Triunghi

Problema propusa de Edison Nica,  elev, clasa XII, jud Iasi.

Enunt:

Se da urmatorul triunghi:

1:                  1
2:               2      3
3:            4     5      6
4:         7     8      9     10
5:     11    12    13     14     15
6:  16   17    18   19   20   21    22
.......................

Sa se gaseasca trei numere care formeaza un tringhi echilateral a caror suma este X, astfel īncāt doua numere sa se afle pe aceeasi linie iar al treilea sa se gaseasca pe o linie cu indice mai mic.

Limite: X apartine intervalului [1, 1e19].

Date de intrare:

X se citeste din fisierul X.IN.

Date de iesire:

Cele trei numere se vor scrie (īn ordine crescatoare) īn fisierul X.OUT pe o linie, separate printr-un spatiu. Daca exista mai multe solutii, se va scrie numai una.

Timp de executare: 0.5 secunde pe test.

Exemplu:

X.IN      X.OUT

1         NU

20        NU

101       15 41 45

34254     11018 11616 11620

P019804: A FI SAU A NU FI... EXCLUS

Problema propusa de Adrian Manzur, elev, jud. Caras-Severin.

Enunt:

Īn 1999, īntr-o tabara oarecare, īntr-un oras oarecare, la un an dupa incidentele din Poiana Pinului, organizatorii au o mare problema: cum sa-i cazeze pe elevi astfel īncāt incidentele sa nu se repete. Stiind ca daca sunt mai mult de doi bucuresteni īntr-o camera, va fi dezastru, ca fiecare bucurestean are un anumit grad de periculozitate.

Dānduse numarul de paturi dintr-o camera, ajutati-i pe organizatori sa-i cazeze pe elevi.

Datele de intrare:

Fisierul BUC.IN contine pe prima linie:

n - numarul elevilor; 

p - numarul paturilor dintr-o camera; 

b - numarul bucurestenilor;

iar pe urmatoarele b linii, gradul de periculozitate al fiecaruia.

Se mai stie ca numarul elevilor e divizibil cu numarul de paturi dintr-o camera.

Date de iesire:

Daca e posibil sa nu fie scandal, fisierul de iesire BUC.OUT va contine mesajul 'Nu exista probleme', iar īn caz contrar va contine mesajul 'Huston, avem o problema', iar pe linia urmatoare numarul minim de camere devastate.

Timp de executare: MiniM instantaneu

Nota: Camere sunt destule, cu māncarea mai sunt probleme.

Exemplul 1:

BUC.IN            BUC.OUT

10   2   3        Nu exista probleme

30

15

20

Exemplul 2:

BUC.IN            BUC.OUT

9   3   7         Houston, avem o problema

10                1

20

3

18

5

7

35

INDICATII:

  1. Īncercati backtracking, pentru ca sigur se īncadreaza īn timp.
  2. Nu va folositi de gradul de periculozitate.

P019805: Star Trek

Problema propusa de Mihai Scortaru,  elev, Liceul de Informatica, Cluj.

Enunt:

Nava spatiala Enterprise este trimisa pe planeta Alfa Centauri IV pentru a realiza un experiment ciudat. Oamenii de stiinta au creat (prin inginerie genetica) un nou animal numit Macky, dupa numele Dr. McCoy (conducatorul grupului de cercetatori). Acest animal are posibilitatea de a se deplasa cu viteze foarte mari. Ei leaga de urechea animalului un clopotel care suna la fiecare secunda. De fiecare data cānd aude clopotelul, animalul se sperie si īsi dubleaza viteza. Stiind ca la īnceput animalul porneste cu 1 m/s, savantii vor sa calculeze timpul īn care animalul parcurge o anumita distanta (dublarea vitezei are loc instantaneu). Cum domnul Sulu este bolnav, Cpt. James T. Kirk apeleaza la dumneavoastra pentru a calcula perioada de timp.

Date de intrare:

Fisier INPUT.TXT contine distanta d (īn metri).

1<=d<=2.000.000.000

Date de iesire:

Fisierul OUTPUT.TXT va contine perioada t (cu o precizie de 1 miime de secunda).

Timp de executare: 2,457 secunde/test.

P019806: Multiplu

Problema propusa de Andrei Vancea, elev, Liceul de Informatica, Cluj.

Enunt:

Se dau numerele naturale n (2 <= n <= 15000) si b (2 <= b <= 9). Sa se calculeze un multiplu al lui n format doar din cifre de 0 si b.

Date de intrare: fisierul MULTIPLU.IN va ontine n si b.

Date de iesire: fisierul MULTIPLU.OUT va contine multiplul determinat de program.

Exemplu:

MULTIPLU.IN:   40 3

MULTIPLU.OUT:   3000

Timp maxim de executare: 1 secunda.

P019807: Scufita Rosie

Problema propusa de Badiu Nicolae, elev,  Liceul B.P.Hasdeu”, clasa a XI-a.

Enunt:

Īn fiecare duminica, Scufita Rosie trebuie sa plece de acasa ca sa o viziteze pe bunicuta ei. Īnsa pentru a ajunge la ea, Scufita Rosie trebuie sa mearga pe un drum foarte bine ales. Deoarece casa se afla īn padure, fetita a inventat un dispozitiv ingenios cu care poate sa sara peste orice obstacol cu o deviatie constanta pe OX si OY. Astfel, ea poate sari peste gropi, copaci si chiar sa evite eventualii lupi care o pāndesc.

Avānd la dispozitie un laptop performant si harta padurii digitizata, ea realizeaza un program care sa o ajute sa determine un drum sigur catre bunicuta ei. Daca gaseste macar un drum corespunzator, ea īl va alege pe cel mai scurt. Daca nu, va astepta pāna duminica viitoare pentru ca sa primeasca prin satelit o harta ce permite solutii.

Date de intrare: Numele fisierului de intrare se citeste din primul parametru al programului.

Structura fisierului de intrare:

  • pe prima linie se afla numarul de linii si coloane pentru matricea patratica a hartii padurii (1 L n L 600);
  • pe urmatoarele n linii se vor afla cāte n cifre despartite prin spatiu, reprezentānd:
0 - drum fara primejdie

1 - copac

2 - groapa

3..9 - lup

Observatie: Oricare cifra nenula este un obstacol pe care Scufita Rosie nu poate sa cada īn urma unei sarituri.

  • pe urmatoarea linie se afla linia si coloana īn plan a casei bunicutei (0 <= x,y <= n).
  • pe ultima linie se gasesc doua numere ce reprezinta deviatia pe OX si pe OY a dispozitivului care o aduce pe Scufita Rosie īntr-o alta pozitie (0 <= L1, L2<=n).

Observatie: Scufita Rosie poate sa sara numai īn interiorul hartii si numai cu o incrementare sau decrementare īn acelasi timp pe OX cāt si pe OY, folosindu-se si L1 si L2 pe oricare din axe.

Scufita Rosie porneste din coordonata (1, 1) a hartii.

Restrictii: Nu se poate incrementa sau decrementa īn saritura Scufitei Rosii pe ambele axe numai L1 sau L2.

Date de iesire: Fisierul de iesire va fi OUTPUT.TXT, avānd urmatoarea structura:

- pe prima linie se va afisa numarul minim de sarituri pe care le face Scufita Rosie pāna la casa bunicii, daca exista macar o solutie īn conditiile date. Īn caz contrar se va afisa mesajul 'NU ESTE POSIBIL'.

Exemple:

Intrare:                     Intrare:

5                            6

0                            0 0 0 0 0 0 0 0 0 0

1 0 0 1 0 1 0 0 1 0 0

0 1 0 0 0 0 1 0 0 0 0

1 0 0 1 1 1 0 0 1 1 0

0 0 1 0 0 0 0 1 0 0 0

5 4 0 0 0 0 0 0

1 2                          6 3

                             1 3 

OUTPUT.TXT:                  OUTPUT.TXT:

3                            NU ESTE POSIBIL

Observatie: Nu se fac verificari la citire sau scriere.

Timp maxim de executare:

8 secunde/test pentru un calculator 586/133Mhz.

P019808: Giga Voda

Problema propusa de prof. Emanuela Mateescu,

Liceul de Informatica, Iasi.

Enunt:

Īn Tara lui Giga Voda pregatirile sunt īn toi: preafrumoasa-i fiica, Octeta, se va marita cu cel mai luminat pretendent la dalba’i māna.

La poarta īmparatiei au dat buluc o māndra ceata de voinici, dornici sa cāstige māna (si averea) Octetei.

Acela care va reusi īntr-un timp cāt mai scurt sa rezolve problema data de Giga Voda, va primi īn plus si jumatate din īmparatie.

Amar de cel ce nu va izbuti: va fi trimis acasa!!!

Problema consta īn gasirea elei mai lungi īnsiruiri de vorbe, luate dintr-un hrisov, care are cel mult 500 de vorbe, fiecare vorba avānd cel mult 20 slove.

Numele hrisovului este dat de Voda, īn el aparānd pe fiecare rānd cāte o vorba.

O vorba din īnsiruire este imediat urmata de o alta vorba numai daca a doua se obtine din prima, aplicānd una din urmatoarele transformari:

  • īnlocuirea unei slove;
  • inserarea unei slove;
  • stergerea unei slove.

Voinicii puteau sa-si aleaga vorbele numai īn ordinea īn care ele apareau īn hrisov.

Dupa maxim 1 secunda gramaticul Logo trebuie sa primeasca un hrisov cu numele OUTPUT.TXT care are pe primul rānd un numar L, ce arata lungimea sirului de vorbe obtinut din hrisovul dat de Voda.

Pe urmatoarele L rānduri sunt condeiate vorbele gasite de voinici.

Ca sa-i ajute, Voda l-a pus pe Logo sa le dea o pilda.

Hrisovul lui Voda                                  Hrisovul voinicului

                                               (OUTPUT.TXT)

pin                                            6

pic                                            pin

spic                                           pina

pina                                           pana

pana                                           spana

spil                                           span

spana                                          spin

span

pom

spin

P019809: Amnistie

Problema propusa de prof. Emanuela Mateescu,

Liceul de Informatica, Iasi.

Enunt:

Executānd prevederile unei amnistii partiale, un gardian trebuie sa elibereze din cele N (1 < N < 2.0E9) celule ale īnchisorii cel mult MAX (1 < MAX < N) detinuti. Celulele sunt asezate īn rānd, sunt numerotate de la 1 la N si fiecare celula este ocupata de un singur detinut. Regulamentul de amnistiere trebuie respectat īntocmai:

Gardianul trebuie sa deschida toate celulele īnchisorii.

La pasul urmator, gardianul trebuie sa īnchida fiecare a doua celula.

La pasul 3, gardianul trebuie sa ia celulele din 3 īn 3, rasucind cheia īn broasca (cele deschise vor fi īnchise, iar cele īnchise deschise). Aceste operatii trebuie sa se repete, astfel īncāt la pasul i gardianul va lua celulele din i īn i si va rasuci cheia īn broasca lor. Numaratoarea trebuie sa īnceapa īntotdeauna din dreptul primei celule.

Detinutii ale caror celule au ramas deschise dupa efectuarea tuturor acestor operatii vor fi eliberati daca numarul lor nu depaseste MAX, numarul maxim de amnistieri permise. Īn caz contrar, procedeul se reia, gardianul luānd īn considerare la numaratoare īn continuare numai celulele detinutilor selectati la pasul precedent, pāna cānd numarul de detinuti selectati īn urma aplicarii complete a procedeului nu depaseste MAX.

Cunoscānd N numarul de celule din īnchisoare, si MAX numarul maxim de amnistieri permise, determinati celulele norocoase.

Date de intrare: Fisierul de intrare, al carui nume se citeste de la tastatura, contine pe prima linie N, numarul de celule din īnchisoare, iar pe a doua linie MAX, numarul maxim de amnistieri permise.

Date de iesire: Īn fisierul de iesire OUTPUT.TXT vor fi afisate pe linii separate numerele celulelor din care vor fi eliberati detinutii, īn ordinea crescatoare a numerelor lor.

Exemplu:

Pentru fisierul de intrare

20

3

fisierul de iesire OUTPUT.TXT va contine:

1

16

Timp maxim de executare: 0.5 secunde/test.

P019810: Īnmultiri

Problema propusa de prof. Adrian Nita,

Liceul Emanoil Gojdu”, Oradea.

Enunt:

Gigel, elev olimpic, a fost recompensat pentru rezultatele deosebite la informatica cu o tabara la Poiana Lu’ Pin. Īn prima zi, neavānd program clar, a facut o excursie pāna la Manastirea Lu Cio Lan.

Aici probleme mari: parintele chelar era bolnav!!! Avea longint-ita acuta, manifestata prin alergie la numere mari.

Gigel, saritor din fire, s-a oferit sa-l ajute, folosind un calculator de buzunar, care s-a dovedit inutilizabil pentru numerele mari necesare preasfintiei sale.

Cum manastirea primise ca donatie un La’ p(o)top (Pent’ um Contra), Gigel s-a oferit sa-i faca parintelui un program de īnmultiri pentru numere īntregi pozitive cu cel mult 20 de cifre.

Parintele era pretentios: dorea īnmultirile afisate pe ecran, asa cum īnvatase īn clasa a III-a primara.

Exemplu:

123

25

---

615

246

----

3075

Numerele se citesc de la tastatura, separate prin spatiu.

Afisarea rezultatului, pe ecran, se face instantaneu.

P019811: Amnistie

Problema propusa de prof. Dana Lica,  Liceul I. L. Caragiale”, Ploiesti.

Enunt:

Cartierul General al invadatorilor se afla īn orasul p, stabilit initial.

Cunoscāndu-se reteaua de drumuri cu sens unic, ce leaga orasele din Tara Fāsiilor si costurile deplasarii blindatelor pe acestea, sa se gaseasca orasul care poate fi invadat (plecānd din orasul p) pe un numar maxim de trasee (drumuri), toate de cost minim.

Date de intrare: Numele fisierului de intrare se citeste de la tastatura. Acesta va contine datele sub forma urmatoare:

  • Pe prima linie sunt scrise doua numere īntregi: n si p (separate prin spatiu), reprezentānd numarul de orase (n<=100) si respectiv orasul de plecare.
  • Pe urmatoarele linii sunt scrise triplete de numere:  i, j, si c (separate prin spatiu), reprezentānd cāte un drum direct de la i la j de cost c.

Date de iesire: Iesirea va fi īn fisierul OUT.TXT si va contine:

  • Pe prima linie, tripletul de numere: nr, s, min (separate prin spatiu), reprezentānd numarul maxim (nr) de trasee existente īntre p si s, toate de acelasi cost minim (min).
  • Pe urmatoarele nr linii vor fi scrise traseele, pentru fiecare specificāndu-se, īn ordine, orasele strabatute.

Observatie: Īn cazul īn care exista mai multe solutii, se va afisa una singura

Exemplu:

Pentru fisierul de intrare:

7 1

1 2 1

2 3 5

2 6 1

5 3 2

6 5 4

6 7 3

7 4 1

7 3 1

3 4 2

5 1 1

Fisierul de iesire va contine:

2 3 6

1 2 3

1 2 6 7 3

Timp de executare: 1 secunda/test.

P019812: Polinom

Problema propusa de prof. Anastasiu Doru Popescu, Liceul Radu Greceanu”, Slatina.

Enunt:

Se considera n numar natural, n L 10000 si a0, a1, ... , an un sir de numere naturale mai mici sau egale cu 10000.

Notam cu P(x)= an xn + an-1 xn-1 +...+ a1 x + a0

polinomul cu coeficientii dati de termenii sirului.

Pentru x dat, de tip real, determinati:

a) o rearanjare a componentelor sirului astfel īncāt valoarea P(x) a polinomului sa fie minima;

b) valoarea minima obtinuta la punctul a).

Datele de intrare se citesc din fisierul text POL.IN, avānd structura:

x

n

a0

a1

. . . 

an

Datele de iesire se vor scrie īn fisierul text POL.OUT avānd structura:

a0

a1

. . . elementele sirului īn ordinea care realizeaza minimul de la punctul a)

an

min valoarea minima ceruta la punctul b)

Exemplu:

POL.IN:

3

2

1

2

1

POL.OUT:

2 

1

1

14

Timp maxim de executare: 2 secunde pentru fiecare test.

P019813: Posta

Problema propusa de prof. Emanuela Mateescu,

Liceul de Informatica, Iasi.

Enunt:

Un postas trebuie sa treaca zilnic pe toate strazile din cartierul sau. Īn fiecare zi el pleaca de la posta si trebuie sa se īntoarca la posta. Cum īn cartier sunt m strazi (1 < m < 5000), dupa o saptamāna deja īsi pune problema sa īsi optimizeze traseul. Pentru aceasta a īnceput prin a numerota intersectiile, īncepānd cu 1 pentru intersectia īn care se gaseste posta. Pentru a se feri de complicatii, postasul a considerat ca īntr-o intersectie nu trebuie neaparat sa se īntālneasca doua strazi, este suficient ca locul sa fie un capat de strada. Apoi si-a facut o harta, pe care a marcat toate intersectiile si toate strazile. A observat ca īn cartierul sau pot exista strazi distincte care au ambele capete respectiv īn aceleasi intersectii si ca de la posta poate ajunge pe orice strada doreste, trecānd doar pe strazi din cartierul sau. Postasul ar prefera un traseu pe care sa nu fie nevoit sa treaca de doua ori pe o aceeasi strada.

Scrieti un program care sa testeze daca postasul are sanse sa īsi īndeplineasca visul si daca da, sa determine un traseu convenabil.

Datele de intrare se citesc dintr-un fisier al carui nume se citeste de la tastatura.

Pe prima linie se gaseste m, numarul de strazi din cartier.

Pe fiecare din urmatoarele m linii se gasesc cāte doua numere separate prin spatiu, care reprezinta numerele asociate intersectiilor ce reprezinta capetele strazilor din cartier.

Date de iesire: Rezultatele vor fi afisate īn fisierul OUTPUT.TXT.

Prima linie din fisier contine mesajul 'DA', daca problema are solutie, respectiv 'NU', īn caz contrar.

Daca problema are solutie, īn fisierul de iesire vor fi afisate intersectiile īn ordinea īn care sunt parcurse pe un traseu optim (unul īn care fiecare strada este parcursa o singura data), īncepānd cu 1, intersectia de plecare si terminānd, de asemenea, cu 1, fiecare intersectie pe o linie separata.

Exemple:

Intrare:          OUTPUT.TXT
5                 DA
1 4               1
1 2               4
1 3               1
1 4               2
2 3               3
1
Intrare:          OUTPUT.TXT
1 2               NU
1 4
Intrare:          OUTPUT.TXT
1                 DA
1 1               1
1 

Timp maxim de executare: 1 secunda/test.

[cuprins]