Încercați-vă puterile!
PROBLEME propuse pentru rezolvareAșa cum veți afla din enunțul problemei "Apărați cetatea", în mijlocul acestei veri, la Mediaș, s-au adunat cei 17 componenți ai Lotului Național și într-o competiție "dură" s-au întrecut pentru a câștiga dreptul de a participa la Balcaniada de Informatică, respectiv la Olimpiada de Informatică a Europei Centrale organizate la Ioannina (Grecia), respectiv la Brno (Cehia). P069901: A. P. M.Prof. Dana Lica, Colegiul Național "I.L. Caragiale", Ploiești Se consideră un arbore având costuri atașate pe muchii și un șir de numere naturale mai mici decât 30000. Să se adauge arborelui un număr maxim de muchii având costuri din numerele date, astfel încât graful obținut să aibă ca arbore parțial de cost minim arborele inițial.
Date de intrare
Pe prima linie a fișierului text APM.IN se află numărul natural n reprezentând numărul nodurilor din arbore (nŁ100). Pe următoarele n-1 linii se găsesc câte trei numere naturale despărțite printr-un spațiu, sub forma i j c, având semnificația: muchia de la i la j are costul c Pe următoarele linii se află șirul de numere dat, câte un element pe o linie.
Date de ieșire
Pe fiecare linie a fișierului APM.OUT se vor scrie trei numere i j c, având semnificația: muchie adăugată între nodurile i și j de cost c. Cele trei numere se vor despărți prin câte un spațiu.
Observații
1. Fiecare element din șir va reprezenta costul unei singure muchii adăugate. 2. Elementele șirului nu sunt neapărat distincte. 3. Între oricare două noduri din graf va exista cel mult o muchie. 4. În cazul în care nu se poate atașa nici o muchie, în fișierul de ieșire se va scrie 0. 5. În cazul în care problema admite mai multe soluții, în fișier se va scrie una singură.
Exemplu
APM.IN APM.OUT 4 1 4 5 1 2 2 2 3 3 3 4 4 3 1 2 2 5 3
P069902: For everProf. Roxana Tâmplaru, Liceul de Informatică, Craiova Se consideră următoarea secvență de algoritm, scrisă în pseudocod: pentru v1=1,k execută pentru v2=v1,k execută pentru v3=v2,k execută ... pentru vn=vn-1,k execută Incrementează; Să se determine numărul de apeluri ale procedurii Incrementează.
Date de intrare
Fișierul de intrare FOREVER.IN conține două numere naturale n (1ŁnŁ5000) și k (1ŁkŁ5000) despărțite printr-un singur spațiu, unde: - n reprezintă numărul structurilor pentru; - k reprezintă valoarea finală a tuturor structurilor pentru.
Date de ieșire
Rezultatul se va scrie în fișierul FOREVER.OUT. Acesta este un număr natural și reprezintă numărul de apeluri ale procedurii Incrementează.
Exemplu
FOREVER.IN FOREVER.OUT 2 8 36
P069903: Spre culmiCătălin Frâncu, student MIT, Boston, SUA Se dă un vector cu NŁ10000 numere întregi, cuprinse între 1 și 50000. Să se partiționeze acest vector în cât mai puține subșiruri strict crescătoare.
Date de intrare
Fișierul CRESC.IN conține două linii. Prima linie conține numărul N, iar a doua conține cele N numere, despărțite prin spații.
Date de ieșire
Fișierul CRESC.OUT va conține pe prima linie numărul minim K de subșiruri în care se poate partiționa vectorul. Pe fiecare din următoarele K linii se va descrie câte unul din aceste subșiruri, precizând indicii în vector ai elementelor subșirului, în ordine crescătoare, despărțiți prin spații. Ordinea de afișare a subșirurilor este indiferentă.
Exemplu
CRESC.IN CRESC.OUT 7 2 9 2 4 7 10 11 8 2 3 4 7 1 5 6 Semnificația ieșirii este: vectorul poate fi partiționat în două subșiruri. Un subșir conține primul, al cincilea și al șaselea element din vector (deci 9-10-11), iar celălalt conține al doilea, al treilea, al patrulea și ultimul element (deci 2-4-7-8).
P069904: Apărați cetateaCristian Cadar, student Universitatea Politehnică, București Vechiul principat al Transilvaniei este din nou atacat de trupele otomane. De data aceasta, ținta trupelor turcești este Cetatea Mediașului, vestită pentru capetele luminate pe care le adăpostește. Armata otomană a reușit să intre în Transilvania prin cetatea Brașovului și acum se îndreaptă spre Mediaș. Sarcina voastră, gânditori ai Mediașului, este de a împiedica cucerirea acestui oraș-cetate. Pentru a realiza acest lucru, beneficiați de o hartă a țării, hartă care descrie legăturile dintre orașe. Pentru fiecare drum existent între două orașe, cunoașteți numărul minim de oșteni care trebuie amplasați pe acel drum, pentru a înfrânge turcii care încearcă să treacă pe acolo. Deoarece armata română este, ca de obicei, redusă, scopul vostru este de a apăra cetatea Mediașului folosind un număr cât mai mic de oșteni.
De exemplu, pentru harta din figura următoare, numărul minim necesar de oșteni este 23, punând 7 oșteni pe drumul de la Sighișoara la Mediaș și 16 oșteni pe drumul de la Hunedoara la Cluj.
Pentru simplificare, vom considera orașele numerotate de la 1 la n, n fiind numărul total de orașe. Orașul 1 va fi considerat Mediașul, iar orașul n Brașovul.
Date de intrare
Pe prima linie a fișierului MEDIAS.IN este scris numărul total de orașe, iar pe următoarele linii, până la sfârșitul fișierului sunt scrise câte trei numere i j c, având semnificația: pentru a păzi drumul de la i la j sunt necesari cel puțin c oșteni.
Date de ieșire
Rezultatele se vor scrie în fișierul MEDIAS.OUT. Pe prima linie va fi scris numărul minim de soldați necesari, iar următoarele linii, până la sfârșitul fișierului, vor conține câte trei numere naturale i j c, reprezentând faptul că pe drumul de la i la j au fost amplasați c oșteni.
Exemplu
MEDIAS.IN (fișierul corespunde figurii de mai sus) 7 3 1 7 6 1 47 7 2 12 7 2 20 2 4 11 7 3 15 5 3 20 7 4 10 4 2 21 4 6 16 6 5 23
MEDIAS.OUT
23 3 1 7 4 6 16
Observații
· Drumurile sunt orientate. · Între două orașe pot exista mai multe drumuri în ambele direcții. · Numărul total de drumuri este cel mult 10000. · Numărul total de orașe este cel mult 5000. · Numărul de soldați necesar blocării unui drum este cel mult 65000. · Timpul de execuție diferă de la un test la altul (în funcție de complexitatea testului) și se situează în intervalul 1-9 secunde.
P069905: Axa OXprof. Emil Onea, inspector Inspectoratul Județean Vrancea Se consideră axa OX cu originea în punctul de coordonată 0. Pe această axă nu pot fi reprezentate decât puncte având coordonate naturale mai mici decât 20000. Cunoscându-se distanțele dintre oricare două puncte reprezentate pe axă se cere determinarea coordonatelor acestora. Lista distanțelor cuprinde cel mult 1000000 de valori.
Date de intrare
În fișierul text AXA.IN distanțele dintre punctele reprezentate pe axă sunt scrise pe o linie, despărțite prin câte un spațiu.
Date de ieșire
În fișierul text AXA.OUT se vor scrie coordonatele punctelor reprezentate pe axă, despărțite prin câte un spațiu.
Observații
1. Originea reprezintă un punct de pe axă. 2. Punctele reprezentate pe axă sunt distincte (au coordonate diferite). 3. Problema va admite întotdeauna soluție. 4. În cazul în care există mai multe soluții se va afișa una singură.
Exemplu
AXA.IN 2 4 6 2 5 7 9 9 11 3
AXA.OUT
0 2 6 9 11
P069906: Oferte promoționaleRadu Lupșa, asistent Universitatea "Babeș-Bolyai", Cluj Un lanț de magazine organizează o acțiune promoțională, oferind gratuit anumite produse clienților aflați în magazin la anumite ore.
Un client dorește să obțină un profit cât mai mare de pe urma acestor oferte. În acest scop el pleacă de acasă la momentul 0, îndreptându-se spre primul magazin ales; odată ajuns, așteaptă ora ofertei, ia gratuit produsul oferit, după care pleacă mai departe spre următorul magazin, și așa mai departe. Bineînțeles, drumul de la un magazin la altul îi ia un timp strict pozitiv, iar deplasarea costă, reducându-i din profit. La finalul zilei, adică nu mai târziu de momentul 57600, clientul nostru trebuie să ajungă înapoi acasă. Se cere o planificare a vizitei magazinelor care să maximizeze profitul.
Date de intrare
Datele de intrare se citesc din fișierul de intrare PROMOTII.IN, în care: · pe prima linie sunt scrise două numere naturale N (NŁ 100) și M (MŁ5000) reprezentând numărul de magazine, respectiv numărul total de oferte (separate printr-un spațiu); · pe fiecare din următoarele M linii, sunt scrise câte trei numere: numărul de ordine al magazinului, momentul la care are loc oferta promoțională și valoarea produsului oferit; nu există două oferte în același magazin la aceeași oră; · pe următoarele N+1 linii, este scrisă matricea timpilor necesari deplasării. În linia i coloana j se găsește timpul necesar deplasării de la magazinul i la magazinul j; magazinul cu numărul N+1 reprezentând casa clientului nostru; diagonala matricei conține zerouri; · pe următoarele N+1 linii se află matricea costurilor deplasărilor, cu aceleași convenții ca mai sus.
Date de ieșire
Ieșirea se va face în fișierul PROMOTII.OUT în următorul format: pe prima linie se va afișa profitul obținut de client, iar în continuare pentru fiecare obiect promoțional primit se va scrie o linie conținând două numere: numărul magazinului urmat de momentul la care are loc oferta.
Exemplu
PROMOTII.IN PROMOTII.OUT 2 5 52 1 2 10 1 2 2 3 20 1 4 1 4 25 1 5 1 5 10 2 10 2 10 10 0 2 2 2 0 3 1 1 0 0 1 1 1 0 1 1 1 0
P069907: La grădinițăLect. univ Clara Ionescu, Universitatea "Babeș-Bolyai", Cluj Cu ocazia sfârșitului anului școlar la grădiniță se pregătește un spectacol. Copiii sunt aliniați în două grupuri și așezați față în față. Cei care fac parte din același grup, se țin de mână:
Urmează o acțiune pe care o numim formarea unui singur lanț de copii și care se va realiza astfel încât oricare doi copii, aflați în două grupuri diferite, se pot prinde de mână cu condiția să nu își "încrucișeze" mâinile; în figura 1 este vizualizată o posibilitate pentru exemplul dat.
figura 1
figura 2
Fie 1, 2, , m copiii din primul grup și m+1, m+2, , m+n copiii din al doilea grup. Vom da în continuare două semnificații noțiunii de lanț corect. 1) Pentru orice 1 Ł i < j Ł m, i trebuie să apară în noul lanț înaintea lui j. O condiție similară se pune și pentru al doilea grup de copii. 2) Condiția 1) se relaxează, în sensul că în momentul în care unul dintre cele două grupuri de copii s-a încheiat, elementele rămase din al doilea grup pot fi considerate și în ordine inversă (figura 2). De asemenea, lanțul poate să înceapă cu copii aparținând inițial unuia din grupuri, așezați în ordine inversă (figura 3). Cele două relaxări se pot combina (figura 4).
figura 3
figura 4
Scrieți un program care stabilește numărul lanțurilor corecte care se pot forma respectând regula 1), apoi numărul lanțurilor corecte care se pot forma respectând regula 2).
Date de intrare
Numerele întregi n (1<nŁ20) și m (1<mŁ20), reprezentând numărul copiilor din cele două grupuri se vor citi din fișierul de intrare de tip text COPII.IN.
Date de ieșire
Numărul lanțurilor corecte care se pot forma respectând regula 1) și numărul lanțurilor corecte care se pot forma respectând regula 2) se vor scrie în fișierul COPII.OUT.
Exemplu
COPII.IN COPII.OUT 2 2 6 8
P069908: Pătrate
prof. Doru PopescuAnastasiu, Liceul "Radu Greceanu", Slatina
Se dă un număr întreg n (6ŁnŁ100). Să se determine o modalitate de partiționare a unui pătrat în n pătrate.
Date de intrare
Pe prima linie a fișierului PATRAT.IN se află numărul n.
Date de ieșire
În fișierul PATRAT.OUT se va scrie un tablou pătratic T ale cărui elemente sunt numere naturale din mulțimea M=1,2,...,n. Fiecare element xÎM este folosit în T pentru reprezentarea unui singur pătrat din partiție. Liniile tabloului T se vor scrie în fișierul de ieșire pe rânduri separate. Pe un rând al fișierului PATRAT.OUT elementele lui T sunt separate printr-un spațiu.
Exemplu
PATRAT.IN PATRAT.OUT 10 1 1 1 1 4 4 7 8 1 1 1 1 4 4 9 10 1 1 1 1 5 5 6 6 1 1 1 1 5 5 6 6 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 2 2 2 2 3 3 3 3 Exemplul codifică partiția:
P069909: Puncteprof. Doru PopescuAnastasiu, Liceul "Radu Greceanu", Slatina Se dau n (3ŁnŁ5000) puncte în plan astfel încât oricare trei sunt necoliniare. Punctele sunt date prin coordonatele lor carteziene (x1,y1); (x2,y2); ...; (xn,yn), numere întregi din intervalul [-30000, 30000]. Se cere să se determine un cerc (centrul și raza sa) care să treacă prin cel puțin trei din cele n puncte și să nu conțină în interiorul său nici un alt punct din cele n puncte date.
Date de intrare
Fișierul PUNCTE.IN are structura: n x1 y1 x2 y2 ... xn yn
Date de ieșire
Fișierul PUNCTE.OUT va avea structura: a b r
unde a b r (numere reale aproximate la șapte zecimale) sunt coordonatele carteziene ale centrului cercului, respectiv raza.
Exemplu
PUNCTE.IN 5 1 8 0 5 3 0 0 7 5 0
PUNCTE.OUT 4.0000000 4.0000000 4.1231056
P069910: La ora de germanăOvidiu Gheorghioiu, student MIT, Boston, SUA Se știe că nemții au o adevărată pasiune pentru formarea de noi cuvinte prin contopirea unora existente, uneori rezultând cuvinte foarte lungi, ca de exemplu Sehenswurdigkeiten (= lucru demn de văzut, monument). Profesoara de germană, care pregătește un referat pe această temă, v-a rugat pe voi, lotul de informatică să o ajutați să "prepare" cuvinte noi. Ea v-a dat o listă de cuvinte (care, mai mult sau mai puțin întâmplător, au aceeași lungime), și v-a rugat să îi găsiți un cuvânt nou, cât mai scurt posibil, care să conțină K cuvinte (nu neapărat diferite) din lista respectivă.
Date de intrare
Pe prima linie a fișierului GERMANA.IN se găsesc trei numere naturale: - N (1ŁNŁ100) reprezintă numărul de cuvinte din listă, - L (1ŁLŁ255), reprezintă lungimea comună a cuvintelor, - K (1ŁKŁ255), numărul de poziții din cuvântul rezultat pe care trebuie să apară cuvinte din listă. Pe următoarele N linii se găsesc N cuvinte distincte de lungime exact L.
Date de ieșire
Fișierul GERMANA.OUT va conține pe prima linie lungimea minimă obținută a cuvântului solicitat, iar pe a doua se va afișa cuvântul.
Exemplu
GERMANA.IN 8 4 7 iese maro vale urma eseu rosu oaie aron
GERMANA.OUT 16 maroaieseurmaron sau ieseurmaroaieseu
P069911: Arbore parțialLect. univ Clara Ionescu, Universitatea "Babeș-Bolyai", Cluj Se consideră un graf neorientat conex având n noduri. Să se determine unul din arborii parțiali ai grafului dat, care are număr maxim de frunze.
Exemplu
Date de intrare
În fișierul ARBORE.IN pe prima linie este scris un număr natural n (3ŁnŁ2000) reprezentând numărul nodurilor. Pe următoarele n linii urmează descrierea grafului, care va avea cel mult 10000 de muchii și este conex. Primul număr de pe cea de a j+1-a linie precizează numărul de noduri k, adiacente cu nodul j. După acest număr urmează k numere naturale xk{1,n}\{j} reprezentând nodurile adiacente nodului j. Datele scrise pe aceeași linie sunt despărțite prin câte un spațiu.
Date de ieșire
În fișierul ARBORE.OUT, pe prima linie se va scrie numărul maxim de frunze. Pe următoarele n-1 linii se vor scrie perechi de numere naturale (despărțite printr-un spațiu) reprezentând muchiile arborelui având acest număr maxim de frunze. În cazul în care există mai multe soluții, se va preciza una singură. Ordinea în care se afișează muchiile și ordinea în care se precizează vârfurile muchiilor este oarecare.
Exemplu
ARBORE.IN 8 3 2 3 8 4 1 5 6 8 4 1 4 7 8 4 3 5 6 7 3 2 4 6 4 2 4 5 7 4 3 4 6 8 4 1 2 3 7
ARBORE.OUT
5 1 8 2 8 3 8 7 8 7 6 4 6 5 6
P069912: Numereprof. Doru PopescuAnastasiu, Liceul "Radu Greceanu", Slatina Se dau n numere naturale x1, x2, ..., xn din intervalul [1,109]. Să se determine (dacă există), pentru un număr natural m din intervalul [1,109] un șir de numere naturale a0, a1, ..., ak având proprietățile:
1) k<n 2) m=a0+a1x1+a2x1x2+...+akx1x2...xk 3) ai<xi+1, 0ŁiŁk 4) akč0
Date de intrare
Pe prima linie a fișierului NUMERE.IN este scris numărul m, (1ŁmŁ109) reprezentând numărul pentru care se cere descompunerea precizată în enunț. Pe următoarea linie este scris numărul natural n (1ŁnŁ1000) reprezentând numărul de numere date. Pe cea de a treia linie se află scrise cele n numere x1, x2, ..., xn, despărțite prin câte un spațiu.
Date de ieșire
În cazul în care există soluție, pe prima linie a fișierului NUMERE.OUT se va scrie cuvântul DA, în caz contrar se va scrie NU. În caz afirmativ pe a doua linie se va scrie un număr natural k, având semnificația din enunț. Pe cea de a treia linie se vor scrie cele k+1 numere a0, a1, ..., ak, despărțite prin câte un spațiu.
Exemple
NUMERE.IN 153 5 2 3 5 4 7
NUMERE.OUT DA 4 1 1 0 1 1
NUMERE.IN
150 4 2 3 4 2
NUMERE.OUT
NU [cuprins] |