Brașov, Str. Bihorului nr.3 cod postal 500209 e-mail:colegiul_mesota@yahoo.com
Telefoane: secretariat 0268/543455 sau 0368/449197; director 0268/543457 ; director adj. 0268/543456 sau 0368/007093 | Contactaţi-ne



search engine by freefind căutare avansată

Subiecte

Olimpiada de Informatică

Clasa a IX-a

Faza judeţeană, 23 martie 2003

 

Problema 1: TEXT

 

Vasile lucrează intens la un editor de texte. Un text este format din unul sau mai multe paragrafe. Orice paragraf se termină cu Enter şi oricare două cuvinte consecutive din acelaşi paragraf sunt separate prin spaţii (unul sau mai multe). În funcţie de modul de setare a paginii, numărul maxim de caractere care încap în pagină pe o linie este unic determinat (Max).

Funcţia pe care Vasile trebuie o implementeze acum este alinierea în pagină a fiecărui paragraf din text la stânga şi la dreapta. Pentru aceasta el va trebui să împartă fiecare paragraf în linii separate de lungime Max (fiecare linie terminată cu Enter). Împărţirea se realizează punând numărul maxim posibil de cuvinte pe fiecare linie, fără împărţirea cuvintelor în silabe. Pentru aliniere stânga-dreapta, el trebuie repartizeze spaţii în mod uniform între cuvintele de pe fiecare linie, astfel încât ultimul caracter de pe linie să fie diferit de spaţiu, iar numărul total de caractere de pe linie să fie egal cu Max. Excepţie face numai ultima linie din paragraf, care rămâne aliniată la stânga (cuvintele fiind separate printr-un singur spaţiu, chiar dacă linia nu este plină).

În general, este puţin probabil ca alinierea să fie realizabilă prin plasarea aceluiaşi număr de spaţii  între oricare două cuvinte consecutive de pe linie. Vasile consideră că este mai elegant ca, dacă între unele cuvinte consecutive trebuie plasat un spaţiu în plus faţă de alte perechi de cuvinte consecutive, acestea să fie plasate la începutul liniei.

 

Cerinţă

Scrieţi un program care să citească lungimea unei linii şi textul dat şi care să alinieze textul la stânga şi la dreapta.

 

Date de intrare

Fişierul de intrare text.in conţine pe prima linie Max, lungimea maximă a unui rând.

Pe următoarele linii este scris textul.

 

Date de ieşire

Fişierul de ieşire text.out conţine textul aliniat stânga-dreapta.

 

Restricţii

§      2<=Max<=1000

§      Lungimea maximă a oricărui cuvânt din text este 25 caractere şi nu depăşeşte Max.

§      Lungimea unui paragraf nu depăşeşte 1000 de caractere.

§      Soluţia este unică.

 

Exemple

text.in

text.out

Explicaţie

20

Vasile are multe bomboane bune.

Vasile are multe bomboane bune.

Pe prima linie au fost plasate câte 3 spaţii între cuvintele consecutive.

 

text.in

text.out

Explicaţie

20

Ana are mere.

Ion are multe pere galbene?

Ana are mere.

Ion  are  multe pere galbene?

Între Ion şi are există 2 spaţii, între are şi multe- 2 spaţii, iar între multe şi pere- 1 spaţiu.

Observaţi că paragraful Ana are mere. (care are lungimea mai mică decât 20) a rămas aliniat la stânga, iar ultima linie din fiecare paragraf rămâne aliniată la stânga, cuvintele consecutive fiind separate printr-un singur spaţiu.

Timp maxim de executare: 1 secundă/test.


Olimpiada de Informatică

Clasa a IX-a

Faza judeţeană, 23 martie 2003

 

Problema 2: NUMERE

 

Gigel este un mare pasionat al cifrelor. Orice moment liber şi-l petrece jucându-se cu numere. Jucându-se astfel, într-o zi a scris pe hârtie 10 numere distincte de câte două cifre şi a observat că printre acestea există două submulţimi disjuncte de sumă egală. Desigur, Gigel a crezut că este o întâmplare şi a scris alte 10 numere distincte de câte două cifre şi spre surpriza lui, după un timp a găsit din nou două submulţimi disjuncte de sumă egală.

 

Cerinţă

Date 10 numere distincte de câte două cifre, determinaţi numărul de perechi de submulţimi disjuncte de sumă egală care se pot forma cu numere din cele date, precum şi una dintre aceste perechi pentru care suma numerelor din fiecare dintre cele două submulţimi este maximă.

 

Date de intrare

Fişierul de intrare numere.in conţine pe prima linie 10 numere naturale distincte separate prin câte un spaţiu.

x1 x2 ...x10

 

Date de ieşire

Fişierul de ieşire numere.out conţine trei linii. Pe prima linie se află numărul de perechi de submulţimi de sumă egală, precum şi suma maximă obţinută, separate printr-un spaţiu. Pe linia a doua se află elementele primei submulţimi, iar pe linia a treia se află elementele celei de a doua submulţimi, separate prin câte un spaţiu.

NrSol Smax             NrSol - numărul de perechi; Smax - suma maximă

x1 ... xk                 elementele primei submulţimi

y1 ... yp                 elementele celei de a doua submulţimi

 

Restricţii şi precizări

§         10 £ xi, yi £ 99, pentru 1 £ i £ 10

§         1 £ k, p £ 9

§         Ordinea submulţimilor în perechi nu contează.

§         Perechea de submulţimi determinată nu este obligatoriu unică.

 

Exemplu

numere.in

numere.out

Semnificaţie

60 49 86 78 23 97 69 71 32 10

130 276

78 97 69 32

60 49 86 71 10

130 de soluţii; suma maximă este 276, s-au folosit 9 din cele 10 numere prima submulţime are 4 elemente, a doua are 5 elemente

 

Timp maxim de executare/test: 1 secundă

 


Olimpiada de Informatică

Clasa a X-a

Faza judeţeană, 23 martie 2003

 

Problema 1: SPIRALA

 

Se consideră un automat de criptare format dintr-un tablou cu n linii şi n coloane, tablou ce conţine toate numerele de la 1 la n2 aşezate ”şerpuit” pe linii, de la prima la ultima linie, pe liniile impare pornind de la stânga către dreapta, iar pe cele pare de la dreapta către stânga (ca în figura alăturată).

Text Box: 1	2	3	4
14	13	12	5
15	16	9	8
10	11	6	7

Numim ”amestecare“ operaţia de desfăşurare în spirală a valorilor din tablou în ordinea indicată de săgeţi şi de reaşezare a acestora în acelaşi tablou, ”şerpuit” pe linii ca şi în cazul precedent.

De exemplu, desfăşurarea tabloului conduce la şirul: 1 2 3 4 5 12 13 14 15 16 9 8 7 6 11 10, iar reaşezarea acestuia în tablou conduce la obţinerea unui nou tablou reprezentat în cea de-a doua figură alăturată.

Text Box: 1	2	3	4
6	7	8	5
11	10	15	14
16	9	12	13

După orice operaţie de amestecare se poate relua procedeul, efectuând o nouă amestecare. S-a observat un fapt interesant: că după un număr de amestecări, unele valori ajung din nou în poziţia iniţială (pe care o aveau în tabloul de pornire). De exemplu, după două amestecări, tabloul de 4x4 conţine 9 dintre elementele sale în exact aceeaşi poziţie în care se aflau iniţial (vezi elemente marcate din figură).

 

Cerinţă

Pentru n şi k citite, scrieţi un program care să determine numărul minim de amestecări ale unui tablou de n linii necesar pentru a ajunge la un tablou cu exact k elemente aflate din nou în poziţia iniţială.

 

Date de intrare

Fişierul de intrare spirala.in conţine pe prima linie cele două numere n şi k despărţite printr-un spaţiu.

 

Date de ieşire

Fişierul de ieşire spirala.out conţine o singură linie pe care se află numărul de amestecări determinat.

 

Restricţii şi precizări

§      3<=N<=50

§      Datele de intrare sunt alese astfel încât numărul minim de amestecări necesare să nu depăşească 2*109

§      La încheierea programului nu se va solicita apăsarea unei taste

 

Exemple

 

spirala.in

spirala.out

spirala.in

spirala.out

4 9

2

6 36

330

 

Timp maxim de executare/test: 1 secundă


Olimpiada de Informatică

Clasa a X-a

Faza judeţeană, 23 martie 2003

 

Problema 2: TAXE

 

Într-o ţară în care corupţia este în floare şi economia la pământ, pentru a obţine toate aprobările necesare în scopul demarării unei afaceri, investitorul trebuie să treacă prin mai multe camere ale unei clădiri în care se află birouri.

Clădirea are un singur nivel în care birourile sunt lipite unele de altele formând un caroiaj pătrat de dimensiune nxn. Pentru a facilita accesul în birouri, toate camerele vecine au uşi între ele. În fiecare birou se află un funcţionar care pretinde o taxă de trecere prin cameră (taxă ce poate fi, pentru unele camere, egală cu 0). Investitorul intră încrezător prin colţul din stânga-sus al clădirii (cum se vede de sus planul clădirii) şi doreşte ajungă în colţul opus al clădirii, unde este ieşirea, plătind o taxă totală cât mai mică.

 

Cerinţă

Ştiind că el are în buzunar S euro şi că fiecare funcţionar îi ia taxa de cum intră în birou, se cere să se determine dacă el poate primi aprobările necesare şi, în caz afirmativ, care este suma maximă de bani care îi rămâne în buzunar la ieşirea din clădire.

 

Date de intrare

Fişierul de intrare taxe.in conţine pe prima linie cele două numere S şi n despărţite printr-un spaţiu, iar pe următoarele n linii câte n numere separate prin spaţii ce reprezintă taxele cerute de funcţionarii din fiecare birou.

 

Date de ieşire

Fişierul de ieşire taxe.out conţine o singură linie pe care se află numărul maxim de euro care îi rămân în buzunar sau valoarea -1 dacă investitorului nu-i ajung banii pentru a obţine aprobarea.

 

Restricţii şi precizări

§      3<=N<=100

§      1<=S<=10000

§      Valorile reprezentând taxele cerute de funcţionarii din birouri sunt numere naturale, o taxă nedepăşind valoarea de 200 de euro.

§      La încheierea programului nu se va solicita apăsarea unei taste

 

Exemple

 

taxe.in

taxe.out

10 3

1 2 5

1 3 1

0 8 1

3

 

Timp maxim de executare/test: 1 secundă


Olimpiada de Informatică

Clasele a XI-a şi a XII-a

Faza judeţeană, 23 martie 2003

Problema 1: COMPUS

 

La ultima expediţie pe Marte a fost descoperit un compus organic necunoscut. Acest compus este acum studiat în laboratoarele NASA. Cercetătorii au descoperit că acest compus este constituit numai din atomi de hidrigen (H), ixigen (I) şi carbin (C) şi are masa moleculară M.

Se ştie că regulile de formare a compuşilor organici pe Marte sunt următoarele:

-        un atom de carbin se poate lega de oricare dintre atomii de C, H şi I cu oricâte dintre cele 4 legături pe care le are (astfel, în combinaţia H-C=C primul atom de carbin se leagă prin două legături de alt atom de carbin şi cu o legătură de alt atom de hidrigen)

-        un atom de hidrigen se poate lega numai de un atom de carbin cu singura legătură pe care o posedă

-        un atom de ixigen se poate lega numai de atomi de carbin cu cele două legături pe care le posedă

-        un compus este un ansamblu cu proprietatea că toţi atomii de carbin sunt legaţi conex între ei şi nu există vreun atom cu una sau mai multe legături libere (nelegate de un alt atom).

Combinaţia H-C=C nu este un compus deoarece atomii de carbin mai au legături libere.

Cercetătorii au în vedere studiul categoriilor de compuşi, făcând distincţie între doi compuşi numai dacă aceştia diferă prin numărul de atomi de carbin, de ixigen sau de hidrigen.

 

Cerinţă

Scrieţi un program care să determine câţi compuşi distincţi formaţi din atomi de carbin, hidrigen şi ixigen (cel puţin unul din fiecare) şi care au masa moleculară M există.

 

Date de intrare

Fişierul de intrare compus.in conţine pe prima linie masa moleculară a compusului.

 

Date de ieşire

Fişierul de ieşire compus.out conţine o singură linie pe care se află numărul de compuşi determinat.

 

Restricţii şi precizări

§      30<=M<=1000000

§      Masa atomului de H este 1, masa atomului de C este 5, iar masa atomului de I este 3. Masa moleculară a unui compus este egală cu suma maselor atomilor din care este constituit compusul respectiv.

§      Ordinea în care sunt “utilizate” legăturile unui atom nu contează. De asemenea, nici ordinea atomilor sau legăturile interne dintre ei nu contează atâta timp cât respectă regulile de formare enunţate.

 

Exemple

Există un singur compus cu masa moleculară 10: cel format cu un atom de C, doi atomi de H si un atom de I (5+2*1+3=10), compus ale cărui legături pot fi reprezentate astfel:

 H-C=I

   |

   H


Se pot obţine 3 compuşi cu masa moleculară 40: (5C, 6H, 3I), (6C, 4H, 2I), (7C, 2H, 1I):

Reprezentarea cu legături a oricăruia dintre compuşi nu este unică. Orice altă combinaţie corespunzătoare aceluiaşi triplet nu se consideră un compus distinct.

 

Exemple

compus.in

compus.out

compus.in

compus.out

40

3

125

28

 

Timp maxim de executare/test: 1 secundă


Olimpiada de Informatică

Clasele a XI-a şi a XII-a

Faza judeţeană, 23 martie 2003

 

Problema 2: ZMEU

 

Un zmeu cu n capete călătoreşte din poveste în poveste, iar în poveştile tradiţionale întâlneşte câte un Făt Frumos care-l mai scurtează de câteva capete, în timp ce în poveştile moderne salvează omenirea mâncând în timp record, cu toate capetele lui, insecte ucigaşe apărute prin mutaţii genetice. Într-o seară, el îşi planifică o seccesiune de poveşti cărora le dea viaţă. El ştie p poveşti numerotate de la 1 la p, durata fiecăreia şi numărul de capete pe care le pierde în fiecare poveste. Mai ştie o mulţime de k perechi de poveşti, semnificând faptul că a doua poveste din pereche nu poate fi spusă după prima poveste din pereche.

 

Cerinţă

Ştiind că trebuie înceapă cu povestea 1 şi să încheie succesiunea cu povestea p, ajutaţi bietul zmeu să aleagă una sau mai multe poveşti intermediare astfel încât durata totală să fie minimă şi să rămână cu cel puţin un cap la sfârşitul tuturor poveştilor.

 

Date de intrare

Fişierul de intrare zmeu.in conţine pe prima linie numerele n, p şi k despărţite prin câte un spaţiu. Pe fiecare din următoarele p linii se află câte o pereche de numere di şi ci (separate prin câte un spaţiu) ce reprezintă durata şi numărul de capete tăiate pentru fiecare poveste. Iar pe ultimele k linii se află câte o pereche de numere pi şi pj (separate prin câte un spaţiu) ce semnifică faptul că povestea pj nu poate fi spusă după povestea pi.

 

Date de ieşire

Fişierul de ieşire zmeu.out conţine o singură linie pe care se află un număr natural reprezentând durata (minimă) a succesiunii de poveşti sau valoarea -1 dacă nu există o astfel de succesiune.

 

Restricţii şi precizări

§      2=N<=500

§      1<=P<=200

§      1<=k<=30000

§      Valorile reprezentând duratele şi numărul de capete sunt numere naturale (duratele fiind strict pozitive), nedepăşind valoarea 10.

 

Exemple

 

zmeu.in

zmeu.out

10 4 2

2 6

4 0

1 3

3 3

3 2

4 3

9

 

Timp maxim de executare/test: 1 secundă

 



Contact
Brașov, Str. Bihorului nr.3, cod postal 500209, e-mail: colegiul_mesota@yahoo.com

Telefoane
secretariat: 0268 543455 / 0368 449197, director: 0268 543457, director adj.: 0268 543456 sau 0368/007093