Subiectul 1. (100p)
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
Subiectul 2. (100p)
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 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
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
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 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 eficient 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.
Fisierul de intrare URGENTA.IN are urmatorul format:
N M K
i1 j1 p1 - între punctele i1 si j1 exista o
cale de acces de prioritate p1
i2 j2 p2 - între punctele i2 si j2 exista o
cale de acces de prioritate p2
...
iM jM pM - între punctele iM si jM
exista o cale de acces de prioritate pM
Fisierul de iesire URGENTA.OUT va avea urmatorul
format:
gravmax - gravitatea maxima
C - numarul de
cai de acces întrerupte de calamitate
k1 h1 - între
punctele k1 si h1 a fost întrerupta calea de
acces
k2 h2 - între punctele k2 si h2
a fost întrerupta calea de acces
...
kC hC - între punctele kC si hC
a fost întrerupta calea de acces
|
URGENTA.IN |
URGENTA.OUT |
|
|
|
Timp maxim de executare: 1 secunda / test
Olimpiada Judeteana de Informatica
9 martie 2002, ora 900
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
nunta.out
Timp maxim de executare: 1 secunda / test
Faza judeteana, 23 martie 2003
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.
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.
Fisierul de intrare compus.in contine pe prima linie masa moleculara a compusului.
Fisierul de iesire compus.out contine o singura linie pe care se afla numarul de compusi determinat.
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):
|
compus.in |
compus.out |
compus.in |
compus.out |
|
|
|
|
|
Timp maxim de executare/test: 1 sec.
INSPECTORATUL sCOLAR JUDEŢEAN
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 :
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>
GOSPODAR.IN
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;
NOTĂ
Timp efectiv de lucru - 2 ore;
Se acorda 10 puncte din oficiu;
Datele de intrare sunt corecte;
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
EXTRA.OUT
00000AA000000
00000AA000000
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
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.
!b*(a+b+c)
d+!a*c
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 - .
P . - - .
Q - - . -
R . - .
S . . .
T -
U . . -
V . . . -
W . - -
X - . . -
Y - . - -
Z - - . .
Mesajul codificat Morse este reprezentat printr-un sir de biti, dupa regulile:
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:
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:
Atunci 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:
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 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
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 |
|
|
DA |
|
NU |
Timp de executie: 1 secunda/test
Punctaj: 45 puncte
Observatie: Datele de intrare sunt corecte.
Judete
Laserul
Drum cu semafoare
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.
Pe prima linie, momentul cel mai târziu al plecării
Pe a doua linie, sirul intersectiilor parcurse (1 si N inclusiv)
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
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
Adica restul impartirii lui 2^5 (2 la puterea a 5-a ) la 3 este 2
Monede
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
|
|
|
|
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
EXTRA.OUT
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:
in fisierul de iesire "inel.out" se va obtine:
Numerul maxim de generatoare de aceeasi culoare : 2
Rotatiile facute:
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;
x1 y1 -pe urmatoarele n linii rezultatele celor n meciuri;
x2 y2 -xi , yi numere pozitive (0<=xi,yi<=100);
... (xi - goluri inscrise de gazde; yi - oaspeti)
xn yn
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);
j1 -pe urmatoarele k linii numarul de ordine al meciurilor alese;
jk
Exemplu:
Input.txt: Output.txt:
Input.txt: Output.txt:
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
JOC.OUT
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
CUIE.OUT (exista si alte variante!!!)
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
b). INTERSEC.TXT Fisierul de iesire "NUMEROT.TXT" poate contine
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
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.
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.
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
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.
se considera debitele râurilor ca fiind numere întregi
se considera ca datele de intrare sunt valide.
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:
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:
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
Fisierul T.OUT contine
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
OUT.TXT
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
ai 1000, i=1,2,...,n
Limita de timp: 5 secunde pe test.
Exemplu:
SUME.IN SUME.OUT
Explicatii: sumele distincte care se pot forma sunt: 0,2,3,5,7,8,10
Prof.
Stelian Ciurea - Liceul Teoretic Brukenthal
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
Prof.
Antoniu Pitic - Liceul Teoretic "O. Ghibu"
Nota: Toate subiectele sunt obligatorii fiecare subiect fiind notat cu 25 puncte
Timp de lucru 3 ore.
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:
|
Cele doa variante de traseu sunt (nu trebuie afisate!!!): |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Subiectul 2: Multiplu
Scrieti un program care pentru un numar natural N (0 < N <= 4999) si pentru M cifre date X1, X2, ...XM (0<M<=9, 0<=XI<=9) sa gaseasca cel mai mic multiplu strict pozitiv al lui N care nu contine alte cifre în afara de X1,X2..XM (cifrele X1,X2..XM 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 X1,X2..XM.
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 |
|
|
|
Venit
Componenta A[i]
a tabloului unidimensional A reprezinta venitul 
sau pierderile 
unei întrepinderi pe parcursul zilei i, i 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
|
|
|
|
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.
exista 10 teste pentru fiecare problema
punctajul total = 300 puncte
nu exista puncte din oficiu.
Clasele a XI-a si a XII-a
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 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.
stiind ca trebuie sa înceapa cu povestea 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.
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 di si ci (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 pi si pj (separate prin câte un spatiu) ce semnifica faptul ca povestea pj nu poate fi spusa dupa povestea pi.
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 daca nu exista o astfel de succesiune.
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 .
Exemple
|
zmeu.in |
zmeu.out |
|
|
|
Timp maxim de executare/test: 1 secunda
|
