Proba 1:

        Problema 1 (Hexagon) - 30 puncte

	Toata lumea stie - daca nu sah - cel putin cum se misca dama pe o tabla
de sah. Sa ne imaginam insa ca avem o tabla sub forma unui hexagon.
Mai jos se afla o astfel de tabla de dimensiune 3, unde pe fiecare latura exista 
cate 3 spatii (notate cu 'x').

                           x   x   x
                         x   x   x   x
                       x   x   x   x   x
                         x   x   x   x
                           x   x   x

Atunci o dama - notata cu Q - va controla campurile notate cu 'o':

                           x   o   x
                         o   o   x   x
                       o   Q   o   o   o 
                         o   o   x   x
                           x   o   x

Pare ceva simplu: aici dama poate controla 3 diagonale (nu se poate actiona pe 
verticala), spre deosebire de tabla de sah clasica,  unde pot fi controlate
pana la 4 diagonale.

Problema: Fiind data o tabla hexagonala de dimensiune n, care este numarul 
minim de dame ce pot fi asezate, astfel incat fiecare camp al tablei sa fie 
controlat de cel putin o dama.

Intrare:
n - numarul de campuri de pe o latura a tablei, dat de la tastatura;
    (1<=n<=40);

Iesire: In fisierul de iesire 'hexa.out' sunt doua linii:
k - Numarul minim de dame care se pot aseza pe tabla astfel incat sa fie
    verificate conditiile:
   i) Orice camp al tablei este controlat de cel putin o dama;
  ii) Pe orice diagonala a tablei se afla cel mult o dama;
     (altfel spus, damele nu "se ataca" intre ele).
Pe a doua linie se afla o asezare a damelor, care reprezinta o solutie a 
problemei (restrictiile i,ii);
p_1 q_1 p_2 q_2 .. p_k q_k
   unde (p_i q_i) reprezinta pozitia damei i pe tabla (al q_i-lea element de pe 
linia p_i).

Exemplu:
Pentru intrarea
3
o iesire posibila este:
3
1 1 2 3 3 2

Timp de executie: 5" per test (pentru un calculator PC 386 40 MHz).

Observatii: 
Prin orice punct al tablei trec exact trei diagonale. 
Orice doua diagonale care trec printr-un punct fac intre ele un unghi 
de 120 grade.

                                           prof. Adrian ATANASIU
                                           Universitatea Bucuresti
---------------------------------------------------------------------

        Problema 2 (Numere prime) - 20 puncte

Conform teoremei lui Erdos, pentru orice n>1, intre n si 2n exista cel
putin un numar prim.
      Fiind dat k natural, k<=1300, sa se determine cel mai mic numar
n cu proprietatea ca in intervalul deschis (n,2n) sunt exact k numere prime.
Intrare (de la tastatura):
k
Iesire (ecran):
n
Cerinta: Programul trebuie sa rezolve problema in maxim 60" pentru fiecare test.
(PC-386, 40 MHz}

                                    prof. Adrian ATANASIU
                                    Universitatea Bucuresti
--------------------------------------------------------------------------
        Problema 3 (Hacker) - 25 puncte

	Un serviciu de informatii a surprins un mesager care transmitea
urmatorul text criptat:

alzfx mmdrw mmzff kuefi tt

Agentii pusi pe urma lui sunt atentionati sa afle tot ce pot, fara a da de
banuit ca au gasit o scurgere de informatii (altfel adversarul ar sti ca
este deconspirat si ar schimba modul de actiune). Ei isi fac meseria si reusesc 
sa gaseasca programul de criptare, care codifica un mesaj folosind un cuvant
cheie (acelasi sau altul pentru fiecare text). Gasesc chiar si cheia cu care 
s-a criptat textul de sus: este cuvantul 'martie'.
Iata si programul de criptare:
uses crt;
var
  ii,o:text;
  text,cheie:string;
  i,j,k,k1,n,m,p:integer;
begin
  clrscr;
  assign(ii,'vig_in'); assign(o,'vig_out');
  reset(ii);rewrite(o);
  readln(ii,text);
  {Textul se da cu litere mici, fara spatii; dupa un rand liber, se da cheia}
  readln(ii); readln(ii,cheie);
  n:=length(text); m:=length(cheie);
  for j:=1 to n do begin
    i:=ord(text[j])-97;
    k1:=j mod m;
    if k1=0 then k1:=m;
    k:=ord(cheie[k1])-97;
    p:=(i+k) mod 26;
    write(o,char(p+97));
    if (j mod 5)=0 then write(o,' ');
    if (j mod 55)=0 then writeln(o)
                    end;
    close(ii); close(o)
end.

	Pe baza acestor informatii, serviciul poate construi un program de 
decriptare. Astfel, au putut fi decriptate mesajele:

1) alzfx mmdrw mmzff kuefi tt					- cheie 'martie'
2) oayfr zuanm rfytu hnjyb juatu qyjnc uadya			- cheie 'unu'
3) rzqpd qdrig sqqtw uaiww kdtic onlbi ooddt qoobl aqvci uo	- cheie 'doi'
4) befik rkigj ikncx qorgm evqib dezbw izbxm lbepc fv		- cheie 'trei'
5) cumfn ressi prtjy bagrh ralzh jthkw tsxdu cagtu obhrl p	- cheie 'patru'

Incercati si voi.
Pentru fiecare mesaj decriptat se primesc 5 puncte.

                                        prof. Adrian ATANASIU
                                        Universitatea Bucuresti
-------------------------------------------------------------------------
