Etapa 2: 22 ianuarie 1997

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

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

Problema 3: 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 (386 - 33MHz).

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

[Index] [Informatii importante!] [Participanti] [Etapa 1] [Etapa 3]