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.

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.

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.

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ă.

APM.IN APM.OUT

4 1 4 5

1 2 2 2 3 3

3 4 4

3 1 2

2

5

3

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ă.

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.

Rezultatul se va scrie în fişierul FOREVER.OUT. Acesta este un număr natural şi reprezintă numărul de apeluri ale procedurii Incrementează.

FOREVER.IN FOREVER.OUT

2 8 36

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.

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.

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ă.

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).

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.

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.

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.

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

23

3 1 7

4 6 16

ˇ 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.

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.

Î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.

În fişierul text AXA.OUT se vor scrie coordonatele punctelor reprezentate pe axă, despărţite prin câte un spaţiu.

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ă.

AXA.IN

2 4 6 2 5 7 9 9 11 3

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.

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.

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.

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

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

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).

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.

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.

COPII.IN COPII.OUT

2 2 6 8

P069908: Pătrate

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.

Pe prima linie a fişierului PATRAT.IN se află numărul n.

Î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.

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:

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.

Fişierul PUNCTE.IN are structura:

n

x1 y1

x2 y2

...

xn yn

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.

PUNCTE.IN

5

1 8

0 5

3 0

0 7

5 0

PUNCTE.OUT

4.0000000 4.0000000 4.1231056

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ă.

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.

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.

GERMANA.IN

8 4 7

iese

maro

vale

urma

eseu

rosu

oaie

aron

GERMANA.OUT

16

maroaieseurmaron sau ieseurmaroaieseu

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.

Î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.

Î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.

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

5

1 8

2 8

3 8

7 8

7 6

4 6

5 6

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

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.

Î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.

NUMERE.IN

153

5

2 3 5 4 7

NUMERE.OUT

DA

4

1 1 0 1 1

150

4

2 3 4 2

NU

[cuprins]