Baraj II

         
Subiecte

         
			Olimpiada Nationala de Informatica
				Baraj ziua 2
				Problema 4


Cautatorul de mine					Punctaj: 50 puncte.

  In familia Adams urmeaza sa se sarbatoreasca ziua de nastere a unchiului 
Fester; cei doi copii ai familiei Adams, cunoscand pasiunea lui pentru 
explozii, s-au gandit sa-i daruiasca un nou joc.
  Jocul consta dintr-o tabla formata din N*N cutii (1<=N<=20), fiecare fiind 
identificata prin doua numere i, j (1<=i,j<=N), reprezentand linia, respectiv 
coloana pe care se afla cutia. Cutiile pot contine unul dintre urmatoarele 
tipuri de obiecte:
- o bomba;
- o hartie in care este scris numarul de cutii vecine care contin bombe (se 
considera cutii vecine acele cutii din tabla ale caror coordonate difera 
prin maxim o unitate de cele ale cutiei curente);
  Deschiderea unei cutii care contine o bomba duce la explozia acesteia si 
implicit la terminarea nefericita a jocului; deschiderea unei cutii care 
contine o hartie permite citirea informatiei de pe ea.
  Cadoul nu ar fi complet daca unchiul Fester ar fi nevoit sa deschida si 
toate cutiile care nu contin bombe; din punctul lui de vedere asta ar fi o 
activitate ingrozitor de plictisitoare si iritanta. In consecinta, scopul 
celor doi copii este de a deschide cat mai multe cutii "pasnice" si de a 
marca cat mai mult cutii "periculoase"; scrieti un program care sa rezolve 
aceasta problema. Initial sunt cateva cutii deschise si cateva cutii marcate 
corect (cu bombe). Situatia initiala va fi citita din fisierul de 
intrare INPUT.TXT, cu urmatorul format:
N
C11 C12 ... C1N
C21 C22 ... C2N
.
.
.
CN1 CN2 ... CNN
unde:
- N indica dimensiunea tablei de joc;
- Cij (1<=i,j<=N) poate avea urmatoarele valori:
  - intre 0 si 8 daca cutia din pozitia i,j este deschisa si contine o 
    hartie (pe care e scris numarul Cij);
  - 9 daca cutia nu este deschisa inca si nu se stie nimic despre ea;
  - 10 daca cutia contine o bomba si a fost marcata.

In continuare jocul se va desfasura interactiv, dupa urmatoarele reguli:
a)  programatorii in Pascal trebuie sa includa in programul lor unit-ul 
  COMM.TPU, care contine urmatoarele declaratii:
- procedure InitializareJoc;  care trebuie apelata o singura data la 
  inceputul jocului. 
- function Deschide(x,y:integer):integer;  apelul ei semnifica deschiderea 
  cutiei de la pozitia x,y; functia va returna:
  - numarul inscris pe hartie daca cutia contine o hartie;
  - 13 daca cutia continea o bomba care tocmai a explodat, deci a generat 
    terminarea jocului;
- function Bomba(x,y:integer):integer;  apelul ei semnifica marcarea cutiei 
  de la pozitia x,y; functia va returna:
  - 10 daca cutia continea intr-adevar o bomba;
  - 13 daca cutia nu continea o bomba (si in acest caz jocul este terminat);
- procedure TerminareJoc;  trebuie apelata la incheierea fericita a jocului, 
  adica, atunci cand nu mai sunt cutii al caror continut este necunoscut, 
  sau cand pentru cele ramase nu se mai poate deduce continutul.
b)  programatorii in C vor trebui sa includa in programul lor header-ul
  COMM.H care contine urmatoarele declaratii (cu aceleasi semnificatii ca 
  mai sus):
- void InitializareJoc(void);
- int Deschide(int x, int y);
- int Bomba(int x, int y);
- void TerminareJoc(void);

Note: 
1.  Atunci cand dumneavoastra va verificati programul in timpul concursului, 
  aceste proceduri si functii afiseaza un mesaj corespunzator pe ecran si 
  citesc de la tastatura valoarea pe care trebuie sa o returneze. Folosirea 
  lor este obligatorie!
2.  Fisierele COMM.PAS, COMM.TPU, COMM.H se gasesc in directorul: C:\BOMBE.
3.  Jocul se incheie nefericit, in una din urmatoarele situatii:
  - a fost deschisa o cutie care contine o bomba;
  - a fost marcata o cutie care nu contine o bomba;
  - continutul unei cutii a fost determinat de programul dumneavoastra in 
    mod aleator (continutul nu poate fi dedus prin rationament logic, 
    din informatiile existente).

Exemple:
1. INPUT.TXT	2. INPUT.TXT
3		3
9  9  9		1 10  9
9 10  9		1  9  9
1  9  9		0  9  9

  Pentru fisierele de intrare de mai sus (1, respectiv 2), programul 
dumneavoastra trebuie sa contina apelurile de mai jos (setul 1, respectiv 2):
1.					2.
InitializareJoc;			InitializareJoc;
Deschide(2,1)  	{=> 1}			Deschide(2,2);		{=>11}
Deschide(1,1)  	{=> 1}			Deschide(3,2);		{=>11}
Deschide(1,2)  	{=> 2}			Bomba(3,3);		{=>13}
Bomba(1,3)     	{=>10}			{Terminare nefericita}
Deschide(3,1)		{=>11}
TerminareJoc;
{terminare fericita}

Nota: Intre acolade au fost specificate valorile returnate de functii 
(valori care au fost introduse de la tastatura)!


			Olimpiada Nationala de Informatica
			  Timisoara, 23-30 martie 1997

				BARAJ, ZIUA 2
			         PROBLEMA 3 

Blocuri paralelipipedice					Punctaj: 50p

  Pe o suprafata plana xOy cad pe verticala n (1<=n<=99) blocuri 
paralelipipedice dreptunghice de inaltime 1. Laturile bazelor sunt paralele 
cu axele de coordonate. Ele au pe cele doua baze un adeziv puternic. Pentru 
fiecare bloc, numerotat in ordinea caderii (1,2,...,n), se cunosc 
coordonatele x,y (0<=x,y<=100) ale proiectiei pe plan a coltului stanga jos,
precum si lungimea si latimea bazei (numere naturale nenule, mai mici 
decat 100). Daca un bloc cade peste un alt bloc aflat pe un anumit nivel, 
el va ramane pe nivelul imediat superior, atunci cand suprafata de contact 
este de minimum 1. Se cere:
a) inaltimea gramezii;
b) numerele de ordine ale blocurilor ce au proprietatea ca pot fi extrase, 
   separat, din intreaga gramada,  fara ca gramada ramasa sa se prabuseasca;
c) numerele de ordine ale blocurilor (in numar maxim) ce pot fi extrase 
   simultan de pe fiecare nivel, incepand cu primul (baza gramezii), in 
   ordinea ascendenta a nivelelor, fara ca gramada ramasa sa se prabuseasca.

INTRARE:
  Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
n		- numarul de blocuri 
x1 y1  lx1 ly1	- coordonatele proiectiei coltului stanga jos, lungimea si 
		  latimea bazei blocului 1, separate printr-un spatiu
. . . . . . . . . . 
xn yn  lxn lyn	- cordonatele proiectiei coltului stanga jos, lungimea si 
		  latimea bazei blocului n, separate printr-un spatiu

IESIRE:
  Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
h			- inaltimea gramezii
t1 t2  ...  tp		- blocurile ce au proprietatea de la punctul b), 
			  separate printr-un spatiu	
Urmeaza h linii de forma:
z1 z2  ...  zq		- blocurile ce pot fi extrase simultan de pe 
			  fiecare nivel, de la 1 la h, separate printr-un 
			  spatiu. Daca pe un nivel nu se poate extrage nici 
			  un bloc, atunci pe linia corespunzatoare in fisierul
			  de iesire se va afisa cifra 0.
In cazul c), daca exista mai multe solutii, se va afisa doar una.  

Exemplu 
Pentru fisierul de intrare INPUT.TXT
8
1  1  3  2
5  1  4  2
10  1  3  2
8  2  3  2
3  2  3  2
5  3  5  3
15  1  3  2
8  5  4  3
Iesirea in fisierul OUTPUT.TXT este
4
1  2  3  4  5  7  8
1  3  7
4 
0 
8
	Nota: 
	Datele de intrare se presupun corecte
	Timp de executie 10 secunde/test

 
 
         
Clasament

          Clasamentul dupa Baraj I la clasele: a IX-a, a X-a, a XI-a, a XII-a
 

Pentru informatii scrieti la:
IntraNet - IntraNet@litm.sorostm.ro