Etapa 6: 19 februarie 1997

Problema 1
Problema 2
Problema 1: 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 sec/test pe un 586 la 133MHz.
prof. Maria si Adrian Nita
Liceul "Emanuil Gojdu"
Oradea
Problema 2: Joc 2 (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.
    7. 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
    Liceul de Informatica
    Brasov
    [Index] [Informatii importante!] [Participanti] [Etapa 5] [Etapa 7]