Īncercati-va puterile!
Probleme propuse pentru REZOLVAREP019801: ConstelatiiPropusa 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:
Datele de iesire se vor scrie īn fisierul STELE.OUT īn urmatorul format:
Exemplu: Pentru fisierul STELE.IN:
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: LEMMINGSProblema 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:
...... Date de iesire: Fisierul LEMMINGS.OUT are structura:
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: TriunghiProblema propusa de Edison Nica, elev, clasa XII, jud Iasi. Enunt: Se da urmatorul triunghi: 1: 12: 2 33: 4 5 64: 7 8 9 105: 11 12 13 14 156: 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 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... EXCLUSProblema 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:
P019805: Star TrekProblema 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: MultipluProblema 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 RosieProblema 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:
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.
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 VodaProblema 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 dalbai 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:
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: AmnistieProblema 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: ĪnmultiriProblema 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: AmnistieProblema 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:
Date de iesire: Iesirea va fi īn fisierul OUT.TXT si va contine:
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: PolinomProblema 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:
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: PostaProblema 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.TXT5 DA1 4 11 2 41 3 11 4 22 3 31Intrare: OUTPUT.TXT1 2 NU1 4Intrare: OUTPUT.TXT1 DA1 1 11 Timp maxim de executare: 1 secunda/test. |