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

Proba 2:

4. CALUTI (25 puncte)

        Fie o tabla de dimensiune n*n, unde 3 <= n <=20, avand campurile
numerotate de la 1 la n*n. In colturi se afla doi cai albi, respectiv doi cai
negri.
      Sa se schimbe locurile cailor albi cu cei negri cu un numar MINIM de
mutari.
       Miscarea cailor este alternativa.

                              ----------------------
                              |1     |2     | 3    |
                              |   o  |      |   o  |
                              |      |      |      |
                              ----------------------
                              |4     |5     |6     |
                              |      |      |      |
                              |      |      |      |
                              ----------------------
                              |7     |8     |9     |
                              |   *  |      |   *  |
                              |      |      |      |
                              ----------------------

       In figura de mai sus s-au notat cu "o" caii albi si cu "*" cei negri.

       Dimensiunea tablei, n, se citeste de la tastatura.

       Scrierea rezultatului se va face in fisierul "solutie" care va contine
pe coloane diferite miscarile alternative ale cailor specificand la inceputul
fiecarei coloane despre ce cal este vorba. Miscarea cailor se marcheaza sub
forma n1-n2. Pe ultima linie se va scrie numarul de mutari.

       Exemplu:

n = 3

fisierul "solutie":

 o   *   o   *
1-6 7-2 3-8 9-4
6-7 2-9 8-1 4-3
7-2 9-4 1-6 3-8
2-9 4-3 6-7 8-1
16
 
Timp maxim de executie pentru un n dat, 15 secunde pentru 386 la 33MHz.
                     
                                       prof. Maria si Adrian Nita
                                      Liceul "Emanuil Gojdu" Oradea
-------------------------------------------------------------------------

5. TRIUNGHIURI (25 puncte)

	Fiind date n (3<= n <=100) puncte in plan, sa se determine trei
dintre acestea, care formeaza un triunghi ce contine numarul maxim de
puncte posibil, dintre cele ramase.

	Citirea se face din fisierul "trdate" avand structura:
n
x1 y1
x2 y2
.....
xn yn

unde n este numarul de puncte, iar xi, yi coordonatele punctelor.

	Solutia se scrie in fisierul "trsol" avand structura:
a b
c d
e f
p

unde (a,b), (c,d), (e,f) sunt coordonatele varfurilor triunghiului,
iar p numarul de puncte aflate in interiorul triunghiului. Se considera 
ca un punct aflat pe o latura triunghiului este in interior.


Timp maxim de executie 30 secunde pentru un 386 la 33MHz

                                         prof. Maria si Adrian Nita
                                        Liceul "Emanuil Gojdu" Oradea
 
----------------------------------------------------------------------

6. ARITMETICA  BAT-O  VINA ! (25 puncte)

	Fie o expresie de forma:

op nr_1 nr_2 ... nr_n = rezultat

unde:
op poate fi una dintre cele patru operatii elementare +, -, *, /
nr_1 ... nr_n sunt n numere intregi cuprinse intre 1 si 10.000.

op actioneaza asupra tuturor numerelor nr_i. Se cere sa se stabileasca
forma fiecarui nr_i (in sensul de a-i permuta cifrele ce-l compun), astfel
incat sa obtinem rezultatul aflat dupa semnul "=".

Exemplu:
+ 23 17 = 49

23 poate fi considerat in suma ca si 23 sau 32
17 poate fi considerat in suma ca si 17 sau 71

Solutia este:
+ 32 17 = 49


Citirea se face din fisierul "ardat" avand structura
op nr_1 nr_2 ... nr_n = rezultat

Atentie! In fisierul "ardat" pot fi mai multe seturi de date!!!

Solutia se va scrie int-un fisier "arsol" avand structura:
op cele n numere in forma corecte = rezultat

Atentie! In cazul in care fisierul de intrare contine mai multe seturi 
de date, in fisierul "arsol" vor fi mai multe linii, corespunzatoare
fiecarui set.

Pentru exemplul de mai sus:
"ardat"
+ 23 17 = 49

"arsol"
+ 32 17 = 49

In cazul in care nu exista solutie se va tipari, in fisier, mesajul
nu exista solutie

Timp maxim de executie/test 30 secunde

                                        
                                     prof. Maria si Adrian Nita
                                    Liceul "Emanuil Gojdu" Oradea
================================

Proba 3:


7. ARITMETICA (30 puncte)	

	Fie a/b o fractie ireductibila (1 <= a,b <= 1000, intregi). Sa se
scrie fractia sub forma unei fractii zecimale, punand in evidenta, daca este
cazul, perioada.
	Intrarea: fisierul "in" avand structura
a b
unde a si b reprezinta numaratorul, respectiv numitorul fractiei.
	Iesirea: fisierul "out" contine pe fiecare linie fractia zecimala
(folosind notatiile din matematica) corespunzatoare fractiei citite din
fisierul "in".
	
Exemplu:
Fisierul "in"
1 1
1 4
1 3
113 102

Fisierul "out"
1
0,25
0,(3)
1,1(0784313725490196)

	Timp de executie 30 secunde/test

                                         prof. Maria si Adrian Nita
                                           Liceul "Emanuil Gojdu"
                                                  Oradea

----------------------------------------------------------------------------

8. CONCURS (45 puncte)

	Examenul de admitere la Facultatea de Informatica se desfasoara
intr-o sala de forma patrat, in care in fiecare punct de coordonate intregi
este plasat cate un scaun, cu exceptia unui culoar ce inconjoara sala si
permite plasarea unor scaune pentru supraveghetori (tot in puncte de
coordonate intregi). Un supraveghetor sta pe un scaun si pe orice linie
dreapta ce trece prin pozitia sa el vede cel mult un candidat.
	Scrieti un program care sa citeasca de la tastatura un numar natural
n (3 <= n <= 50), care reprezinta dimensiunea salii de examen si afiseaza in
fisierul "concurs.out" pe prima linie numarul minim de supraveghetori
necesari astfel incat fiecare candidat sa fie supravegheat de cel putin
putin o persoana, iar pe urmatoarele linii indicele de linie, respectiv de
coloana, separati prin spatiu, pentru pozitia fiecarui supraveghetor.

De exemplu, pentru n=10, fisierul "concurs.out" poate fi:

3
1 1
1 2
2 1

	Timp de executie 30 secunde/test
  
                                            prof. Emanuela Mateescu
                                             Liceul de Informatica 
                                               "Grigore Moisil"
                                                     Iasi
=============================

Proba 4:

Problema 9: Impaturirea hartilor (45 puncte)

    O harta strategica este reprezentata ca o matrice cu n linii si m
coloane (1<=n , m<=100) fiecare componenta a matricii continand cota zonei
de teren corespunzatoare exprimata in metri de la nivelul marii, cota fiind
un numar natural. Determinati o modalitate de a impaturi harta astfel incat
deasupra sa se gaseasca o zona de arie maxima avand aceeasi cota. Plierea
hartii se poate face doar orizontal si vertical ( deci pe directii paralele
cu laturile hartiei ) si numai cu doua parti egale ( deci daca o dimensiune
a hartiei este impara, plierea de-a lungul laturii respective nu este
posibila ) . Pe ecran se va afisa aria zonei astfel determinate, cota
corespunzatoare, precum si codificarea sirului de plieri efectuate, folosind
urmatoarea conventie : se precizeaza mai intai directia ( H-orizontal
; V-vertical ) , apoi pozitia de la care se face plierea, apoi modul
de pliere ( L-partea stanga deasupra ; R-partea dreapta
deasupra ; U-partea de sus deasupra ; D-partea de jos deasupra
) , doua plieri consecutive fiind separate prin spatiu. Daca problema nu are
solutie se va afisa mesajul "Ghinion".
Restrictii de intrare/iesire : 
   Numele fisierului se va citi del a tastatura. Fisierul de intrare
contine pe prima linie n si m , dimensiunile hartiei ,
separate printr-un spatiu , iar pe urmatoarele n linii cate m
numere naturale care reprezinta cotele . 
   Fisierul de iesire se va numi harta.out si va contine :
   pe prima linie mesajul "Aria maxima" urmat de valoarea maxima a zonei de teren determinate
   pe a doua linie mesajul "Cota" urmat de valoarea cotei comune zonei determinate
   pe a treia linie codificarea sirului de plieri

sau

   mesajul "Ghinion", daca problema nu are solutie.

   Exemplu:

Pentru fisierul de intrare :

     3 4
     1 1 1 1
     2 2 2 2
     2 2 2 2

Fisierul de iesire va contine mesajul "Ghinion"

Pentru fisierul de intrare :

     4 4
     1 1 1 1
     2 1 3 4
     1 2 3 4
     2 2 2 2

Fisierul de iesire poate fi :

  Aria maxima 4
  Cota 1
  H2U H1U

sau

  Aria maxima 4
  Cota 2
  H3D H4D


   Atentie ! Daca exista mai multe solutii se va afisa una singura !

Timp de executie 30 sec/test.

------------------------------------------------------------------------

10.  VARFURILE UNOR FIGURI GEOMETRICE (30 puncte)

  Se considera punctele unei matrici infinite de triunghiuri echilaterale
ca cele de mai jos:

                                      1
                                    /   \
                                   2 --- 3
                                 /   \ /   \  
                                4 --- 5 --- 6
                              /   \ /   \ /   \
                             7 --- 8 --- 9 --- 10
                            /  \  /  \  /  \  /   \
                          11 -- 12 -- 13 -- 14 -- 15
                         /   \  /  \  /  \  /  \  /  \ 
                       16 -- 17 -- 18 -- 19 -- 20 -- 21
                      /  \   /  \  /  \  /  \  /  \  /  \ 
                     22 -- 23 -- 24 -- 25 -- 26 -- 27 -- 28          
        		. . . . . . . . . . . . . .			

	Observati ca grupuri ale acestor puncte formeaza varfurile unor
forme geometrice. 
	De exemplu:
{1,2,3} si {7,9,11} sunt varfurile unor triunghiuri
{11,13,26,24} si {2,7,9,18} sunt varfurile unor paralelograme
{4,5,9,13,12,7} si {8,10,17,21,32,34} sunt varfurile unor hexagoane 

	Scrieti un program care sa citeasca mai multe seturi de date,
sa le analizeze si sa hotarasca daca punctele sunt varfurile unei figuri
geometrice: triunghi, paralelogram sau hexagon. Pentru ca o figura sa fie 
corecta, trebuie sa indeplineasca urmatoarele conditii:
 1. fiecare latura sa coincida cu o muchie a matricii
 2. laturile figurii sa fie congruente

	Citirea se face din fisierul "input" care contine mai multe seturi
de date, fiecare set pe o linie. Exista cel mult 6 numere pe o linie, 
cuprinse in intervalul 1..32767.
	Rezultatul se tipareste in fisierul "output" si consta in listarea 
numerelor urmate de rezultatul analizei.

	Exemplu:

fisierul "input":
1 2 3
11 13 29 31
26 11 13 24
4 5 9 13 12 7
1 2 3 4 5 
47
11 13 23 25
 
fisierul "output":
1 2 3 sunt varfurile unui triunghi
11 13 29 31 nu sunt varfurille unei figuri acceptabile
26 11 13 24 sunt varfurile unui paralelogram
4 5 9 13 12 7 sunt varfurile unui hexagon
1 2 3 4 5 nu sunt varfurile unei figuri acceptabile
47 nu sunt varfurile unei figuri acceptabile
11 13 23 25 nu sunt varfurile unei figuri acceptabile

Timp de executie 30 sec/test.   

                                            Concurs ACM 1991
==========================

Proba 5:

11. UN ALT FEL DE HANOI (45 puncte)


     Fie 2 <= n <= 10 tije pe care se afla bile colorate. Culorile sunt
notate cu numere de la 1 la n. Sa se aranjeze bilele pe tije, astfel incat
pe fiecare sa fie n bile notate, de jos in sus, de la 1 la n. Pentru miscarea
bilelor se va folosi o tija ajutatoare, notata n+1. Pe fiecare tija numarul
maxim de bile este n. O bila se poate muta pe o alta tija, daca pe aceasta
tija este loc si daca deasupra bilei nu se afla o alta.
     Pozitia finala trebuie sa arate astfel:

             n       n      n       ...      n          |
            n-1     n-1    n-1              n-1         |
             .       .      .                .          .
             .       .      .                .          .
             .       .      .                .          .    <-- tije
             3       3      3                3          |
             2       2      2                2          |
             1       1      1                1          |
          ----------------------------------------------------
             1       2      3                n         n+1   <-- numarul
                                                                  tijei

     Configuratia initiala se citeste din fisierul "date" avand structura:
pe prima linie este numarul de tije  n
pe urmatoarele n linii sunt n numere de la 1 la n,separate prin spatii,
reprezentand asezarea bilelor pe fiecare tija, asezare citita de jos in sus.
      Iesirea se face in fisierul "rez" in care fiecare linie, cu exceptia
ultimei care contine un numar m, are forma
i x y

unde:
i reprezinta culoarea;
x si y numarul tijei de pe care, respectiv pe care, se muta bila; aceste
numere sunt cuprinse intre 1 si n+1.
m numarul total de mutari

Exemplu:
fisierul "date":
2                                         1     2     |
1 1                                       1     2     |
2 2                                     -----------------
                                          1     2     3
fisierul "rez":
2 2 3
2 2 3                                     2     2     |
1 1 2                                     1     1     |
2 3 1                                   -----------------
2 3 2                                     1     2     3
5                            

Timp de executie: 1min/test pe un 586 la 133MHz.

                                           prof.Maria si Adrian Nita
                                            Liceul "Emanuil Gojdu"
                                                    Oradea
----------------------------------------------------------------------

12. NUMERE (30 puncte)
                     (mai simplu decat pare!)

Sa se determine toate numerele naturale n < 60.000 cu urmatoarea proprietate:
daca 1 < m < n si daca m este natural si prim cu n, atunci m este numar
prim.

Scrierea in fisierul "numsol" cu structura:

n1
n2
...
nk

unde ni sunt numerele cerute.


Timp de executie 10 secunde.

                                             prof. Maria si Adrian Nita
                                               Liceul "Emanuil Gojdu"
                                                      Oradea
--------------------------------------------------------------------

Proba 6:


13. JOC 1 (40 puncte)

Fie o tabla de joc avand forma de patrat cu latura 2 <= n <= 6. Suprafata
de joc este alcatuita din n*n patrate numerotate cu 1, 2, ... ,n*n ca in 
figura de mai jos. Se considera de asemenea n*n piese, avand fiecare marimea
unui patratel, inscriptionate, pe fiecare latura cu cate un numar. Sa se 
aranjeze piesele pe tabla de joc, astfel incat pe laturile comune sa fie, 
respectiv, acelasi numar.

Exemplu:
Pentru n=3 fie tabla de joc:
                
                   ----------------------- 
                  |1      |2      |3      |
                  |       |       |       |
                  |       |       |       |
                  |-------|-------|-------|
                  |4      |5      |6      |
                  |       |       |       |
                  |       |       |       |
                  |-------|-------|-------|
                  |7      |8      |9      |
                  |       |       |       |
                  |       |       |       |
                   ----------------------- 
                  
si piesele:

                 -------      -------      ------- 
                |   3   |    |   3   |    |   5   |
                |2     3|    |3     4|    |5     4|
                |   2   |    |   3   |    |   3   |
                 -------      -------      ------- 

                 -------      -------      ------- 
                |   1   |    |   3   |    |   2   |
                |0     3|    |4     1|    |0     3|
                |   2   |    |   4   |    |   3   |
                 -------      -------      ------- 

                 -------      -------      ------- 
                |   3   |    |   4   |    |   1   |
                |3     5|    |3     3|    |3     0|
                |   3   |    |   3   |    |   5   |
                 -------      -------      ------- 


Solutia este:

                   ----------------------- 
                  |   1   |   4   |   1   |
                  |0     3|3     3|3     0|
                  |   2   |   3   |   5   |
                  |-------|-------|-------|
                  |   2   |   3   |   5   |
                  |0     3|3     5|5     4|
                  |   3   |   3   |   3   |
                  |-------|-------|-------|
                  |   3   |   3   |   3   |
                  |2     3|3     4|4     1|
                  |   2   |   3   |   4   |
                   ----------------------- 


Fisierul de intrare, "dat", are structura:

n                             dimensiunea tablei
V1 N1 E1 S1                   numerele inscriptionate pe
V2 N2 E2 S2                   fiecare piesa, citite in   
...........                   ordinea Vest, Nord, Est, Sud    
Vi Ni Ei Si                   Observatie: indicele i = n*n
                              ^^^^^^^^^^                     
                                           

Fisierul de iesire, "rez", are forma unei matrici, ale carei elemente 
reprezinta numarul casutei ocupate de piesele citite din fisierul "dat".

Pentru exemplul de mai sus, fisierul de intrare "dat" este:

3
2 3 3 2
3 3 4 3
5 5 4 3
0 1 3 2
4 3 1 4
0 2 3 3
3 3 5 3
3 4 3 3
3 1 0 5

iar fisierul de iesire "rez" este:

7 8 6
1 9 4
5 2 3


Observatii: - fisierul de intrare "dat" poate contine mai multe seturi de
^^^^^^^^^^    date;
            - piesele nu se rotesc pentru a fi puse pe tabla de joc.


Timp de executie 30 secunde/test (586 la 133MHz)

                                        prof. Maria si Adrian NITA
                                          Liceul "Emanuil Gojdu"
                                                  ORADEA

---------------------------------------------------------------------------

14.  JOC 2 (Arhicunoscut!) (35 puncte)

   N betisoare, sunt asezate unele peste altele. Se cere un program care
determina daca este posibil sa se ridice toate betisoarele. In caz afirmativ
se vor enumera betisoarele in ordinea ridicarii; altfel, se vor enumera doar
betisoarele care au putut fi ridicate.

PRECIZARI
1. Nici un betisor nu poate fi in pozitie verticala.
2. Se poate ridica un betisor doar daca deasupra lui nu se afla nici un alt
betisor.
3. Fiecare betisor este dat prin coordonatele capetelor (care sunt puncte
in spatiu).
4. Se cere o solutie.
5. Presupunem ca datele sunt corecte (fara validari!).
6. N < 51.

INTRAREA
Fiecare set de date se va afla intr-un fisier text al carui nume se
citeste, cu urmatoarea structura: 
	pe prima linie N, numarul de betisoare; 
	pe fiecare din urmatoarele N linii va fi cate un betisor dat 
	prin 6 numere (reale) reprezentand coordonatele capetelor 
	(x1, y1, z1), respectiv (x2, y2, z2). Aceste numere reale sunt
	cuprinse in intervalul [-100, 100].

EXEMPLUL 1
4
0  0  0  3  0  0 
2  3  1  2 -1  5
6  2  0  5  0  0
0  2  0  3  2  0

EXEMPLUL 2
5
0  0  0  3  0  0
0  2  0  3  2  0
5  0  0  6  2  0
2 -1  1  2  3 -1
4  0  0  4  3  1

IESIREA 
Pentru fiecare set de date se va scrie raspunsul in fisierul text "maroc",
respectand formatul de mai jos.

Pentru exemplul 1:

6  2  0  5  0  0
2  3  1  2 -1  5
0  0  0  3  0  0 
0  2  0  3  2  0

Pentru exemplul 2:
4  0  0  4  3  1
5  0  0  6  2  0

Pe ecran, pentru fiecare set de date se va scrie "Da" - in cazul in care se
pot ridica toate betisoarele, sau "Nu" - in caz contrar. 

Pentru exemplul 1:
Da
Pentru exemplul 2:
Nu

Timp de executie 30 secunde/test (586 la 133MHz).

                                               prof. Delia GARBACEA
===========================

Proba 7:


15. PERECHI (45 puncte)

	Sa se determine toate perechile de numere naturale (a, b) pentru care:
        q * q + r = n
unde q si r sunt respectiv catul si restul impartirii lui a*a+b*b la a+b.
	Fisierul de intrare "pin" va avea pe fiecare linie cate o valoare
<= 10.000 corespunzatoare unui "n".

	Fisierul de iesire "prez" va avea structura:

n                  numarul "n" citit din fisierul "pin"
a1 b1
a2 b2
....              perechile de numere naturale cerute
ai bi
t                  numarul perechilor gasite pentru un "n" citit

Observatie:        in cazul in care pentru un "n" citit nu exista nici o
^^^^^^^^^^^        pereche de numere (a, b) se va scrie in fisierul "prez",
                   mesajul "nu exista perechi (a, b)"


      Timp de executie 30 secunde/test (586 la 133MHz)
                                           prof. Maria si Adrian Nita
                                             Liceul "Emanuil Gojdu"
   						     Oradea
         
-------------------------------------------------------------------------

16. DREPTUNGHIURI (30 puncte)

        Fie n dreptunghiuri, cu laturile paralele cu axele de coordonate, date
prin elementele "colt stanga sus" (xs, ys) si "colt dreapta jos" (xd, yd). Sa
se precizeze dreptunghiurile care se intersecteaza.
        Citirea se face din fisierul "din" avand structura:

1 xs1 ys1 xd1 yd1
2 xs2 ys2 xd2 yd2
................
n xsn ysn xdn ydn

unde:
1, 2, ..., n     reprezinta numerele de ordine ale dreptunghiurilor
xsi ysi xdi ydi  reprezinta coordonatele "colt stanga sus", "colt dreapta
                 jos" dreptunghiului "i"  
                 
        Afisarea se face in fisierul "drez" care contine n linii de forma:

i d1 d2 d3 ... dk

cu semnificatia: dreptunghiul i se intersecteaza cu dreptunghiurile
                 d1, d2, ..., dk


Observatii:      0 <= n <= 100
^^^^^^^^^^^      0 <= xsi, ysi, xdi, ydi <= 1000  (intregi)
                 doua dreptunghiuri se intersecteaza daca:
                        - cel putin cate o latura se intersecteaza; 
                        - au un cel putin un varf comun;
                        - au cel putin o latura comuna;
                 daca dreptunghiul i nu se intersecteaza cu nici un alt 
                 dreptunghi, atunci pe linia respectiva va aparea scris 
                 doar "i"
Exemplu:         
^^^^^^^^
Fie fisierul "din":

1 1 6 10 1
2 2 9 4 5 
3 8 11 13 6
4 13 4 15 2
5 5 9 17 3
6 4 16 5 14 

Fisierul "drez" va fi:

1 2 3 5
2 1
3 1 4 5
4 5
5 1 3 4
6
 
      Timp de executie 30 secunde/test (586 la 133MHz)

                                            prof. Maria si Adrian Nita
                                             Liceul "Emanuil Gojdu"
   						     Oradea

---------------------------------------------------------------------------  
