
	1. Wily Hacker gaseste pe biroul sefului sau schema de criptrare a
mesajelor importante primite de acesta (vezi figura). De asemenea, gaseste in
computerul sefului fisiere cu texte criptate insotite de cheile de criptare
asociate.
Ideea care ii vine este sa scrie un program pentru decriptarea acestor mesaje.

     M1         M2                                      M3        M4
     |          |                                       |         |
     \/         \/                                      \/        \/
K1-> <    K2 -> &                                 K3 -> +   K4 -> <
     |          |                                       |         |
     |----------|--------> + <--------------------------|         |
     |          |----------|-----------> + <------------|---------|
     |          |          \/            |              |         |
     |          |  K1+K2-> <             |              |         |
     |          |          |             \/             |         |
     |          |          |-----------> & <------------|---------|
     |          |          |             |              |         |
     |          |          |             \/             |         |
     |          |          |     K3+K4-> <              |         |
     |          |          \/            |              |         |             
     |          |          & <-----------|              |         |
     \/         |          |             \/             \/        |
     + <--------|----------|--------------------------> +         |
     |          \/         \/                           |         \/
     |          + <-------------------------------------|-------> +
     |          |                                       |         |
     \/         \/                                      \/        \/
K4-> <     K3-> &                                  K2-> &    K1-> <
     |          |                                       |         |
     \/         \/                                      \/        \/
     C1         C2                                      C3        C4
       
	Wily a citit o carte despre metodele moderne de criptare; aici se arata
ca acum circa doua decenii criptografia a devenit subiectul multor aplicatii
legate de computer security. Tot mai multe persoane au devenit interesate in
a-si asigura confidentialitatea propriilor mesaje. Un cifru este o metoda 
secreta de transformare a textelor clare (mesaje) in texte cifrate (criptograme).
Aceasta operatie, numita criptare, este controlata de o cheie de criptare.
Bineinteles, trebuie sa existe si o transformare inversa, numita decriptare,
care transforma criptograma in mesaj, folosind o cheie de decriptare asociata
cheii de criptare.
         Wily remarca ca algoritmul din figura cripteaza un mesaj M de 64 biti
intr-o criptograma c de 64 biti folosind o cheie de control K tot de 64 biti.
functia de criptare foloseste 3 tipuri de operatii:
- sau exclusiv, marcat cu simbolul +;
- adunarea modulo 2^16, marcata cu simbolul &;
- deplasarea circulara la stanga, cu un numar de pozitii date de cheia K, 
	marcata cu simbolul <.
Toate aceste functii lucreaza cu operanzi pe 16 biti.
Algoritmul foloseste urmatoarele notatii:
  - Mi, i=1,4 reprezinta cele patru blocuri de cate 16 biti ale textului clar;
  - Ci, i=1,4 reprezinta cele patru blocuri de cate 16 biti ale criptogramei;
  - Ki, i=1,4 reprezinta cele patru blocuri de cate 16 biti ale cheii de 
criptare.
	Dupa multa munca, Wily gaseste schema corecta de decriptare si metoda
prin care poate obtine cheile de decriptare.
	Problema cere sa se scrie un program care obtine textele clare 
corespunzatoare criptogramelor si cheile de descriptare, descopreind o anumita
schema de lucru, similar cum a facut Wily Hacker.

Intrare:
	Fisierul de intrare contine mai multe grupuri de texte criptate si chei;
fiecare linieconsta dintr-o criptograma formata din 16 caractere hexazecimale
(64 biti) si, dupa cel putin un blanc, cele 16 caractere hexazecimale (64 biti)
ale cheii de criptare.

Iesire:
	In fisierul de iesire (A.OUT) se vor scrie caracterele ASCII ale 
textului clar, cate un mesaj pe fiecare linie, reprezentand rezultatul 
decriptarii mesajelor.

Exemplu:
	daca in A.DAT se afla
85bfa0242caa796e    1111222233334444
4c0d17278cbf4222    abcdabcdabcdabcd

	iesirea va fi de forma:
TEACHERS
STUDENTS
================================================
 
	2. Problem G {Double Trouble} Serviciile secrete din Hudonia au o mare
atractie pentru numerele ciudate. Aceasta atractie este atat de mare incand 
Hudonia este in incurcatura. Numerele pe care le cauta au urmatoarea proprietate.
La rotirea spre dreapta a unui astfel de numar (adica daca se ia ultima lui
cifra si se pune in fata) ceea ce sa obtine este un nuar de doua ori mai mare.
   Numerele cu aceasta proprietate au fost numite de ei dublu-incurcate
(double trouble). De exemplu X=421052631578947368 este un numar dublu-incurcat
pentru ca 2X=842105263157894736 este o rotire spre dreapta a lui X.
Numarul X este dublu-incurcat in sistemul de numeratie cu baza 10. Orice sistem
p>=2 de numeratie are multe astfel de numere. In baza 2 de exemplu, numerele
01 si 0101 sunt dublu-incurcate (de remarcat ca aici zerourile de la inceput
capata o importanta deosebita). 
	Serviciul secret din Hudonia cauta cele mai mici numere dublu-incurcate
din anumite baze de numeratie. In sistemul binar de exemplu, cel mai mic numar 
dublu-incurcat este 01. In sistemul zecimal este 052631578947368421. 
	Sarcina unui bun patriot hudonian este de a scrie un program care sa
calculeze, pentru o baza de numeratie p cel mai mic numar dublu-incurcat.
Intrare:
	Fisierul de intrare consta dintr-o secventa de numere, cate unul pe linie,
terminate cu end-of-file. Fiecare numar este mai mic de 200.
Iesire:
	Fisierul de iesire da, pentru fiecare numar p din fisierul de intrare
cel mai mic numar dublu-incurcat care se poate scrie in baza p (inclusiv
zerourile din fata - daca sunt necesare). Modalitatea de scriere este cea din
exemplul de mai jos, in aceeasi ordine ca la intrare. Cifrele din baza p sunt 
reprezentate zecimal, fiecare cifra (inclusiv ultima) fiind urmata de un singur 
spatiu.
Exemplu: Pentru intrarea: 
2
10
35

   iesirea va fi
Pentru baza 2 numarul dublu-incurcat este
0 1
Pentru baza 10 numarul dublu-incurcat este
0 5 2 6 3 1 5 7 8 9 4 7 3 6 8 4 2 1
Pentru baza 35 numarul dublu-incurcat este
11 23

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

	3. Dandu-se un numar intreg N (2 <= N < 100) sa se gaseasca descompunerea
sa in factori primi.
Intrare:
un fisier numit C.IN care contine mai multe numere, cite unul pe linie, 
ultima linie continind 0.
Iesire:
	Se va face la terminal; pentru fiecare numar din fisierul de intrare se
va afisa o linie continind numarul n urmat de exponentii fiecarui numar prim 
in descompunerea lui n!.

Exemplu:
fisierul de intrare:
5
53
0
fisierul de iesire:
  5! =  3  1  1
 53! = 49 23 12  8  4  4  3  2  2  1  1  1  1  1  1  1
========================================

    4. Incepem cu precizarea ca toate numerele care intervin in enuntul
care urmeaza sunt numere naturale pozitive. Fiind dat numarul N numim partitie a 
lui N o secventa de numere x1<x2<...<xk impreuna cu o secventa de numere n1,..,
nk  satisfacnd egalitatea n1x1+n2x2+...+nkxk=N. Se cere sa se determine o 
partitie a numarului N care indeplineste urmatoarele conditii:
1) orice numar cuprins intre 1 si N inclusiv, se reprezinta in mod unic ca o 
suma partiala a acestei partitii;
2) partitia contine un numar maxim de elemente distincte.
Exemplu: Pentru n=7 se pot genera partitiile:
7=7x1
7=1x1+3x2
7=1x1+1x2+1x4
7=3x1+2x2
Partitia 7=3x1+2x2 nu indeplineste conditia (1) deoarece 2 se poate scrie 
2=2x1=1x2, deci reprezentarea nu este unica. Primele 3 partitii indeplinesc 
conditia (1) si drept urmare partitia 7=1x1+1x2+1x4 este cea cautata.
=========================================================  Concurs ACM 1995, Regiunea Nord-Central

	5. Multe persoane sunt familiarizate cu cifrele romane pentru numere 
relativ mici. Simbolurile I,V,X,L,C,D,M reprezinta respectiv numerele 1,5,10,
50,100,500 si 1000. Pentru a reprezenta alte valori, aceste simboluri se
alatura si se aduna conform anumitor reguli. De exemplu numarul 3 se reprezinta
prin III iar 73 prin LXXIII. Exceptiile la regula apar la numerele care au
una din cifre 4 sau 9; aici 4 se scrie IV, 9 - IX, 40 - XL, 90 - XC, 400- CD,
900 - CM. Astfel reprezentarile cu cifre romane pentru 24,39,44,49 si 94 sunt
respectiv XXIV,XXXIX,XLIV,XLIX,XCIV. La fel mai departe.
	Prefetele multor carti au paginile numerotate cu numere romane, pornind
cu I pentru prima pagina. Cat de multe caractere I,V,X,L,C sunt necesare pentru
a numara paginile prefetei ? De exemplu, o prefata cu 5 pagini va folosi numerele
romane I,II,III,IV,V deci vor fi necesare 7 caractere I si 2 caractere V.
Intrare:
O secventa de numere intregi din intervalul 1,399, cate unul pe o linie. 
Pe ultima linie este 0. Pentru aceste numere (exceptie 0) sa se determine numarul
tipurilor diferite de caractere necesare pentru a numerota prefata cu numere
romane.
Iesire:
Pentru fiecare intreg din fisierul de intarre, se va scoate o linie continand 
numarul si numarul de caractere de tipul cerut, sub forma aratata in exemplu:
Exemplu:
Intrare:
1
3
20
99
0
Iesire;
1: 1 I, 0 V, 0 X, 0 L, 0 C
3: 3 I, 0 V, 0 X, 0 L, 0 C
20: 28 I, 10 V, 14 X, 0 L 0 C
99: 140 I, 50 V, 150 X, 50 L, 10 C
=====================

	6. Spunem despre un numar ca are proprietatea sufixului daca el apare ca sufix
al patratului sau (adica cifrele sale apar la sfirsitul sirului de cifre ce
reprezinta acel numar ridicat la patrat). De exemplu, 5, 76 si 9376 au
proprietate sufixului IN BAZA 10. Este clar ca baza in care lucram este
importanta, un numar poate avea proprietatea sufixului intr-o baza si poate sa
nu o aiba in alta baza.

  Ceea ce vi se cere este sa scrieti un program care sa testeze daca numerele
primite la intrare au proprietatea sufixului in baza specificata. Fisierul de
intrare contine pe fiecare linie a sa cate un numar natural n (n<=MAXINT),
urmat de una sau mai multe baze b_1, b_2, ..., b_k. Pentru fiecare valoare a
lui n trebuie afisata o linie cu mesajul:
               NUMARUL n :
unde "n" este inlocuit de valoarea curenta a lui n, dupa care, pentru fiecare
baza b_i trebuie afisat unul dintre mesajele:
               ARE PROPRIETATEA SUFIXULUI IN BAZA b_i
sau
               NU ARE PROPRIETATEA SUFIXULUI IN BAZA b_i
pe cate o linie separata pentru fiecare b_i. O linie libera trebuie sa SEPARE
mesajele ce corespund la valori diferite ale lui n.
    NOTA. Toate valorile din fisierul de intrare precum si valorile afisate la
iesire sunt numere in baza 10.
Exemplu:
Daca fisierul de intrare contine doua linii cu urmatorul continut:
9 2 6 10
5 10 33
iesirea trebuie sa arate ca textul cuprins intre liniile orizontale:
---------------------------------------------------------------------------
NUMARUL      9 :
               NU ARE PROPRIETATEA SUFIXULUI IN BAZA 2
               ARE PROPRIETATEA SUFIXULUI IN BAZA 6
               NU ARE PROPRIETATEA SUFIXULUI IN BAZA 10
NUMARUL      5 :
               ARE PROPRIETATEA SUFIXULUI IN BAZA 10
               NU ARE PROPRIETATEA SUFIXULUI IN BAZA 33
-------------------------------------------------------------------------

	7. Doua orase T1 si T2 sunt legate printr-o cale ferata dubla. Distanta
dintre T1 si T2 este de d metri. Trenurile pleaca la intervale regulate de
timp din cele doua orase: din T1 spre T2 la fiecare t1 secunde, iar din T2 
spre T1 la fiecare t2 secunde. Trenurile care pleaca din T1 au o viteza de 
v1 m/sec, iar cele care pleaca din T2 merg cu v2 m/sec.
  Problema cere sa scrieti un program care calculeaza numarul de "intalniri"
ale trenurilor care leaga T1 de T2 in intervalul de timp [0,tf], tf dat in
secunde.
Conventii:
- la momentul 0 din T1 si T2 pleaca simultan cate un tren;
- Datele de intrare si iesire sunt numere intregi.
Intrare:
Fiecare set de date de intrare ocupa o linie in fisierul de intrare si are forma:
d v1 v2 t1 t2 tf
Iesirea:
  Programul va scrie pe ecran numarul de "intalniri", sub forma:
Set de date k:
n
Exemplu:
Pentru fisierul de intrare:
10 5 5 1 1 2
fisierul de iesire este:
Set de date 1:
6

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

	8. Se considera o sfoara care se incaleca de mai multe ori. Fie A, B
capetele sale. Parcurgem sfoara de la A catre B. Vom nota cu 0 ori de ori
trecem sfoara pe dedesupt, respectiv cu 1 ori de cate ori trecem pe deasupra.
Obtinem astfel un anumit vector avand componentele 0 si 1. Parcurgand inca o 
data sfoara de la A catre B, pentru fiecare trecere pe deasupra, notam a cata
trecere pe dedesubt ii corespunde.
	Fie acum doi vectori ca mai sus, prin care vom codifica o anumita
sfoara. Se cere:
a) Sa se verifice validitatea datelor.
b) Ce se intampla daca tragem de capetele sforii?

     Exemple:
-datelor de intrare:
111000
123
le corespunde sfoara
       |A
       |
       |
 /-----|-------\
 |     |1      |
 |     |       |
 \-----|-------|-------
       |2      |3     B
       \-------/
deci raspunsul va fi:
datele sunt valide
sfoara se desface.

-datelor de intrare:
101010
231
le corespunde sfoara

	|A
	|
   /----|-----\
   |    |2    |
   |    |     |
   |    |     |
   \----------|---------
	|1    |3       B
	|     |
	|     |
	\-----/
deci raspunsul va fi:
datele sunt valide
sfoara se innoada.
====================================
