Documente online.
Zona de administrare documente. Fisierele tale
Am uitat parola x Creaza cont nou
 HomeExploreaza
upload
Upload




OLIMPIADA DE INFORMATICĂ - CLASA a XI a si a XII a

profesor scoala


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]*12+x[2]*22+.+x[k]*k2.

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)

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

Cuvinte.in Fraze.out

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

Date de iesire

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

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
























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

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






Timp maxim de executare/test: 1 sec.

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 :

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 .

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

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)




d+!a*c





Fisierul P11.out


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:

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


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





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)


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





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


TIMP DE EXECUTIE: 1 sec./test

























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

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




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.

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







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!!!):






















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

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


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


Exemple

zmeu.in

zmeu.out










Timp maxim de executare/test: 1 secunda


Document Info


Accesari: 6097
Apreciat: hand-up

Comenteaza documentul:

Nu esti inregistrat
Trebuie sa fii utilizator inregistrat pentru a putea comenta


Creaza cont nou

A fost util?

Daca documentul a fost util si crezi ca merita
sa adaugi un link catre el la tine in site


in pagina web a site-ului tau.




eCoduri.com - coduri postale, contabile, CAEN sau bancare

Politica de confidentialitate | Termenii si conditii de utilizare




Copyright © Contact (SCRIGROUP Int. 2024 )