Etapa 1: 15 ianuarie 1997

Problema 1
Problema 2
Problema 3
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:

  1. Orice camp al tablei este controlat de cel putin o dama;
  2. 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.

Se cer DOAR mesajele initiale si mesajele decodificate corespunzatoare !

Prof. Adrian ATANASIU
Universitatea Bucuresti
[Index] [Informatii importante!] [Participanti] [Baraj] [Probleme baraj] [Etapa 2]