CLASA a XI a  si a XII a

Subiectul 1. (100p)

Suma (ACM site)

   Pentru n numar natural nenul, sa se gaseasca o combinatie de semne + si - (cu alte cuvinte un sir x=(x[1], x[2], x[3], . ,x[k]), unde elemntul x[i] poate fi +1 sau -1, 1<=i<=k) si un numar k natural nenul astfel incat n=x[1]*1²+x[2]*2²+.+x[k]*k².

            Datele de intrare se citesc din fisierul text SUMA.IN, ce contine pe prima linie numarul n.

          Datele de iesire vor fi depuse in fisierul text SUMA.OUT. Pe prima linie se va scrie combinatia de k semne (+ sau -) corespunzatoare lui n dat in fisierul de intrare, fara spatii intre ele sau alti separatori.

          Exemple

SUMA.IN                                                      SUMA.OUT

5                                                                 ++--+

Subiectul 2. (100p)

Casa în livada

            Un fermier doreste sa construiasca o casa mare de forma patrata pe terenul de forma patrata a livezii sale. Deoarece nu doreste sa taie nici un pom, vrea sa gaseasca o locatie în care sa construiasca pe un teren fara pomi. În acest scop terenul a fost împartit în N x N parcele.

            Scrieti un program care sa determine cea mai mare cas 757u2013h 59; patrata care poate fi construita în livada fara a taia nici un pom. Laturile casei trebuie sa fie paralele cu axa orizontala, respectiv cea verticala.

 Intrarea se face din fisierul Casa.in care contine :

-          pe prima linie doua numere întregi N si T, separate printr-un spatiu, reprezentând numarul parcelelor de pe o latura, respectiv numarul parcelelor pe care cresc pomi.

-          pe liniile 2, . , T + 1 câte doua numere intregi din intervalul [ 1, N] reprezentând linia si coloana unei parcele pe care se afla pom.

Iesirea se face pe ecran , si va contine lungimea maxima a unei laturi a casei.

Exemplu: Pentru fisierul Casa.in

8         3

2         2

2         6

6         3

Se va tipari pe ecran valoarea 5

Subiectul 2. (100p)

Jocul silabelor

In fisierul Cuvinte.in pe prima linie este un numar natural N, iar pe urmatoarele N linii se gasesc cuvinte (pe fiecare linie se gaseste un cuvânt despartit în silabe cu ajutorul caracterului '-'). Cuvintele contin numai majuscule. Spunem ca doua cuvinte rimeaza daca au cel putin doua litere de la sfârsit identice.  Se cere

a)     Cuvintele sa fie distribuite in grupe de cuvinte care rimeaza.

b)     Sa se afiseze frazele ce contin numar maxim de silabe si pentru care cuvântul aflat pe pozitia I rimeaza cu cuvântul aflat pe pozitia I+2, iar cuvintele care rimeaza vor fi ordonate alfabetic. O fraza este formata din minim 3 cuvinte.

Rezultatele vor fi afisate în fisierul Fraze.out sub forma

Grupa 1 .....

Grupa 2 .....

.........

Grupa k ....

Fraza 1  ....

Fraza 2 ....

.........

Exemplu

Cuvinte.in                                                          Fraze.out                      

9                                              Grupa 1: TALISMAN GERMAN UMAN

TA-LIS-MAN                              Grupa 2: NICI

NICI                                         Grupa 3: GENIUL

GE-NIUL                                    Grupa 4: MACAR DOAR

MA-CAR                                              Grupa 5: LACAT

GER-MAN                                  Grupa 6: UN

LA-CAT                                              Fraza 1: GERMAN DOAR TALISMAN MACAR UMAN

U-MAN

DOAR

UN

Barem pentru clasa a IX-a

TOTAL  100 Puncte

TOTAL 100 Puncte

TOTAL 200 Puncte pe lucrare

CLASELE XI-XII

Problema 1 (Urgenta)

Autoritatile dintr-o zona de munte intentioneaza sa stabileasca un plan de urgenta, pentru a reactiona mai efici­ent la frecventele calamitati naturale din zona. În acest scop au identificat N puncte de interes strategic si le-au numerotat distinct de la 1 la N. Punctele de interes strategic sunt conectate prin M cai de acces având prioritati în functie de importanta. Între oricare doua puncte de interes strategic exista cel mult o cale de acces ce poate fi parcursa în ambele sensuri si cel putin un drum (format din una sau mai multe cai de acces) ce le conecteaza.

În cazul unei calamitati unele cai de acces pot fi temporar întrerupte si astfel între anumite puncte de interes nu mai exista legatura. Ca urmare pot rezulta mai multe grupuri de puncte în asa fel încât între oricare doua puncte din acelasi grup sa existe macar un drum si între oricare doua puncte din grupuri diferite sa nu existe drum.

Autoritatile estimeaza gravitatea unei calamitati ca fiind suma prioritatilor cailor de acces distruse de aceasta si doresc sa determine un scenariu de gravitate maxima, în care punctele de interes strategic sa fie împartite într-un numar de K grupuri.

Date de intrare

Fisierul de intrare URGENTA.IN are urmatorul format:
N M K
i₁ j₁ p₁   - între punctele i₁ si j₁ exista o cale de acces de prioritate p₁
i₂ j₂ p₂   - între punctele i₂ si j₂ exista o cale de acces de prioritate p_2
...
i_M j_M p_M            - între punctele i_M si j_M exista o cale de acces de prioritate p_M

Date de iesire

Fisierul de iesire URGENTA.OUT va avea urmatorul format:
gravmax - gravitatea maxima
C         - numarul de cai de acces întrerupte de calamitate
k₁ h₁     - între punctele k₁ si h₁ a fost întrerupta calea de acces
k₂ h₂     - între punctele k₂ si h₂ a fost întrerupta calea de acces
_...
k_C h_C    - între punctele k_C si h_C a fost întrerupta calea de acces

Restrictii si precizari
0<N<256
N-2<M<32385
0<K<N+1
Prioritatile cailor de acces sunt întregi strict pozitivi mai mici decât 256.
Un grup de puncte poate contine între 1 si N puncte inclusiv.
Daca exista mai multe solutii, programul va determina una singura.

Exemplu

URGENTA.IN	URGENTA.OUT
7 11 4 1 2 1 1 3 2 1 7 3 2 4 3 3 4 2 3 5 1 3 6 1 3 7 5 4 5 5 5 6 4 6 7 3	27 8 1 3 1 7 2 4 3 4 3 7 4 5 5 6 6 7

Timp maxim de executare:  1 secunda / test

Olimpiada Judeteana de Informatica
9 martie 2002, ora 9⁰⁰

                                                         CLASELE XI-XII

Problema 2 (Nunta)

În fata palatului Printesei Mofturoase se afla N petitori asezati la coada, unul în spatele celuilalt. Fiecare poarta sub mantie un numar de pietre pretioase pe care doreste sa le ofere printesei ca dar de nunta. Pentru a nu semana vrajba în rândurile lor, printesa a decis sa-i determine ca N-1 dintre ei sa renunte în chip pasnic, petitorul ramas devenind alesul printesei (indiferent de numarul de pietre pretioase detinute de acesta).

Doi petitori vecini la coada se pot întelege între ei astfel: cel care are mai putine pietre pretioase pleaca de la coada primind de la celalalt un numar de pietre astfel încât sa plece acasa cu un numar dublu de pietre fata de câte avea. Daca doi petitori au acelasi numar de pietre, unul din ei (nu conteaza care) pleaca luând toate pietrele vecinului sau.

Un petitor se poate întelege la un moment dat cu unul singur dintre cei doi vecini ai sai. Dupa plecarea unui petitor, toti cei din spatele lui avanseaza.

De exemplu: pentru configuratia alaturata de 5 petitori, un sir posibil de negocieri care conduc la reducerea cozii la un singur petitor este: se înteleg vecinii 4 cu 5 si pleaca 4, se înteleg apoi 1 cu 2 si pleaca 1, se înteleg apoi 3 cu 2 si pleaca 3, se înteleg  2 cu 5 si pleaca 5. Astfel petitorul 2 câstiga mâna preafrumoasei printese, oferindu-i 0 pietre pretioase ca dar de nunta.

Fie P numarul de pietre pretioase pe care le are petitorul care va deveni alesul printesei. Se cer valorile distincte ale lui P la care se poate ajunge prin toate succesiunile de negocieri posibile.

Fisierul de intrare nunta.in contine:

- pe prima linie  numarul de petitori: n  (1 £ n £ 50).

- pe a doua linie, n numere naturale din intervalul [0, 20], reprezentând numarul de pietre pretioase pe care le detin petitorii, în ordinea în care stau la coada.

Fisierul de iesire nunta.out va contine:

- pe prima linie  numarul m de valori distincte ce pot fi obtinute

- pe a doua linie cele m valori ordonate crescator, reprezentând valorile care se pot obtine.       

Exemplu:

nunta.in

4

1 4 2 6

nunta.out

3

1 3 5

Timp maxim de executare:  1 secunda / test

Clasele a XI-a si a XII-a

Faza judeteana, 23 martie 2003

Problema 1: COMPUS

La ultima expeditie pe Marte a fost descoperit un compus organic necunoscut. Acest compus este acum studiat în laboratoarele NASA. Cercetatorii au descoperit ca acest compus este constituit numai din atomi de hidrigen (H), ixigen (I) si carbin (C) si are masa moleculara M.

Se stie ca regulile de formare a compusilor organici pe Marte sunt urmatoarele:

-        un atom de carbin se poate lega de oricare dintre atomii de C, H si I cu oricâte dintre cele 4 legaturi pe care le are (astfel, în combinatia H-C=C primul atom de carbin se leaga prin doua legaturi de alt atom de carbin si cu o legatura de alt atom de hidrigen)

-        un atom de hidrigen se poate lega numai de un atom de carbin cu singura legatura pe care o poseda

-        un atom de ixigen se poate lega numai de atomi de carbin cu cele doua legaturi pe care le poseda

-        un compus este un ansamblu cu proprietatea ca toti atomii de carbin sunt legati conex între ei si nu exista vreun atom cu una sau mai multe legaturi libere (nelegate de un alt atom).

Combinatia H-C=C nu este un compus deoarece atomii de carbin mai au legaturi libere.

Cercetatorii au în vedere studiul categoriilor de compusi, facând distinctie între doi compusi numai daca acestia difera prin numarul de atomi de carbin, de ixigen sau de hidrigen.

Cerinta

Scrieti un program care sa determine câti compusi distincti formati din atomi de carbin, hidrigen si ixigen (cel putin unul din fiecare) si care au masa moleculara M exista.

Date de intrare

Fisierul de intrare compus.in contine pe prima linie masa moleculara a compusului.

Date de iesire

Fisierul de iesire compus.out contine o singura linie pe care se afla numarul de compusi determinat.

Restrictii si precizari

§      30<=M<=1000000

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

§      Ordinea în care sunt "utilizate" legaturile unui atom nu conteaza. De asemenea, nici ordinea atomilor sau legaturile interne dintre ei nu conteaza atâta timp cât respecta regulile de formare enuntate.

Exemple

Exista un singur compus cu masa moleculara 10: cel format cu un atom de C, doi atomi de H si un atom de I (5+2*1+3=10), compus ale carui legaturi pot fi reprezentate astfel:

 H-C=I

   |

   H

Se pot obtine 3 compusi cu masa moleculara 40: (5C, 6H, 3I), (6C, 4H, 2I), (7C, 2H, 1I):

Reprezentarea cu legaturi a oricaruia dintre compusi nu este unica. Orice alta combinatie corespunzatoare aceluiasi triplet nu se considera un compus distinct.

Exemple

compus.in	compus.out	compus.in	compus.out
40	3	125	28

Timp maxim de executare/test: 1 sec.

Olimpiada Nationala de Informatica

Faza pe Judet

Clasa a-XI-a si a-XII-a

PARCURGERE EULER

Fie un arbore general cu radacina (un nod poate avea oricati fii). Arborele are N noduri numerotate de la 1 la N. O parcurgere Euler a acestui arbore se face astfel:

- Se tipareste radacina arborelui;

- Pentru fiecare dintre fiii radacinii:

     - Se parcurge dupa aceeasi metoda subarborele care are drept radacina  fiul respectiv;

     - Se tipareste radacina.

De exemplu, sa consideram arborele cu 7 noduri:

             5

           /   \

         3       7

       / | \       |

  6   1   2    4

Atunci parcurgerea Euler este: 5 3 6 3 1 3 2 3 5 7 4 7 5.

Problema cere ca, dandu-se un numar N si o succesiune de numere, sa se spuna daca succesiunea reprezinta o parcurgere Euler corecta a unui arbore cu N noduri si, in caz afirmativ, sa se reconstituie arborele.

DATE DE INTRARE: Fisierul text EULER.IN contine datele:

N                              // 1<=N<=1000

numar numar ... numar          // O succesiune de numere cuprinse intre

                                                 1 si N. Numarul de numere este necunoscut.

DATELE DE IESIRE: Fisierul text EULER.OUT va contine pe prima linie unul din cuvintele DA sau NU, dupa cum exista sau nu un arbore a carui parcurgere Euler sa fie tocmai succesiunea de numere data. Daca raspunsul este afirmativ, pe urmatoarele N-1 linii se vor afisa muchiile arborelui, in ordinea in care le exploreaza parcurgerea Euler. Pentru fiecare muchie se vor tipari nodul parinte si nodul fiu (in aceasta ordine), separate printr-un spatiu.

EXEMPLE:

EULER.IN                        EULER.OUT

7                                           DA

5 3 6 3 1 3 2 3 5 7 4 7 5       5 3

                                             3 6

                                 3 1

                                             3 2

                                 5 7

                                             7 4

EULER.IN                        EULER.OUT

3                                         NU

1 2 3 1 2 3 1 2 3 1 2 3

TIMP DE RULARE: O secunda.

INSPECTORATUL  sCOLAR  JUDEŢEAN  GALAŢI

OLIMPIADA  DE  INFORMATICĂ

CLASA  a X-a

24 februarie 2001

            In "Muntii  Izolati" , de-a lungul albiei Râului Sec , se afla n gospodarii . Datorita terenului deosebit  de accidentat  cele  n case s-au construit una lânga alta , pe Poteca Pietruita . In ziua de 9 MARTIE , BABA DOCHIA  si-a propus sa faca 2*n+1 vizite . Datorita ninsorii    abundente , BABA DOCHIA poate merge numai pe Poteca Pietruita , trecând de la o casa la alta .(NU POTE TRECE PE LANGA O CASA FARA A O VIZITA !)

De exemplu , pentru n=3 :

                                                        Poteca  pietruita

RÂUL SEC

 1)   Generati toate  modurile în care BABA DOCHIA poate face cele 2*n+1  vizite astfel încât sa porneasca de la o anumita gospodarie , sa nu treaca pe lânga o casa fara a vizita proprietarii acesteia si sa se întoarca la punctul de plecare . Gospodaria de unde pleaca Baba Dochia se citeste din fisierul de intrare. Baba poate vizita de mai multe ori aceeasi casa !  De-a lungul râului sec exista cel putin 2 gospodarii .

2)             Afisati numarul de solutii ale problemei.

Datele de intrare se citesc din fisierul text "Gospodar.In"

Datele de  iesire se  vor scrie în fisierul "Baba.Out"

Formatul fisierului Gopodar.In:

N                                                                 numarul de gospodarii

<nume-gospodarie de plecare>                           gospodaria de unde pleaca BABA DOCHIA

<nume-gopodarie 1>

<nume-gopodarie 2>

<nume-gopodarie 3>            cele n gospodarii

.........

<nume-gopodarie n>

      EXEMPLU :

GOSPODAR.IN

3

Casa cu Plopi

Casa cu Plopi

Casa darapanata

Casa fara gard

BABA.OUT

Casa cu Plopi; Casa darapanata; Casa cu Plopi; Casa darapanata; Casa cu Plopi; Casa darapanata; Casa cu Plopi;

Casa cu Plopi; Casa darapanata; Casa cu Plopi; Casa darapanata; Casa fara gard; Casa darapanata; Casa cu Plopi;

Casa cu Plopi; Casa darapanata; Casa fara gard; Casa darapanata; Casa cu Plopi; Casa darapanata; Casa cu Plopi;

Casa cu Plopi; Casa darapanata; Casa fara gard; Casa darapanata; Casa fara gard; Casa darapanata; Casa cu Plopi;

4

                                                                                                                              Problema propusa de

                                                                                                                              Prof. Balacea Georgeta

NOTĂ

1)    Timp efectiv de lucru - 2 ore;

2)    Se acorda 10 puncte din oficiu;

3)    Datele de intrare sunt corecte;

4)    Timp maxim de executie/test = 1 sec.

OLIMPIADA DE INFORMATICA  faza judeteana

CLASA a XII-a

24 februarie 2001

O suprafata oceanica este identificata de o retea punctiforma de dimensiune MxN formata din elemente cu valoarea 0 (pentru apa) sau 1 (pentru pamant). De pe planeta Marte soseste o nava spatiala cu extraterestri interesati de experimente pe creierele elevilor de clasa a XII-a.

Nava are trei picioare in forma de disc: P1 de raza R1, P2 de raza R2, si P3 de raza R3 . Centrele celor trei discuri sunt dispuse in varfurile unui triunghi dreptunghic isoscel de cateta C. Centrul lui P1 este dispus in varful unghiului drept. O insula este o portiune de pamant inconjurata de ape sau de limitele retelei.

A)     Identificati  numarul de insule

B)      Stiind ca pot fi maxim 26 de insule in retea, afisati harta suprafetei oceanice, identificand fiecare insula cu o litera mare a  alfabetului englez.( pentru fiecare insula se inlocuieste elementul 1 cu litera asociata  insulei).

C)      Identificati toate posibilitatile de aterizare ale navei asociind fiecarui picior litera corespunzatoare insulei pe care se poate aseza in intregime piciorul respectiv

Datele de intrare se preiau din fisierul EXTRA.IN care are urmatoarea structura:

  Pe prima linie a fisierului de intrare sunt valorile M si N,  dimensiunile retelei.

Urmatoarele M linii contin cate N caractere (0 sau 1) reprezentand  reteaua punctiforma ce identifica suprafata oceanica.

Urmatoarea linie contine patru numere reale pozitive reprezentand razele celor trei picioare ale navei ( R1, R2, R3) si lungimea catetei C.

Datele de iesire se scriu in fisierul EXTRA.OUT in urmatorul format

Prima linie: numarul de insule

Urmatoarele M linii contin cate N caractere formate din cifra 0 sau literele mari ale alfabetului englez , reprezentand harta suprafetei oceanice.

In continuare variantele gasite la punctul (C) al problemei vor fi afisate cate una pe fiecare linie in formatul urmator:

P1-I1  P2-I2  P3-I3     unde I1,I2,I3 reprezinta o litera mare a alfabetului englez corespunzatoare insulei pe care se aseaza piciorul respectiv.

Daca la punctul (C) nu exista solutie se va scrie "NU POATE ATERIZA"

                                                                                                                Problema propusa de 

                                                                                                                Prof. Georgeta Balacea

                                                                                                                Prof. Daniel Maxin

Exemplu

EXTRA.IN

10 13

0000000000000

0000000000000

0000000000000

0000011000000

0000011000000

0000000000000

1111000001111

1111000001111

1111000001111

1111000001111

1 1 1 7

EXTRA.OUT

3

0000000000000

0000000000000

0000000000000

00000AA000000

00000AA000000

0000000000000

BBBB00000CCCC

BBBB00000CCCC

BBBB00000CCCC

BBBB00000CCCC

P1-A  P2-B  P3-C

Nota:

·         Timp efectiv de lucru doua ore.

·         Se acorda 10 puncte din oficiu.

·         Timp  maxim de executie 5 secunde pe test

·         Se va evalua numai fisierul executabil

OLIMPIADA JUDETEANA DE INFORMATICA

CLASA A XI-a

FEBRUARIE 2001

             Fie o expresie de calcul propozitional care foloseste operatorul unar negare (notat cu !) si operatorii binari disjunctie (notat cu +) si conjunctie (notat cu *).  Operanzii expresiei sunt reprezentati prin nume de variabile formate dintr-o singura litera mica a alfabetului englez. Expresia poate contine paranteze rotunde, care modifica prioritatea operatorilor. Sunt respectate in evaluarea unei expresii proprietatile cunoscute: comutativitatea adunarii, comutativitatea inmultirii, asociativitatea adunarii, asociativitatea inmultirii, distributivitatea inmultirii fata de adunare. Fie o expresie (a carei forma este considerata corecta).

a.       Se cere frecventa nv de aparitie a celui mai folosit operator in expresia data.

b.      Pentru valori ale variabilelor propozitionale (enumerate in ordine lexicografica) se cere valoarea x a expresiei date.

c.       Pentru un numar dat, m, sa se evalueze expresia data pentru toate cazurile in care exista m variabile propozitionale consecutive in ordine lexicografica, avand valoarea de adevar 1. Se cere numarul y de valori 1 ale expresiei evaluate obtinute pentru cazurile.

Fisierul de intrare P11.in contine blocuri corespunzatoare mai multor expresii. Blocurile sunt delimitate de un rand gol. Un bloc va contine urmatoarele randuri:

-         pe primul rand se da expresia de calcul propozitional.

-         pe al doilea rand se afla valorile binare ale variabilelor din expresia data anterior, fara delimitatori.

-         pe al treilea rand se gaseste valoarea m.

Fisierul de iesire P11.out contine randuri corespunzatoare blocurilor din fisierul de  intrare. Un rand contine valorile nv, x si y, determinate la punctele a., b. si c., delimitate de cate un spatiu.

Exemplu:

Fisierul P11.in

!b*(a+b+c)

100

2

d+!a*c

001

2

Fisierul P11.out

2 1 0

1 0 1

 

 

NOTA

timp de lucru: 2 ore;

timp maxim de rulare: 1 minut;

Problema 1 - Decodificarea mesajelor Morse

Enunt:

Alfabetul Morse codifica fiecare litera a alfabetului englez printr-un sir de puncte si linii, astfel:

A    . -

B    - . . .

C    - . - .

D    - . .

E    .

F    . . - .

G    - - .

H    . . . .

I    . .

J    . - - -

K    - . -

L    . - . .

M    - -

N    - .

O     - - -

P    . - - .

Q    - - . -

R    . - .

S    . . .

T    -

U    . . -

V    . . . -

W    . - -

X    - . . -

Y    - . - -

Z    - - . .

Mesajul codificat Morse este reprezentat printr-un sir de biti, dupa regulile:

1)   . este codificat prin 1

      - este codificat prin 111

     Oricare doua coduri consecutive sunt separate printr-un 0.

     Exemplu: M este reprezentat prin 1110111, iar B prin 111010101

2) Literele interioare apartinând aceluiasi cuvânt sunt separate prin 000 (3 de 0).

3) Cuvintele sunt separate prin 00000 (5 de 0).

Exemplu: ALB ROSU se codifica prin:

1011100010111010100011101010100000101110100011101110111000101010001010111

Intrare: Fisierul text 'MORSE.IN' contine una sau mai multe linii. Fiecare linie contine o succesiune de 0 si 1. Primul 1 de pe linie poate fi precedat de o serie de 0 nesemnificativi. Fiecare linie se termina cu 7 de 0. Daca un caracter de pe o linie nu respecta una din regulile anterioare, linia se decodifica pâna la aparitia primei erori, dupa care se scrie '?'.

Iesire: Fisierul text 'MORSE.OUT' ce contine textul decodificat.

Cerinta: Fiind dat un text în cod Morse în fisierul text 'MORSE.IN', sa se scrie un program care scrie textul decodificat cu majuscule în fisierul text de iesire 'MORSE.OUT'. Cuvintele vor fi separate printr-un singur spatiu, fara semne de punctuatie.

Restrictii: Lungimea maxima a unei linii din fisierul de intrare este 240.

Exemplu:

Daca fisierul 'MORSE.IN' este:

000000010111000111010100000111010111010000000

00110000000

000101110000000

0000000010111000111010100000111010111010000000

111010100010001010111010001010000000Atunci fisierul de iesire 'MORSE.OUT' va fi:

AD C

?

A

AD C

Problema 2 - Fazan

Într-un fisier se gaseste un text, structurat pe mai multe linii, format din cuvinte scrise cu litere mici ale alfabetului englez, separate prin spatii sau/si marcaje de sfârsit de linie.

Cerinta

Scrieti un program care sa determine cea mai lunga însiruire de cuvinte din text, în ordinea în care acestea apar în textul dat, construita astfel încât pentru oricare doua cuvinte consecutive ultima litera din primul cuvânt sa coincida cu prima litera din urmatorul cuvânt.

Intrare

Numele fisierului de intrare este IN.TXT.

Iesire

Fisierul de iesire se numeste OUT.TXT. Pe prima linie în fisierul de iesire se afla LgMax, numarul de cuvinte din însiruirea determinata.

Pe urmatoarele LgMax linii cuvintele din însiruirea de lungime maxima gasita, câte un cuvânt pe linie.

Restrictii

-        Orice cuvânt are maxim 15 litere.

-        În text exista maxim 1000 de cuvinte.

Exemplu

Pentru fisierul de intrare IN.TXT:

in universul nostru dens si mic

ursii    mananca si nu fac nimic

Fisierul de iesire OUT.TXT poate contine:

3

in

nostru

ursii

Timp maxim de executie: 1 secunda/test

Punctaj: 45 puncte.

Problema 1 - scolari mici, galagie mare

            Elevii claselor a V-a de la scoala de Informatica "Grigore C. Moisil" au câstigat concursul "Un joc pe calculator - o sansa în plus în viitor" si vor pleca toti în excursie de studiu la Disneyland. Trebuie organizate doua grupuri de elevi însotiti de câte un profesor (de informatica, evident). Dupa cum se stie, micutii sunt galagiosi si se cearta pentru tot felul de lucruri mai mult sau mai putin posibile. Pentru a beneficia de o calatorie linistita, profesorii vor încerca sa separe perechile de copii între care au observat ca izbucnesc des conflicte si sa formeze doua grupuri cât mai echilibrate numeric.

Cerinta:

            Sa se scrie un program care sa verifice daca este posibila împartirea copiilor în doua grupuri în care sa nu apara nici un conflict. Daca exista solutie, sa se determine o varianta de repartizare astfel încât sa rezulte doua grupuri cât mai echilibrate numeric (diferenta în modul dintre numarul de copii din primul grup si  numarul de copii din cel de-al doilea grup sa fie minima).

Observatii: Copii sunt identificati prin numere distincte de la 1 la N.

                     Profesorii însotitori nu fac parte din solutie.

Date de intrare:

            Datele de intrare se citesc din fisierul text  ELEVI.IN cu urmatoarea structura

            N  K              // N- numarul de elevi si K-numarul de perechi de copii care pot fi în conflict

            X1 Y1                        // perechile de certareti, cu semnificatia Xi si Yi pot fi în conflict

            X2 Y2

            ...

            Xk Yk

Datele de iesire:

            Datele de iesire se vor scrie in fisierul text ELEVI.OUT cu urmatoarea structura: pe prima linie va apare, scris cu majuscule, raspunsul DA (daca pot fi repartizati în doua grupuri) sau NU (altfel). Daca pe prima linie se afla mesajul DA atunci fisierul de iesire contine pe liniile urmatoare:

             Min                               // diferenta minima în modul

            i1 i2 i3 ... ip     //  copiii repartizati în primul grup (separati prin câte un spatiu)

            j1 j2 j3 ... jq     //  copiii repartizati în al doilea grup (separati prin câte un spatiu)

                                                    

Restrictii:       2<=N<=200

                         p+q=N

                       

Exemple

Exemplul 1		Exemplul 2
ELEVI.IN	ELEVI.OUT	ELEVI.IN	ELEVI.OUT
4 2 1 2 4 2	DA 0 1 4 2 3	4 3 1 2 2 4 1 4	NU

 Timp de executie: 1 secunda/test

 Punctaj: 45 puncte

 Observatie: Datele de intrare sunt corecte.

Judete

Teritoriul unei tari este împartit în judete. Pe harta frontiera tarii si granita administrativa a fiecarui judet reprezinta cîte un poligon definit prin coordonatele (x_i, y_i) ale vîrfurilor sale. Se presupune ca vîrfurile de poligoane sînt numerotate direct prin 1, 2, 3, ..., n, iar coordonatele lor sînt numere reale (vezi desenul). În interiorul oricarui judet nu exista alte judete.

Un virus de calculator a distrus partial informatia despre granitele administrative, lasînd intacte urmatoarele date:

- numarul n si coordonatele (x_i, y_i) ale tuturor vîrfurilor de poligoane;

- numarul de segmente m care formeaza laturi de poligoane si informatia despre extremitatile fiecarui segment.

Scrieti un program care determina numarul de judete d si vîrfurile fiecarui poligon ce reprezinta o granita administrativa de judet.

Date de intrare.

Fisierul text JUDET.IN contine pe prima linie numerele n, m separate prin spatii. Urmatoarele n linii contin cîte doua numere reale separate prin spatiu. Linia contine coordonatele x_i, y_i  ale vîrfului i. Urmatoarele m linii contin cîte doua numere de vîrfuri a si b separate prin spatiu, cu semnificatia:  vîrfurile a si b sînt extremitatile unui segment.

Date de iesire.

Fisierul text JUDET.OUT va contine  linii. Pe prima linie se scrie numarul de judete d. Pe fiecare din urmatoarele linii se scriu numerele de vîrfuri ale poligonului ce reprezinta granita administrativa a unui judet.

Exemplu.

JUDET.IN          JUDET.OUT

11 14 2 8 5 7 1 6 6 6 3 5 4 5 5 4 1 3 7 3 4 2 2 1 1 2 2 4 4 7 10 11 10 9 8 6 6 10 7 9 5 2 1 3 3 5 3 8 8 11 6 7

4 1 2 5 3 2 4 7 6 8 3 5 6 10 11 8 6 7 9 10

Restrictii. . Timpul de executie nu va depasi 3 secunde. Fisierul sursa se va numi JUDET.PAS, JUDET.C sau JUDET.CPP. Aceasta problema se va nota cu 110 puncte.

Laserul

Se considera o placa dreptunghiulara cu dimensiunile m´n, unde m si n sînt numere naturale. Aceasta placa trebuie taiata în m×n placi mai mici, fiecare bucata avînd forma unui patrat cu dimensiunile 1´1 (vezi desenul). Întrucît placa este neomogena, pentru fiecare bucata se indica densitatea d_xy, unde x, y sînt coordonatele coltului stînga-jos al patratului respectiv.

Pentru operatiile de taiere se foloseste un strung cu laser. Fiecare operatie de taiere include:

- fixarea unei placi pe masa de taiere;

- stabilirea puterii laserului în functie de densitatea materialului de taiat;

- o singura deplasare a laserului de-a lungul oricarei drepte paralele cu una din axele de coordonate;

- scoaterea celor doua placi de pe masa de taiere.

Costul unei operatii de taiere se determina dupa formula , unde d_max este densitatea maxima a bucatilor 1´1 peste marginile carora trece raza laserului. Evident, costul total T  poate fi determinat adunînd costurile individuale c ale tuturor operatiilor de taiere necesare pentru obtinerea bucatilor 1´1.

Scrieti un program care calculeaza costul minim T.

Date de intrare.

Fisierul text LASER.IN contine pe prima linie numerele m si n separate prin spatiu. Urmatoarele m linii ale fisierului contin cîte n numere naturale d_xy separate prin spatiu.

Date de iesire.

Fisierul text LASER.OUT contine pe o singura linie numarul natural T.

Exemplu.

LASER.IN       LASER.OUT

3 5 1 1 1 1 5 1 7 1 1 1 1 1 1 6 1		52

Restrictii. . Timpul de executie nu va depasi 3 secunde. Fisierul sursa va avea denumirea LASER.PAS, LASER.C, LASER.CPP. Aceasta problema se va nota cu 110 de puncte.

CLASA a X a

Problema 1 (100 puncte)

Drum cu semafoare

Un sofer amator trebuie sã ajungã la o orã prestabilitã într-un anumit punct al orasului. Circulatia fiind reglementatã de recent instalatele semafoare, al cãror ciclu de functionare este cunoscut soferului nostru, acesta doreste sã determine la ce orã trebuie sã plece de acasã pentru a ajunge la timp la destinatie.

Orasul are N intersectii, numerotate de la 1 la N. Fiecare stradã este identificatã prin numerele intersectiilor pe care le leagã. În fiecare intersectie sunt instalate mai multe semafoare, câte unul pentru fiecare conexiune posibilã. Astfel, fiecare semafor este identificat printr-un triplet: semaforul (i, j, k) reglementând accesul de pe strada (i, j) cãtre strada (j, k). Punctul de plecare este intersectia 1, iar punctul de sosire este intersectia N. Din intersectia 1 se poate pleca în orice moment pe oricare din strãzile ce pãrãsesc intersectia. Dacã soferul ajunge într-o intersectie si semaforul crespunzãtor directiei în care vrea sã plece este rosu, atunci el va astepta trecerea pe verde. În intersectia N se poate ajunge oricând, dar cel târziu la momentul prestabilit.

Intrarea

Datele se citesc din fisierul semafor.in având urmãtorul format:

·        Prima linie contine patru numere naturale (separate prin spatii): N, M, P si T reprezentând numãrul de intersectii, numãrul de strãzi (considerate în sens unic), numãrul de semafoare si respectiv momentul sosirii la destinatie (în secunde).

·        Urmãtoarele M linii descriu strãzile si contin câte trei numere naturale (separate prin spatii): i, j si t, unde t reprezintã timpul (în secunde) necesar deplasãrii pe strada directã de la intersectia i la intersectia j.

·        Urmãtoarele P linii descriu semafoarele si contin câte 6 numere naturale: i, j, k, r, v, t cu urmãtoarea semnificatie: semaforul este instalat în intersectia j si reglementeazã plecarea spre k a vehiculelor venite dinspre i; el este rosu timp de r secunde, apoi verde timp de v secunde (dupã care functionarea se repetã periodic); prima trecere de pe rosu pe verde are loc la momentul t.

Limite: N£500, M£5000, P£10000; restul numerelor sunt mai mici su egale cu 32000.

Iesirea

În fisierul semafor.out se vor scrie:

·        Pe prima linie, momentul cel mai târziu al plecãrii

·        Pe a doua linie, sirul intersectiilor parcurse (1 si N inclusiv)

CLASA a XI a  si a XII a

Problema 2. (100 puncte)

PROBLEMA CUBURILOR (100 puncte)

            La un examen psihologic, un concurent este supus urmatoarei probe. Are la dispozitie doua rânduri de cuburi. Pe fiecare rând e dispus un anumit numar de cuburi (<=100), fiecare cub având fetele colorate cu o anumita culoare (toate fetele fiind colorate cu aceeasi culoare). La un moment dat concurentul poate face  urmatoarea operatie: din oricare rând de cuburi, poate elimina un cub, fara însa a modifica ordinea acestora. Pentru a trece proba, concurentului  i se cere, daca e posibil, sa elimine un numar minim de cuburi astfel încât  cele doua rânduri de cuburi sa ramâna identice (ca numar de cuburi, si ca ordine a culorilor cuburilor)

Intrare

Datele se citesc din fisierul text 'cuburi.in' având urmatoarea  structura:

-          pe prima linie sirul culorilor de pe primul rând de cuburi separate  printr-un spatiu

-          pe a doua linie sirul culorilor de pe al doilea rând de cuburi separate  printr-un spatiu

-          datele de intrare se presupun a fi corecte

-          lungimea unei linii din fisier nu depaseste 256 de caractere

Iesire

Rezultatul se va tipari in fisierul text 'cuburi.out' astfel

-          daca se gaseste solutie,

-      pe prima linie se va tipari numarul de cuburi ramase

-      pe a doua linie se va tipari sirul culorilor cuburilor ramase  pe cele doua rânduri, separate printr-un spatiu

-          daca nu se gaseste solutie, se va tipari 'NU'

EXEMPLUL 1

  cuburi.in                                            Þ              cuburi.out

  rosu galben verde negru                                        3

  violet rosu galben alb negru                                 rosu galben negru

EXEMPLUL 2

 cuburi.in                                             Þ              cuburi.out

  rosu galben alb                                                    NU

  verde negru

Timp de executie: 1 secunda/test

CLASA a XI a  si a XII a

Problema 2. (100 puncte)

Role de banda

La un centru de calcul (ramas în urma cu vreo 30 de ani) exista N benzi magnetice, numerotate de la 1 la N. Fiecare banda este asezata pe o rola; nu exista doua benzi asezate pe aceeasi rola. Rolele sunt în numar de N+1, numerotate de la 0 la N, existând o rola goala. Fiecare banda având un început si un sfârsit, ea poate fi înfasurata în doua moduri pe rola: cu începutul în interior sau cu începutul în exterior.

În urma utilizarii, benzile s-au amestecat pe role. Este necesar deci sa fie readuse la locul lor, adica banda i trebuie readusa pe rola i si înfasurata cu începutul în exterior. În acest scop, singura operatie permisa este transferul unei benzi de pe rola pe care se afla pe rola goala; în urma transferului sensul de înfasurare se inverseaza, adica daca banda era cu începutul în exterior ea ajunge cu începutul în interior si viceversa. Se cere, daca este posibil, gasirea unei succesiuni de transferuri astfel încât în final fiecare banda sa ajunga pe rola corespunzatoare.

Intrarea:

Datele de intrare se citesc din fisierul role.in având urmatorul format:

·        pe prima linie se gaseste numarul N de benzi

·        pe fiecare din urmatoarele N linii se gasesc câte doua numere naturale reprezentând asezarea câte unei benzi: a i-a linie (dintre cele N) specifica asezarea benzii cu numarul i, primul numar fiind numarul rolei pe care este asezata, iar al doilea este 0 daca banda este cu începutul în exterior si 1 daca banda este cu începutul în interior.

Limite: N£20000.

Iesirea:

În fisierul role.out se va scrie:

·        pe prima linie numarul T de transferuri

·        pe urmatoarele T linii se va scrie câte un numar reprezentând numarul rolei de pe care se transfera banda catre rola goala.

Numarul T de transferuri nu va depasi 100000.

Daca nu exista solutie, atunci fisierul de iesire va contine doar cuvântul IMPOSIBIL.

.

                                                                       

 MODULO ::::::::::::::::: Calculati (A^B) mod C, unde 0<=A,B,C<=MaxLongInt  . 

 Datele de intrare se citesc din "mod.in" care contine numerele A,B si C

 cate unul pe o linie.

Rezultatul se va scrie pe prima linie a fisierului "mod.out".

Exemplu :

mod.in :       mod.out

2                  2

5

3

Adica restul impartirii lui 2^5 (2 la puterea a 5-a ) la 3 este 2 

TIMP DE EXECUTIE: 1 sec./test 

Monede

Într-o pusculita se afla N monede de diferite valori cu greutatea totala G grame. Greutatea fiecarei monede de o anumita valoare este data în tabelul ce urmeaza.

Valoarea monedei, Lei	Greutatea monedei, grame
1	1
5	2
10	3
25	4
50	5

Elaborati un program care determina suma minima S care ar putea sa fie în pusculita.

Date de intrare.

Fisierul text MONEDE.IN contine pe prima linie numerele naturale N si G separate prin spatiu.

Date de iesire.

Fisierul text MONEDE.OUT contine pe o singura linie un numar natural - suma minima S exprimata în lei.

Exemplu.

MONEDE.IN        MONEDE.OUT

4 14

70

Restrictii. . Timpul de executie nu va depasi 3 secunde. Fisierul sursa se va numi MONEDE.PAS, MONEDE.C sau MONEDE.CPP.

Aceasta problema se va nota cu 50 de puncte.

Numere

Elaborati un program care descompune numarul natural n în suma de k numere naturale în asa mod încît produsul lor  sa fie maxim.

Date de intrare.

Fisierul NUMERE.IN contine pe prima linie numarul natural n.

Date de iesire.

Fisierul NUMERE.OUT contine pe prima linie produsul maxim p.

Exemplu.

NUMERE.IN                   NUMERE.OUT

11

54

Restrictii. . Timpul de executie nu va depasi 1 secunda. Fisierul sursa se va numi NUMERE.PAS, NUMERE.C sau NUMERE.CPP.

                                            

 

PR ::5) O suprafata oceanica este identificata de o retea punctiforma de dimensiune MxN formata din elemente cu valoarea 0 (pentru apa) sau 1 (pentru pamant). De pe planeta Marte soseste o nava spatiala cu extraterestri interesati de experimente pe creierele elevilor de clasa a-XII-a.

Nava are trei picioare in forma de disc: P1 de raza R1, P2 de raza R2, si P3 de raza R3. Centrele celor trei discuri sunt dispuse in varfurile unui triunghi dreptunghic isoscel de cateta C. Centrul lui P1 este dispus in varful unghiului drept. O insula este o portiune de pamant inconjurata de ape sau de limitele retelei.

A)    Identificati numarul de insule.

B)     Stiind ca pot fi maxim 26 de insule in retea, afisati harta suprafetei oceanice, identificand fiecare insula cu o litera mare a alfabetului englez. (pentru fiecare insula se inlocuieste elementul 1 cu litera asociata insulei).

C)    Identificati toate posibilitatile de aterizare ale navei asociind fiecarui picior litera corespunzatoare insulei pe care se poate aseza in intregime piciorul respectiv.

Datele de intrare se preiau din fisierul EXTRA.IN care are urmatoarea structura:

            Pe prima linie a fisierului de intrare sunt valorile M si N, dimensiunea retelei.

Urmatoarele M linii contin cate N caractere  (0 sau 1) reprezentand reteaua punctiforma ce identifica suprafata oceanica.

Urmatoarea linie contine patru numere reale pozitive reprezentand razele celor trei picioare ale navei ( R1, R2, R3) si lungimea catetei C.

Datele de iesire se scriu in fisierul EXTRA.OUT in urmatorul format:

Prima linie: numarul de insule

Urmatoarele M linii contin cate N caractere formate din cifra 0 sau literele mari ale alfabetului englez, reprezentand harta suprafetei oceanice.

In continuare variantele gasite la punctul (C) al problemei vor fi afisate cate una pe fiecare linie in formatul urmator:

P1-I1 P2-I2 P3-I3     unde I1, I2, I3 reprezinta o litera mare a alfabetului englez corespunzatoare insulei pe care se aseaza piciorul respectiv.

Daca la punctul (C) nu exista solutie se va scrie "NU POATE ATERIZA"

Exemplu

EXTRA.IN

10 13

0000000000000

0000000000000

0000000000000

0000011000000

0000011000000

0000000000000

1111000001111

1111000001111

1111000001111

1111000001111

1117

EXTRA.OUT

30000000000000

Clasa a XI-a si a XII-a

Problema 2

            Fie m inele de raze egale asezate astfel incat formeaza un cilindru; fiecare inel are n bile ( n>=3, m>=3). Bilele sunt fixe in raport cu inelul pe care se afla , iar centrele bilelor formeaza un poligon regulat. Bilele pot fi albe sau negre; inelele se pot roti unul fata de celalalt cu un unghi multiplu de +/- 360 grade/n ( sensul pozitiv spre dreapta, sensul negativ spre stanga). Pornind de la o configuratie data, sa se determine o configuratie cu proprietatea ca numarul generatoarelor cilindrului continand m bile de aceeasi culoare este maxim. Datele de intrare se vor citi din fisierul " inel.in", iar datele de iesire se vor stoca in fisierul " inel.out".

Exemplu:

Daca in fisierul de intrare "inel.in" se vor introduce date:

5

4

1 0 1 0

0 1 1 0

1 0 1 0

1 0 0 0

1 0 1 1

in fisierul de iesire "inel.out" se va obtine:

Numerul maxim de generatoare de aceeasi culoare : 2

Rotatiile facute:

(2,0)

(3,0)

(4,2)

(5,2)

            I

ETAPA (Bogdan) Intr-o etapa in Europa se joaca n meciuri de fotbal (n<=100). Stiind rezultatele a n meciuri si doua numere x si y (0<=x,y<=100) sa se aleaga k meciuri (k<=n) din cele n astfel incat suma golurilor inscrise de gazde in cele k meciuri alese sa fie x si suma golurilor inscrise de oaspeti in cele k meciuri alese sa fie y. In cazul in care nu exista solutie se va afisa numarul 0 in fisierul de iesire.

            Obs: un meci nu poate fi ales de doua ori;

                        daca exista mai multe solutii se va furniza una singura;

Datele de intrare se citesc din fisierul "input.txt" astfel:

n -pe prima linie numarul de meciuri;

x₁ y₁ -pe  urmatoarele n linii rezultatele celor n meciuri;

x₂ y₂ -x_i , y_i numere pozitive (0<=x_i,y_i<=100);

... (x_i - goluri inscrise de gazde; y_i - oaspeti)

x_n y_n

x y      -numerele    x si y;

Datele de iesire se scriu in fisierul "output.txt" astfel:

k -pe prima linie k (numarul de meciuri alese);

j₁ -pe urmatoarele k linii numarul de ordine al meciurilor alese;

.

j_k

Exemplu:

Input.txt:                                                           Output.txt:

3                                                                      2

2 1                                                                    1

4 2                                                                    3

5 3

7 4

Input.txt:                                                           Output.txt:

1                                                                      0

1 1

2 2

Timp de executie: o secunda pe test.

Nota: ambele subiecte sunt obligatorii; timp de lucru 3 ore.

Olimpiada de Informatica - Faza pe Municipiul Bucuresti

Clasa a XI-a si a XII-a - faza pe municipiu

Problema 1

Jocul de unul singur(50 puncte)

            Cand Mars este cu adevarat plictisit , si simte nevoia de ceva nou si interesant , ia un pachet de carti special si se joaca . Prin ce e acest pachet special ? Prin faptul ca are numai carti negre si rosii , si anume N carti negre si R carti rosii ( N si R cunoscute ) .

            Jocul consta in faptul ca dupa ce amesteca foarte bine cartile (adica orice configuratie are sanse egale sa apara) incepe si extrage o carte . Fara sa se uite la ea incearca sa ghiceasca ce carte este (rosie sau neagra) , dupa care se uita la ea . Daca a ghicit-o, o pune de-o parte si extrage alta , continuand procedeul pana nu mai nimereste sau se termina pachetul . Daca nu a ghicit-o jocul s-a terminat si isi numara cate carti a reusit sa ghiceasca (fara ultima, pe care n-ai ghicit-o) .

Dar Mars s-a plictisit sa joace la intamplare si si-a facut o strategie . El numara ce carti au iesit si astfel stie ce carti au ramas in pachet. Cand se pune problema sa ghiceasca, el alege culoarea prezenta cel mai des pe cartile ramase in pachet , iar in caz de egalitate alege rosu.

            Jucand asa des, i-a venit in minte o intrebare . Care este numarul mediu de carti pe care reuseste sa le ghiceasca la un joc ? Intr-adevar el a jucat atat de mult incat si-a dat seama de rezultat , dar nu stie daca voi stiti ...

            In fisierul de intrare JOC.IN se gasesc doua numere separate printr-un spatiu (N respectiv R) . Iar voi trebuie sa scrieti in fisierul JOC.OUT pe un singur rand un numar cu 4 zecimale exacte reprezentand numarul mediu de carti extrase la un joc .

Exemplu :

JOC.IN

1 1

JOC.OUT

1.0000

Explicatii :

Avem un pachet cu o carte rosie si una neagra . Mars zice rosu si are sanse 50% sa nimereasca . Daca nu a ghicit, are 0 carti ghicite, iar daca a nimerit sigur o va nimeri si pe a doua pentru ca stie ce carte a ramas si va avea 2 carti ghicite . Astfel numarul mediu este 1.

Observatii :

·                     0<=N,R<=10000

·                     Daca N si R sunt 0 numarul de carti ghicite este 0

·                     Se recomanda folosirea tipului de date double pentru a evita pierderi de precizie

Timp de executie 1 secunda pe un 486 . Se asigura 200K memorie disponibila .

Inspectoratul Scolar al Municipiului Bucuresti

Problema 2

CUIE (50 puncte)

            Pe o masa din lemn (considerata infinita) sunt amplasate N placi dreptunghiulare identice, de laturi L, respectiv H. Placile sunt plasate paralel cu axele, in pozitii de coordonate intregi, si se pot suprapune (partial si/sau total).

            Sa se bata cuie in masa, astfel incat:

            - fiecare cui sa intepe cel putin o placa;

            - fiecare placa sa fie intepata de EXACT un cui.

            Se considera ca un cui batut exact pe o margine a unei placi NU INTEAPA placa respectiva. Coordonatele cuielor pot fi intregi sau reale. L si H sunt numere naturale nenule, N<=1500.

            Fisierul de intrare CUIE.IN are urmatoarea structura:

            L H                  - dimensiunile placilor

            N                     - numarul de placi

            x1 y1               

            x2 y2

            ...

            xN yN

            Pozitia fiecarei placi K este specificata prin xK si yK. Placa este un dreptunghi delimitat de dreptele: x=xK, x=xK+L, y=yK, y=yK+H. Un cui de coordonate (XC,YC) inteapa placa K daca

            xK < XC < xK+L          si

            yK < YC < yK+H        

            In fisierul de iesire CUIE.OUT se vor afisa coordonatele cuielor, cate un cui pe fiecare linie. Nu se impune o limita pentru numarul de cuie, dar solutia trebuie sa respecte restrictiile problemei.

            Exemplu:

            CUIE.IN

            4 3

            6

            9 6

            1 1

            3 3

            8 1

            9 6

            10 2

            CUIE.OUT                   (exista si alte variante!!!)

            2 2

            6 5

            11 3

            10 8.2

                                                                            OLIMPIADA DE INFORMATICA

                                                                               FAZA JUDETEANA 10.03.2001

                                                                                           CLASELE XI-XII

Problema 1.

    Intr-un oras intersectiile de strazi sunt numerotate de la 1 la n (se considera intersectii si capetele stazilor care nu se intalnesc cu alte strazi). Primaria orasului doreste sa numeroteze si strazile orasului intr-un mod  care sa tina seama de numerotarea intersectiilor, astfel incat doua strazi diferite sa aiba numere diferite si in fiecare intersectie sa soseasca o strada care sa aiba numarul intersectiei.

    Pentru un graf al stazilor cu intersectii numerotate, sa se faca o astfel de numerotare a strazii respectand restrictiile specificate.

    

    Fisierul de intrare "INTERSEC.TXT" contine un set de date de forma:

         n-numarul de intersectii (2<n<50), inclusiv capetele de strazi, urmate de linii de forma:

         i,j1 j2.jk- intesectia i este legata de intersectiile j1,j2,.,jk printr-o strada(j1>i, j2>i,.,jk>i).

    NOTA: O strada nu are decat doua intersectii, capetele ei.

                  Pentru fiecare set de date se cere sa se determine o numerotare a strazilor, daca exista o astfel de                                                                    

                  numerotare , sau 0 daca nu exista o astfel de numerotare. Numaratoarea se afiseaza pe fiecare

                  linie printr-o pereche de numere care reprezinta intersectiile care delimiteaza strada si apoi     

                   numarul  strazii.

     EXEMPLE :

             a). INTERSEC.TXT     Fisierul de iesire "NUMEROT.TXT" poate contine

4                                                                                                              121

1234                                                                                                  133

23                                                                                                          144

34                                                                                                          232

   345

            b). INTERSEC.TXT      Fisierul de iesire "NUMEROT.TXT" poate contine

   0

   12

 

  Problema 2.

       Se citeste de la tastatura un numar intreg N, 1<=N<=100. Se cere sa se afiseze pe ecran numarul permutarilor de N elemente cu proprietatea ca oricare ar fi i, 1<=i<=N,avem p(i)<>i.

          EXEMPLU:

                  Pentru N=4  numarul cerut este 9.

   Problema 3.

       Fie 0<f(1)<f(2)<f(3)<. un sir de numere naturale. Cel de-al n-lea intreg pozitiv ce nu apartine sirului este f(f(n))+1. Pentru un p natural dat se cere sa se calculeze f(p).

Olimpiada Judeteana de Informatica

Tg. Mures - jud. Mures

10 martie 2001

clasele a XI-a si a XII-a

Problema 1.:  Spre culmi

Se da un vector cu  N <= 10000  numere întregi, cuprinse între  1 si 50000. Sa se partitioneze acest vector în cât mai puþine subsiruri strict crescatoare.

Date de intrare

Fisierul CRESCx.IN contine doua linii. Prima linie contine numarul N, iar a doua contine cele N numere, despartite prin câte un spatiu.

Caracterul x din numele fisierului are semnificatia de numar de ordine al fisierului si se citeste de la tastatura.

Date de iesire

Fisierul CRESC.OUT va contine pe prima linie numarul minim K de subsiruri în care se poate partitiona vectorul. Pe fiecare din urmãtoarele K linii se va descrie câte unul din aceste subsiruri, precizând indicii în vector ai elementelor subsirului, în ordine crescatoare, despartiti prin câte un spatiu. Ordinea de afisare a subsirurilor este indiferentã.

Exemplu

       CRESC0.IN                                                    CRESC.OUT

            7                                                                      2

            9  2  4  7  10  11  8                                          2  3  4  7

                                                                                    1  5  6

Problema 2.: Evitarea inundatiilor

Ministerul Apelor si Padurilor hotaraste sa tina evidenta sistemelor hidrografice pe calculator. Pentru aceasta, trebuie retinute toate cele N (2<=N<=100) râuri si afluentii lor. Cele N râuri sunt numerotate de la 1 la N. Se citesc dintr-un fisier perechi de forma: i  j cu urmatoarea semnificatie: râul i este afluent al râului j.

Pentru a stabili situatiile în care apar inundatii, trebuie calculat debitul fiecarui râu în parte.

Debitul unui izvor se defineste ca fiind cantitatea de apa care trece prin sectiunea izvorului în unitatea de timp. Debitul râului i la varsare va fi egal cu debitul izvorului râului i plus suma debitelor afluentilor la varsare în râul i.

Dându-se pentru fiecare râu debitul izvorului sau, sa se calculeze debitul la varsare al fiecarui râu.

Fisierul text de intrare APE.IN cuprinde mai multe seturi de date, având urmatorul format:

-        prima linie contine numarul de seturi de date;

-        urmatoarele linii contin seturile de date.

Pentru un set de date:

-        prima linie contine numarul râurilor si apoi, pe fiecare linie, perechile de râuri (ultima pereche este 0 0), dupa care urmeaza pe o linie debitele râurilor  ( în ordinea crescatoare a râurilor ), valorile fiind separate printr-un spatiu;

-        datele referitoare la un set de date se încheie cu o linie care contine doar cifra 0.

Observatii

-        se considera debitele râurilor ca fiind numere întregi

-        se considera ca datele de intrare sunt valide.

Iesirea va consta în afisarea pe ecran a debitelor la varsare pentru fiecare râu, în ordinea crescatoare a râurilor, fiecare debit pe un rând.

EXEMPLU:

APE.IN

3

4

1 3

2 4

3 4

0 0

5 3 6 1

0

3

2 1

3 1

0 0

1 2 3

0

8

2 1

8 1

4 2

5 2

7 3

8 3

0 0

1 2 3 4 5 6 7 8

0

Iesirea va fi:

5

3

11

15

6

2

3

20

11

18

4

5

6

7

8

OLT, Clasa a XI-a si a XII-a, 10 martie 2001

PROBLEMA 1 : PRINTRE ISTEŢI   (100 puncte)

            Verde Împarat a decis sa-si casatoreasca fiica. La curtea palatului sosesc mai multi cavaleri sa ceara mâna fetei. Împaratul doreste sa-l aleaga ca ginere pe cel mai istet dintre ei. Pentru aceasta le cere sa gaseasca solutia unei probleme pentru a carei rezolvare se chinuie de mai mult timp. Se da o matrice cu m linii si n coloane si se cere sa se precizeze în câte moduri putem aseza 1 si -1 astfel încât sa se obtina pe fiecare linie si coloana produsul -1, daca se poate. Cavalerii va cer sa-i ajutati în rezolvarea problemei.  

             

            Datele de intrare se citesc din fisierul  ISTET.IN în ordinea:

-pe prima linie: m,n reprezentând dimensiunea retelei (m,n£250)

            Datele de iesire se vor scrie în fisierul  ISTET.OUT :

 -pe prima linie: nr de posibilitati sau 0 când nu exista solutii 

Exemplu:

ISTET.IN                                               ISTET .OUT

3 3                                                       16

Timp de executie 2 secunde/test

           

PROBLEMA 2 : CĂRŢI  (100 puncte)

            N elevi au decis sa schimbe carti între ei, respectând algoritmul urmator:

Fiecare elev da carti la jumatate dintre elevii cunoscuti de el si primeste carti de la cealalata jumatate de elevi care-l cunosc. Se stie ca fiecare elev are un numar par de cunostinte si, un elev care a primit o carte de la un prieten nu poate sa dea o carte la acelasi elev. Nu exista elev care sa nu cunoasca pe nimeni. Daca elevul i îl cunoaste pe j, si j îl cunoaste pe i.

            Sa se stabileasca pentru fiecare elev care sunt elevii carora trebuie sa le dea carti.  

             

            Datele de intrare se citesc din fisierul  CĂRŢI.IN în ordinea:

-pe prima linie: n,  reprezentând numarul de elevi (n£50)

-pe liniile urmatoare se afla n linii care contin câte un numar par de valori separate între ele prin spatii, reprezentând elevii cunoscuti de elevul 1, apoi de elevul  2, s.a.m.d.

           

            Datele de iesire se vor scrie în fisierul  CĂRŢI.OUT :

-pe prima linie: numarul de elevi carora le da carti elevul 1

-pe a doua linie valori separate prin spatii reprezentând elevii care primesc carti de la elevul 1

-....... pentru ceilalti elevi

Exemplu:

CĂRŢI.IN                                               CĂRŢI .OUT

5                                                          2

2 3 4 5                                                 2 4

1 3 4 5                                                 2

1 2 4 5                                                 3 5

1 2 3 5                                                 2

1 2 3 4                                                 1 4

                                                            2

                                                            2 5

                                                            2

                                                            1 3

Timp de executie 2 secunde/test

           

Clasa a XI -XII-a

Problema 1 Timbre

Fiind date un set de n valori distincte de timbre si limita superioara k a numarului de timbre care pot fi lipite pe un plic, determinati cea mai mare secventa de valori consecutive de la 1 la M centi care se poate obtine.

Datele de intrare se citesc din fisierul T.IN ce contine:

        - pe prima linie din fisier se afla k (K<=10000), numarul total de timbre ce pot fi folosite;

          si n numarul de valori ale timbrelor, N<=10000; aceste valori sunt mai mici decat 30000;

        - pe urmatoarea linie se gasesc cele cele n valori ale timbrelor separate prin cate un spatiu.

Datele de iesire se vor scrie in fisierul T.OUT care va contine un singur numar reprezentand numarul M (maxim) de valori consecutive care se pot forma cu maxim K timbre de valori date.

Exemplu:

T.IN

      5 2

1 3

Fisierul T.OUT contine:

      13

Observatie: Explicatia continutului fisierului de iesire din exemplu:

1=1*1; 2=2*1; 3=3*1; 4=4*1; 5=5*1; 6=2*3; 7=2*3+1*1; 8=2*3+2*1; 9=3*3; 10=3*3+1*1; 11=3*3+2*1; 12=4*3; 13=4*3+1*1; Nu exist nici o modalitate de obtine 14 centi folosid maxim 5 timbre de 1 sau 3 centi

Timp de rulare:  5 sec/per test

Problema 2 Dilatare

Se considera un poligon convex cu N varfuri date prin coordonatele lor carteziene.

Printr-un proces de dilatare cu o distanta D fata de fiecare latura, se obtine un nou poligon.

Cerinta: Sa se determine cordonatele poligonului obtinut prin procesul de dilatare si raportul ariilor celor doua poligoane (aria primului/aria noului poligon).

Datele de intrare se citesc din fisierul IN.TXT ce contine:

-         pe prima linie din fisier numarul N (N<=100) si distanta D (D<=1000) cu care se face dilatarea

-         pe urmatoarele linii se gasesc perechi de doua numere intregi x y reprezentand coordonatele carteziene ale primului poligon, scrise in ordine trigonometrica.

Datele de iesire se vor scrie in fisierul OUT.TXT care va contine

- pe primele N linii, perechi de doua numere reale x y reprezentand coordonatele carteziene ale noului poligon, scrise in ordine trigonometrica, cu o zecimala.

-         Pe ultima linie raportul ariilor, cu trei zecimale.

OBSERVATIE: Primul varf al noului poligon scris in OUT.TXT va fi punctul de intersectie dintre paralela la prima latura si paralela la cea de a doua latura a poligonului initial.

Exemplu:

IN.TXT

3 10

60 40

120 40

90 80

OUT.TXT

140.0   30.0

90.0   96.7

40.0   30.0

0.360.

Timp de rulare: 3 sec/per test

 

Clasa a XI-XII-a

1. Se da o multime de n numere pozitive A=. Notam cu SA1, SA2, ... sirul format din submultimile multimii A, (inclusiv multimea vida) si cu SSA1, SSA2, ... sirul alcatuit din sumele fiecareia din respectivele submultimi. Sa se precizeze câte valori distincte apar în acest ultim sir.

Date de intrare: în fisierul text SUME.IN, pe prima linie valoarea lui n, apoi pe urmatoarele linii valorile elementelor a1, a2, ..., an, separate prin minim un caracter alb;

Date de iesire: în fisierul text SUME.OUT, pe prima linie, valoarea ceruta.

Restrictii:      2 £ n £ 500;

                   0 £ ai £ 1000,         i=1,2,...,n

Limita de timp: 5 secunde pe test.

Exemplu:

SUME.IN                SUME.OUT

3                           7                

5 2 3

Explicatii: sumele distincte care se pot forma sunt: 0,2,3,5,7,8,10

                                                Prof. Stelian Ciurea - Liceul Teoretic Brukenthal Sibiu

2. Se dau n cercuri (n £ 20) de raza data, numerotate de la 1 la n, neexistând 3 cercuri cu un punct comun. Prin pas de la cercul i la cercul j se întelege segmentul ce uneste centrele celor doua cercuri. Prin drum se întelege o succesiune de pasi. Sa se determine drumul ce ajunge din centrul primului cerc în centrul ultimului cerc cu proprietatea ca numarul punctelor de intersectie dintre drum si cercuri este minim.

Datele de intrare: se citesc din fisierul CERCUL.IN pe primul rând numarul de cercuri si valoarea razei, apoi pe fiecare rând coordonatele centrelor cercurilor separate prin spatiu.

Datele de iesire: se scriu în fisierul CERCUL.OUT pe un rând separate de spatiu numerele de ordine ale cercurilor din drumul gasit.

Limita de timp: 5 sec/test pe un sistem la 300 Mhz.

Exemplu:

CERCUL.IN                                        CERCUL.OUT

5  1                                                      1 2 5

4 1

2 5

4 5

3 7

1 15

                                    Prof. Antoniu Pitic - Liceul Teoretic "O. Ghibu" Sibiu

           

Nota:    Toate subiectele sunt obligatorii fiecare subiect fiind notat cu 25 puncte

            Timp de lucru 3 ore.

CLASA  a XI-a si a-XII-a

Subiectul 1: Postasul

Se da un cartier ale carui blocuri sunt pozitionate sub forma unei matrici de 4 linii si N coloane.  Pentru un N dat sa se determine numarul variantelor de traseu pe care le poate parcurge postasul zonal, astfel incât sa treaca pe la toate blocurile, o singura data pe la fiecare. Postasul pleaca de la blocul de pe pozitia (1,1) spre blocul de pe pozitia (1,2) (prima linie, a doua coloana) si trebuie sa se întoarca la blocul (1,1).

N se citeste de la tastatura(3<=N<=25) si rezultatul se afiseaza pe ecran.

Exemple:

• Pentru N=3         Iesirea este: 2

Cele doa variante de traseu sunt (nu trebuie afisate!!!):

(1,1) (1,2) (1,3) (2,3) (3,3) (4,3) (4,2) (4,1) (3,1) (3,2) (2,2) (2,1) ->(1,1)

(1,1) (1,2) (1,3) (2,3) (2,2) (3,2) (3,3) (4,3) (4,2) (4,1) (3,1) (2,1) ->(1,1)

• Pentru N=17      Iesirea este: 1029864

Subiectul 2: Multiplu

Scrieti un program care pentru un numar natural N (0 < N <= 4999) si pentru M cifre date X₁, X₂, ...X_M  (0<M<=9, 0<=X_I<=9) sa gaseasca cel mai mic multiplu strict pozitiv al lui N care nu contine alte cifre în afara de X₁,X₂..X_M (cifrele X₁,X₂..X_M pot apare în multiplu de 0, 1 sau mai multe ori).

Numele fisierului de intrare si a celui de iesire se vor citi de la tastatura.

Fisierul de intrare contine mai multe seturi de date separate de câte o linie goala. Fiecare set de date are urmatoarea forma:

·      pe prima line - numarul N

·      pe a doua line - numarul M

      pe urmatoarele M linii - cifrele X₁,X₂..X_M.

Pentru fiecare set de date programul trebuie sa tipareasca în fisierul de iesire, pe o singura linie, multiplul gasit, daca exista si 0 daca nu exista.

Exmplu:

Input	output
22 3 7 0 1 2 1 1 4999 6 5 7 6 2 9 0	110 0 20000999

Venit

Componenta A[i] a tabloului unidimensional A reprezinta venitul  sau pierderile unei întrepinderi pe parcursul zilei i, i=1, 2, 3, ..., n. Suma

reprezinta venitul  sau pierderile întreprinderii pe parcursul unei perioade de k zile, începînd cu ziua j.

Scrieti un program care determina valoarea maxima a sumei S.

Date  de intrare.

Fisierul text VENIT.IN contine pe prima linie numarul natural n. Pe fiecare din urmatoarele n linii ale fisierului este înscris cîte un numar întreg. Pe linia  a fisierului în studiu este înscris numarul A[i].

Date de iesire.

Fisierul text VENIT.OUT va contine pe o singura linie suma maxima S.

Exemplu.

VENIT.IN         VENIT.OUT

6 -1 4 2 -3 2 -1

6

Restrictii. , . Timpul de executie nu va depasi 1 secunda. Fisierul sursa se va numi VENIT.PAS, VENIT.C sau VENIT.CPP.

 

Problema 3- Navigare pe Web(100 puncte)

Se considera n site-uri Web complet interconectate (fiecare site are cate un link la fiecare din celelate site-uri). Un hacker plictisit, doreste sa viziteze toate cele n site-uri, iar fiecare site e vizitat o singura data. Dupa ce a vizitat cele n site-uri, hacker-ul doreste sa ajunga iarasi la site-ul de la care a inceput vizitarea. In cate moduri poate vizita hacker-ul cele n site-uri, pornind de pe un anumit site stabilit , in conditiile mentionate mai sus.

In fisierul de intrare WEB.IN este scris numarul n.

In fisierul de iesire WEB.OUT se va scrie numarul de moduri de vizitare a celor n site-uri.

Limite:

-         2<n<=100;

-         site-ul de la care porneste hacker-ul e singurul site vizitat de doua ori.

Exemplu:

            WEB.IN                    WEB.OUT

4                                                                        3

Observatie: Se cere numarul de moduri distincte de a vizita cele n site-uri.

De exemplu, pentru n=4 vizitarea paginilor in ordinea 1-2-3-4-1 este identica cu vizitarea paginilor in ordinea 1-4-3-2-1.

            Timp de executie: 1 secunda/test. Punctajul 100 puncte.

Fisier sursa	Fisier de intrare	Fisier de iesire
WEB.PAS sau	WEB.IN	WEB.OUT
WEB.CPP

Date de Test:

        WEB.IN                                            WEB.OUT

1.          3                                                          1

2.          8                                                        2520

3.         10                                                      181440

4.         20                                                60822550204416000

5.         45         55 cifre=> 132913578739422438402181290550730794.6400000000000

6.         50         63 cifre=> 304140932.605120000000000

7.         77         111 cifre=> 942747350.86112000000000000000000

8.         83         123 cifre=> 237682166.559680000000000000000000

9.         90         136 cifre=> 825397758.9878400000000000000000000

10.      100        156 cifre=> 466631077.584320000000000000000000000

Observatii:

            -     1 test = 10 puncte

-         exista 10 teste pentru fiecare problema

-         punctajul total = 300 puncte

-         nu exista puncte din oficiu.

Se dau doua siruri de numere întregi a(i), i=1,n si b(j), j=1,m. Se cere sa se afiseze cel mai lung subsir comun ordonat crescator.

Datele se citesc din fisier.

           

Fisierul de intrare: intrare.in

                    n,m

                    sir 1

                    sir 2

fisierul de iesire : iesire.out contine subsirul cerut

            Timp de executie 1 sec.

Date de test:

 Set 1:  

     Intrare.in:

     

                7 5

                8 0 -3 4 -4 9 10

                2 0 4 9 10         

   Set 2:  

     Intrare.in:

     

                5 3

                1 0 2 0 3

                6 7 8          

                       

Set 3:  

     Intrare.in:

     

              30 28

              1 0 2 0 3 4 5 6 0 7 0 8 9 10 0 11 12 13 14 15 16 17 18 19 20 21 22 23 24 0 25

              1 2 3 4 5 6 7 8 9 10 11 0 12 0 13 14 15 16 17 18 19 20 21 0 22 0 23 24         

Clasele a XI-a si a XII-a

Problema 2: ZMEU

Un zmeu cu n capete calatoreste din poveste în poveste, iar în povestile traditionale întâlneste câte un Fat Frumos care-l mai scurteaza de câteva capete, în timp ce în povestile moderne salveaza omenirea mâncând în timp record, cu toate capetele lui, insecte ucigase aparute prin mutatii genetice. Într-o seara, el îsi planifica o seccesiune de povesti carora sa le dea viata. El stie p povesti numerotate de la 1 la p, durata fiecareia si numarul de capete pe care le pierde în fiecare poveste. Mai stie o multime de k perechi de povesti, semnificând faptul ca a doua poveste din pereche nu poate fi spusa dupa prima poveste din pereche.

Cerinta

stiind ca trebuie sa înceapa cu povestea 1 si sa încheie succesiunea cu povestea p, ajutati bietul zmeu sa aleaga una sau mai multe povesti intermediare astfel încât durata totala sa fie minima si sa ramâna cu cel putin un cap la sfârsitul tuturor povestilor.

Date de intrare

Fisierul de intrare zmeu.in contine pe prima linie numerele n, p si k despartite prin câte un spatiu. Pe fiecare din urmatoarele p linii se afla câte o pereche de numere d_i si c_i (separate prin câte un spatiu) ce reprezinta durata si numarul de capete taiate pentru fiecare poveste. Iar pe ultimele k linii se afla câte o pereche de numere p_i si p_j (separate prin câte un spatiu) ce semnifica faptul ca povestea p_j nu poate fi spusa dupa povestea p_i.

Date de iesire

Fisierul de iesire zmeu.out contine o singura linie pe care se afla un numar natural reprezentând durata (minima) a succesiunii de povesti sau valoarea -1 daca nu exista o astfel de succesiune.

Restrictii si precizari

§      2=N<=500

§      1<=P<=200

§      1<=k<=30000

§      Valorile reprezentând duratele si numarul de capete sunt numere naturale (duratele fiind strict pozitive), nedepasind 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 secunda