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