Încercați-vă puterile!

 

PROBLEME propuse pentru rezolvare

Aș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 ever

Prof. 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 culmi

Că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 cetatea

Cristian 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 OX

prof. 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ționale

Radu 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: Puncte

prof. 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țial

Lect. 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: Numere

prof. 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]