	1. Unele scheme de codificare cer ca mesajul codificat sa fie 
trimis in doua parti. Prima parte, numita si header, contine caracterele 
mesajului; a doua parte contine o structura care reprezinta mesajul. 
  Trebuie sa scriti un program care decodifica un mesaj dat sub aceasta
schema. Ideea schemei de codificare esteo secventa de "chei" - siruri 
de 0 si 1 definite astfel:
 0,00,01,10,000,001,010,100,101,110,0000,0001,..,1011,1110,00000....
Prima cheie din secventa este de lungime 1, urmatoarele 3 sunt de 
lungime 2, urmatoarele 7 de lungime 3, apoi sunt 15 de lungime 4, etc. 
Daca doua chei alaturate au aceeasi lungime, a doua se poate obtine din 
prima adaugand 1 in baza 2. Nu exista in secventa nici o cheie formata 
numai din 1.
	Cheile sunt in corespondenta cu caracterele din header in ordinea 
aparitiei lor. Adica, prima cheie (0) corespunde primului caracter din 
header, a doua cheie (00) reprezinta al doilea caracter, a k-a cheie 
corespunde celui de-al k-lea caracter. Daca de exemplu headerul este 
AB#TANCnrtXc, atunci 0 corespunde lui A, 00 lui B, 01 lui #, 10 lui T, 
000 lui A,..,110 lui X si 0000 lui c.
	Mesajul codificat contine numai 0,1 si posibil treceri la linia 
urmatoare, care se vor ignora. Mesajul este impartit in segmente. Primele
3 cifre ale unui segment dau reprezentarea binara a lungimii cheilor in 
segment. Daca de exemplu primele cifre sunt 010, atunci restul segmentului 
consta din chei de lungime 2 (00,01 sau 10). Sfarsitul unui segment este 
un sir de 1 care are aceeasi lungime cu lungimea cheilor in segment. 
Deci, un segment de chei de lungime 2 se termina cu 11. Intregul mesaj 
codificat se termina cu 000 (care ar semnifica un segment in care cheile 
au lungimea 0). mesajul este decodificat translatand cheile din segmente
in caracterele corespunzatoare din header.

Intrare si iesire:
   Fisierul de intrare contine mai multe seturi de date. Fiecare set 
consta dintr-un header - scris pe o singura linie, si un mesaj care poate 
fi extins pe mai multe linii. Lungimea headerului este linitata de faptul
ca sirurile de chei au lungimea maxim 7 (111 in binar). Daca un caracter 
apare de mai multe ori in header, atunci lui ii vor corespunde mai multe 
chei. Mesajul codificat contine numai 0 si 1 si este o codificare corecta, 
conforma cu schema prezentata mai sus. Adica, segmentele de mesaj incep 
cu secventa de 3 cifre si termina cu o secventa de 1. Cheile din orice
segment dat sunt de aceeasi lungime si coresund caracterelor din header.
Mesajul se termina cu 000. 
	Pentru fiecare set de date, programul trebuie sa scrie mesajul
decodificat pe o linie seprata. Nu vor fi linii albe intre mesaje.

Exemplu:
Pentru intrarea
TNM AEIOU
0010101100011
1010001001110110011
11000
$#**\]0100000101101100011100101000
iesirea va fi
TAN ME
##*\$
==================================

	2. Se dau  n  cuvinte  W_1, W_2, ..., W_n, fiecare  fiind  format din
unul  sau doua caractere ( |W_i| <= 2,  1 <= i <= n ).  Sa se gaseasca
un cuvant W de lungime minima care sa contina toate cuvintele W_1, W_2
..., W_n ca subcuvinte.

Intrare:
    Fisierul  de intrare va contine  mai multe seturi de date.  Un set
de date va avea pe prima linie numarul  n  ( n <= 1000 ) de cuvinte si
pe urmatoarele n linii cele n cuvinte cate unul pe linie.

Iesire:
    Se va afisa la terminal cuvantul W.

Exemplu:
    Daca fisierul de intrare are continutul:

7
a
b
cd
cf
fg
gh
gk
    O Iesirea posibila este:
------------------------------------------------------------------------
Cuvantul:
   abcfghgkcd
==================================================================

	3. Serviciul de translatare solicita ultima parte a unui translator
pentru o foarte simpla masina SIC (Simplified Instructional Computer).
Intrarea in translator este formata din expresii aritmetice in forma 
postfixata iar iesirea va fi in limbajul de asamblare. Codul contine un 
singur registru si urmatoarele instructiuni, in care operandul este un 
identificator sau o locatie de memorie.

L - incarca operandul in registru;
A - aduna operandul la continutul registrului;
S - scade
M - inmulteste
d - imparte
N - schimba semnul continutului registrului;
ST - memoreaza continutul registrului intr-o locatie de memorie.

	O operatie aritmetica inlocuieste continuturile registrului cu 
expresia rezultata. Locatiile temporare de memorie sunt asigurate de 
asamblor pentru un operand sub forma 'n', unde n este o cifra.

Intrare si iesire:
	Fisierul de intrare consta din mai multe expresii postfixate, 
fiecare pe o linie separata. Operanzii sunt litere iar operatorii sunt 
cei uzuali (+,-,*,/) plus operatia unara de negatie (@). Iesirea trebuie 
sa fie codul obiect care verifica conditiile:
1. Cate o instructiune pe linie, cu mnemonicele separate de operand (daca 
acesta exista) printr-un blanc;
2. O linie alba separata doua coduri generate pentru expresii diferite.
3. Ordinea initiala a operanzilor se pastreaza in cod;
4. Codul trebuie generat pentru un operator imediat ce este intalnit;
5. Se folosesc cat mai putine locatii temporare de memorie;
6. Pentru fiecare operator din expresie se genereaza numarul minim de 
instructiuni.

Exemplu:

Pentru intrarea
AB+CD+EF++GH+++
AB+CD+-

se genereaza iesirea:
L A
A B
ST $1
L C
A D
ST $2
L E
A F
A $2
ST $2
L G
A H
A$2
A $1
L A
A B
ST $1
L C
A D
N
A $1
=================================

	4. Un radioamator si-a construit o schema electronica pentru decodificarea
semnalelor Morse in conditii de zgomot. La fiecare moment de timp, aceasta
trimite catre calculator un numar intreg in intervalul 0..10 care este cu
atit mai mare cu cit probabilitatea ca la intrarea adaptorului sa fie
prezent un ton este mai mare.
        Semnalele Morse sint compuse din puncte si linii separate de spatii
de anumite durate. Punctele si liniile se manifesta prin prezenta tonului
in timp ce prin spatiu se intelege absenta tonului. In general vom numi
SEMN un punct sau o linie. Nu este permis ca un semn sa urmeze imediat
altui semn, sau ca un spatiu sa urmeze altui spatiu.

[ punct:* linie:*** spatiu mic:_ spatiu mare:___ ]

        Un punct are lungimea de un timp, o linie are lungimea de trei
timpi, un spatiu mic (dintre semne) are lungimea de un timp, iar un spatiu
mare (dintre litere) are lungimea de trei timpi.
Vom nota cu liniile cu L, punctele cu P, spatiile mari cu S, spatiile mici
cu s.
        Daca se memoreaza numerele trimise de catre adaptor catre
calculator de-a lungul a N momente de timp, se obtine un sir de numere
naturale in intervalul 0..10, de lungime N: a_1 a_2 ... a_N.
         Fie b_i = 10-a_i, pt. i=1..N
        Acest sir admite mai multe interpretari ca insiruire de semne
separate de spatii, unele interpretari fiind mai probabile decit altele.
Vom considera ca o interpretare este cu atit mai probabila cu cit are
scorul mai mare.
        Scorul unui punct pe pozitia i_ este a_i, scorul unui spatiu scurt
pe pozitia i_ este b_i, scorul unei linii care acopera pozitiile
i,i+1 si i+2 este a_i + a_(i+1) + a_(i+2), in timp ce scorul unui spatiu
lung care acopera pozitiile i,i+1 si i+2 este b_i + b_(i+1) + b_(i+2).
        Scorul obtinut de o interpretare se defineste ca fiind suma
scorurilor elementelor componente.
De exemplu, sirul
      1,10
poate fi interpretat ca fiind
      Ps    (scorul 1+0=1)
sau
      sP    (scorul 9+10=19)
Evident, a doua interpretare este mai probabila.

Limite:  N <= 1.000
Intrare:
Fisierul de intrare va contine mai multe seturi de date. Fiecare
set de date este format din doua linii, pe prima fiind numarul elementelor
din sir, iar pe a doua elementele sirului.

Iesire:
Pentru fiecare set de date de la intrare, veti scrie doua linii:
o prima linie pe care scrieti scorul interpretarii celei mai probabile
(adica de scor maxim), urmata de o linie pe care scrieti cea mai
probabila interpretare(utilizind simbolurile L,P,S,s).

Exemplu:
intrare:
2
1 10
5
9 8 9 3 4

iesire:
19
sP
37
LsP
========================================================

	5. Intr-un sistem de stocare a informatiei utilizatorii nu stiu exact ce
articol trebuie sa caute, dar pot da o descriere vaga a subiectului de care
sunt interesati. De aceea este foarte util un sistem de cautare care
sa detecteze unde apar mai multe cuvinte cheie grupate la distanta mica unul
de altul dar fara o ordine specifica de aparitie. Un articol care
indeplineste conditiile respective poate fi extras in intregime si examinat,
daca cuvintele dupa care s-a facut cautarea sunt alese cu grija avem sanse
mari ca subiectul textului respectiv sa fie pe tema care ne interesa.

  Trebuie sa scrieti o versiune mult simplificata a acestui program de
cautare: programul vostru accepta la intrare doua cuvinte W1 si W2
si doua numere m > 0 si n >= 0 si cauta printr-o lista de m articole
aparitia celor doua cuvinte W1 si W2 in acelasi articol cu cel mult n cuvinte
intre ele. Articolele in care aceasta conditie este indeplinita sunt afisate
pe terminal.

INTRARE:
  Fisierul de intrare contine mai multe seturi de date. Fiecare set de date
are pe prima linie cuvintele W1 si W2, urmate de numerele m si n, in aceasta
ordine. Restul setului este alcatuit din m articole, cate unul pe linie. Un
articol este un sir de cuvinte separate prin spatii sau semne de punctuatie.
(Un cuvant este o secventa de caractere alfabetice de lungime cel putin 1)
Semnele de punctuatie care pot sa apara sunt: ',' (virgula), '.' (punctul),
';' (punct si virgula), ':' (doua puncte), '?' (semnul intrebarii) si '!'
(semnul exclamarii). Sfarsitul unui articol este dat de end-of-line, cu
exceptia ultimului articol din ultimul set care este terminat cu end-of-file.
Pot sa apara mai multe spatii consecutive intre cuvinte. Articolele nu au o
lungime mai mare de 80 de caractere.

  Cautarea cuvintelor W1 si W2 nu se face case-sensitive. Astfel, cuvintele
"Fish" si "fish" sunt considerate identice.


IESIRE:
  Pentru fiecare set de date trebuie afisate acele articole in care W1 si W2
apar separate de cel mult n cuvinte. Afisati o linie goala dupa fiecare set de
date.

EXEMPLU:
Daca fisierul de intrare contine:

     solve proble 4 1
     This  is a hard problem to solve
     I had to   solve a much  more difficult problem before
     It is hard to   solve this problem
     This problem is hard to   solve
     going fish 5 2
     Some people are going to  catch fish
     Some fish are going to be caught
     A fish kill may   be going  to occur in the lake
     I am going to the lake to fish
     Fish out of water are going to die

atunci la iesire trebuie afisat:
     This is a hard problem to solve
     It is hard to solve this problem

     Some people are going to catch fish
     Some fish are going to be caught
---------------------------------------------------------------------------

	6. Faceti parte dintr-o echipa care proiecteaza un circuit logic
si trebuie sa scrieti un program care simuleaza comportarea lui. 
Circuitul poate fi compus din maxim sapte tipuri de elemente:

- TRUE - element notat cu litera T, fara nici o intrare si o singura 
	iesire Z pozitionata pe True;
- FALSE - element notat cu litera F, fara  nici o intrare si o singura 
	iesire Z pozitionata pe False; 
- NOT - element notat N, cu o intrare X si o iesire Z care reprezinta 
	complementul lui X;
- AND - element notat A cu doua intrari X,Y si o iesire Z care reprezinta 
	conjuctia logica a intrarilor;
- OR - element notat cu O cu doua intrari X,Y si o iesire Z care reprezinta 
	disjunctia logica a intrarilor;
- SYSTEM OUTPUT - element notat cu S, cu o intrare X.

    Scopul este scrierea unui program care evalueaza valoarea lui S dintr-o 
lista data de elemente si o tabela de conexiuni intre ele. Circuitul nu are 
feedbackuri.

Intrarea:
	Este formata dintr-o lista de elemente continnd cte un element pe 
fiecare linie. Ele sunt numerotate in ordinea in care apar la intrare. 
Ultima linie a listei contine un sir de trei caractere: EOE (End Of Elements).
    In continuare sunt date una sau mai multe linii care descriu legaturile 
dintre componentele circuitului. Fiecare linie contine 3 cmpuri separate 
prin cte un spatiu.
Primele doua cmpuri contin cte un numar intreg care specifica componente 
din lista de elemente; al treilea cmp contine un caracter, X sau Y care 
indica faptul ca iesirea din componenta indicata de primul cmp este legata 
la aceasta intrare a componentei indicate de al doilea cmp. Ultima linie a 
fisierului de intrare contine trei caractere EOC (End Of Connections).

Exemplu:
Circuitul aratat in figura este descris de setul de date de intrare:
T
F
T
N
A
O
2O
S
EOE
1 5 X
2 4 X
2 7 Y
3 6 Y
4 5 Y
5 6 X
6 7 X
7 8 X
EOC

Iesirea programului contine un mesaj care da valoarea componentei S a 
sistemului. Se presupune ca exista totdeauna o componenta S in circuitul 
de intrare.
Pentru circuitul dat in exemplul anterior, o iesire corecta este de forma:
SYSTEM OUTPUT are valoarea TRUE
===========================================================

	7. Programele care se executa in paralel pe un singur procesor apar ca fiind 
executate in acelasi timp, dar in realitate CPU (Unitatea Centrala de Calcul) 
alterneaza programele, executand cate un anumit numar de instructiuni din 
fiecare program dupa care trece la urmatorul. 
Problema consta in a simula acest tip de programare paralela cu pana la 10 
programe si sa determine iesirea pe care o vor scoate acestea.
	Programul care este in executie la un anumit moment, se spune ca 
"ruleaza" (running) in timp ce celelalte programe care asteapta sa fie 
prelucrate, spunem ca sunt "pregatite" (ready).
	Un program este o secventa de maxim 25 instructiuni, cate una pe 
linie, terminat cu instructiunea end. Instructiunile permise sunt:
    Tipul de instructiune	Sintaxa
	asignare		<variabila>=<constanta>
	iesire			print <variabila>
	Begin Exclusion		lock
	End Exclusion		unlock
	Oprirea executiei	end
O variabila este o litera mica a alfabetului latin; o constanta este un 
numar intreg din 0..99. Calculatorul dispune doar de 26 variabile care 
sunt gestionate de toate programele. Deci asignararile unei variabile 
intr-un program pot afecta valoarea pe care o tipareste alt program. 
Toate variabilele sunt initializate cu 0.
	Toate programele sunt asezate intr-o coada (first in - first out)
pentru executie. Ordinea initiala in coada este cea din fisierul de intrare. 
Aceasta ordine se poate modifica ca urmare a instructiunilor lock si unlock.
	Instructiunile lock si unlock pot fi folosite ori de cate ori un 
program vrea sa aiba acces exclusiv asupra variabilelor pe care le 
foloseste. Cele doua instructiuni apar in perechi avand intre ele cel putin 
o alta instructiune.
Instructiunea lock precede unlock si ele nu vor fi niciodata imbricate 
(deci un program nu poate avea doua instructiuni lock consecutive).
	Odata ce un program executa o instructiune lock, nici un alt program 
nu poate executa lock pana ce programul care are in lucru instructiunea 
lock nu o inchide cu o instructiune unlock. Daca un program care ruleaza 
incearca sa execute o instruciune lock in timp ce o alta instructiune lock 
este activa, acest program este intrerupt si pus la o coada de blocaj. 
Programele intrerupte in acest fel pierd restul portiei de timp pe care 
trebuiau sa-l mai aiba la executie. 
La executia unei instructiuni unlock, programul aflat in capul cozii de 
blocaj este mutat in capul cozii de programe pregatite. Prima instructiune 
pe care o va executa acest program cand va ajunge in executie va fi 
instructiunea lock pe care nu o putuse executa anterior. De remarcat ca 
programele isi asigura un protocol de excludere reciproca prin folosirea 
corecta a instructiunilor lock si unlock (Un program "rau" fara nici o 
pereche lock/unlock poate altera orice variabila doreste, in ciuda folosirii 
de catre alte programe a instructiunilor lock/unlock).

Intrare si iesire:
	Pe prima linie a fisierului de intrare se afla 7 numere intregi 
separate prin cate un spatiu. Acesti intregi reprezinta (in ordine): 
numarul programelor care urmeaza, timpi de executie pentru fiecare din 
cele cinci instructiuni (in ordinea data mai sus) si numarul de unitati 
de timp alocat fazei de rulare a unui program la un moment. 
Restul fisierului de intrare contine programele, compuse din instructiunile 
descrise mai sus.
	Toate instructiunile unui program incep de pe prima coloana a unei 
linii. Blancurile sunt ignorate in interiorul unei instructiuni.
Fiecarui program i se asociaza un numar de identificare bazat pe localizarea
sa in fisierul de intrare (primul program are ID=1, al doilea ID=2, etc.).
	Iesirea va contine iesirile date de instructiunile de tiparire, asa 
cum apar ele in timpul simularii. Cand este executata o instructiune de 
tiparire, programul vostru trebuie sa arate ID-ul programului care scrie, 
doua puncte (:), un spatiu si valoarea variabilei care se scrie.
Fiecare scriere are loc pe o linie separata.

Exemplu:
Intrare:			Iesire:
3 1 1 1 1 1 1			1: 3
a=4				2: 3
print a				3: 17
lock				3: 9
b=9				1: 9
print b				1: 9
unlock				2: 8
print b				2: 8
end				3: 21
a=3				3: 21
print a
lock
b=8
print b
unlock
print b
end
b=5
a=17
print a
print b
lock
b=21
print b
unlock
print b
end
=======================================

	8. Se urmareste transformarea unui cuvant sursa intr-un cuvant 
destinatie  folosind urmatoarele operatii permise:

COPY(a)           - copiaza caracterul a din sursa in destinatie
DELETE(a)         - sterge caracterul a din sursa
INSERT(a)         - insereaza caracterul a in destinatie
REPLACE(a,b)      - inlocuieste caracterul a cu caracterul b
                  (a dispare din sursa iar in destinatie apare b)
TWIDDLE(ab)       - secventa ab din sursa se transforma in ba in destinatie
                  (ab dispare din sursa si apare ba in destinatie)
KILL(secventa)    - dupa ce s-au efectuat toate operatiile necesare, se poate
                  elimina secventa ramasa (sufixul) din cuvantul sursa.

Exemplu: 
	Pentru transformarea cuvantului sursa ALGORITHM in cuvantul 
destinatie ALTRUISTIC, se poate folosi urmatoarea secventa de operatii:

operatie                           destinatie         sursa
----------------------------------------------------------------------------
copy(a)                                               algorithm
copy(l)                           al                  gorithm
replace(g,t)                      alt                 orithm
delete(o)                         alt                 rithm
copy(r)                           altr                ithm
insert(u)                         altru               ithm
insert(i)                         altrui              ithm
insert(s)                         altruis             ithm
twiddle(it)                       altruisti           hm
insert(c)                         altruistic          hm
kill(hm)                          altruistic

   Asociind cate un cost fiecarei operatii, problema cere sa se determine o
secventa de operatii de cost minim (suma costurilor operatiilor sa fie minima).

INTRAREA.
	Datele se citesc dintr-un fisier text al carui nume se citeste de la
tastatura si are urmatoarea structura:
- pe prima linie sunt sase numere naturale (byte) reprezentand, in ordine,
costurile operatiilor: copy, delete, insert, replace, twiddle, kill;
- fiecare dintre liniile urmatoare contine cate doua cuvinte separate
printr-un spatiu, reprezentand sursa respectiv destinatia.

IESIREA.
	In fisierul text TRANS.OUT se va afisa pentru fiecare pereche de
cuvinte sursa-destinatie un tabel ca si cel din exemplu, urmat de costul
transformarii.
=========================================

	9. Compania de calculatoare la care lucrati are in proiect o linie 
noua de calculatoare si doreste sa dezvolte pentru ele un sistem de operare 
tip Unix. Sarcina ta este sa scrii partea de formatare a functiei ls.
Programul va citi datele dintr-un fisier de intrare ls.in. Intrarea consta 
din o lista de (F) nume de fisiere care trebuiesc sortate (crescator conform
valorilor caracterelor ASCII) si formatate in (C) coloane pe baza lungimii 
(L) a celui mai lung nume de fisier. Numele de fisiere vor fi contine cel 
putin 1 si cel mult 60 caractere; formatarea lor se face aliniat la stanga.
Grosimea primei coloane este egala cu lungimea celui mai lung nume de fisier,
iar grosimea celorlaltor coloane este egala cu lungimea celui mai lung nume 
de fisier plus 2. 
Vor fi atat de multe coloane cate incap in 60 caractere.
	Programul va trebui sa utilizeze cat mai putine linii (R) posibil;
liniile vor fi umplute de la stanga la dreapta.

Intrare:
	Fisierul de intrare contine un numar indefinit de liste de nume de 
fisiere. Fiecare lista incepe cu o linie continand un singur intreg N 
(1<=N<=100). Urmeaza N linii, fiecare avand cate un nume de fisier, aliniat 
la stanga; toata linia (intre 1 si 60 caractere) este considerata ca 
apartinand acelui nume. Caracterele permise sunt cele alfanumerice 
(a..z, A..Z, 0..9) si cele din multimea {-,_,.} (fara virgula). Nu vor exista
caractere ilegale si nici linii goale.
	Imediat dupa ultimul nume de fisier urmeaza un numar N corespunzator 
urmatorului set, sau sfarsitul de fisier. Se cere citirea si formatarea 
tuturor multimilor citite din setul de intrare.

Iesire:
	Pentru fiecare set de nume de fisiere se va tipari o linie cu 60 
caractere '_' urmata de coloanele care contin numele de fisiere. Primele R 
fisiere sortate vor forma coloana 1; fisierele R+1,..,2R din sortare 
formeaza coloana 2, s.a.m.d.

Exemplu:
Pentru intrarea:
12
Weaser
Alfaalfa
Stimey
Buckwheat
Porky
Joe
Darla
Cototn
Butch
Froggy
Mrs._Crabapple
P.D.
19
Mr._French
Jody
Buffy
Sissy
Keith
Danny
Lori
Chris
Shirley
Marsha
Jan
Cindy
Carol
Mike
Greg
Peter
Bobby
Alice
Ruben

iesirea va fi:
----------------------------------------------------------------
Alfaalfa        Cotton          Joe             Stimey
Buckwheat       Darla           Mrs._Crabapple  Weaser
Butch           Froggy          Porky           P.D.
----------------------------------------------------------------
Alice       Chris       Jan         Marsha      Shirley
Bobby       Cindy       Jody        Mike        Sissy
Buffy       Danny       Keith       Mr._French  Ruben
Carol       Greg        Lori        Peter

=============================================================
