|
Olimpiada Nationala de Informatica
Timisoara, 23-30 martie 1997
CLASA a IX-a
ZIUA 2
Problema 3
Spargatorul de ... banci! Punctaj: 50p
Cladirea unei banci cu n (1<=n<=1000) nivele are scari de acces pe doua
parti notate cu s (stinga) si d (dreapta). Pe scari, la anumite nivele se afla
posturi de paza. La fiecare nivel sunt plasate seifuri cu saci de bani (cel
mult 100 de saci la un nivel).
Un hot poate patrunde in cladire pe una din cele doua usi de la parter si
intentioneaza sa ajunga pe acoperis, unde este asteptat de un complice cu un
elicopter. Evitand cu dibacie posturile de control, hotul traverseaza unele
nivele (intr-un singur sens), colectionand sacii cu bani din seifurile care
le intalneste in cale. Sa se stabileasca un traseu (daca exista), pe care il
va parcurge hotul astfel incat sa ajunga la elicopter cu cat mai multi saci
de bani.
INTRARE:
Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
n - numarul de nivele
x1 x2 ... xp (1<=p<=n) - nivelele la care se afla posturi de
control pe partea stanga
y1 y2 ... yq (1<=q<=n) - nivelele la care se afla posturi de
control pe partea dreapta
s1 s2 ... sn - si este numarul de saci din seiful
de pe nivelul i
Daca nu exista nici un post de control pe una sau ambele parti, liniile
corespunzatoare din fisier vor contine un 0.
IESIRE:
Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
m - numarul de saci colectionati
u1u2 ... unun+1 - partea pe care este atins fiecare nivel (s sau d) de la
nivelul 1 la nivelul n (un+1 partea pe care este atins
acoperisul)
Sau
0
# - in cazul in care hotul nu poate ajunge la elicopter
Exemplu
Pentru fisierul de intrare INPUT.TXT
8
4
2 6 7
1 3 4 5 9 0 8 0
Iesirea in fisierul OUTPUT.TXT este
14
dssddssss
NOTA
Datele de intrare se presupun corecte.
Timp de executie: 10 sec. / test!
Olimpiada Nationala de Informatica
Timisoara, 23-30 martie 1997
CLASA a IX-a
ZIUA 2
PROBLEMA 4
D'ale Teleportarii Punctaj: 50p
Pentru excursia de joi membrii Comisiei Centrale doresc sa utilizeze
aparatele de teleportare repartizate. Terenul de teleportare trebuie sa
indeplineasca o serie de conditii pe care numai Parcul Rozelor din Timisoara
le ofera. Acesta are o suprafata dreptunghiulara formata din dale de ciment
si dale de gazon. Toate dalele au forma de patrate de latura 1.
Un aparat de teleportare are nevoie de o suprafata de teleportare bine
definita prin dale de ciment. Suprafata de teleportare data permite
teleportarea spre Nord si se numeste suprafata de teleportare spre Nord.
Prin rotirea suprafetei de teleportare cu 900 spre dreapta se obtine o
suprafata de teleportare spre Est. Prin rotirea suprafetei de teleportare
cu 1800 spre dreapta se obtine o suprafata de teleportare spre Sud. Prin
rotirea suprafetei de teleportare cu 2700 spre dreapta se obtine o suprafata
de teleportare spre Vest.
La identificarea suprafetelor de teleportare din parc se va tine cont ca
nici una din dalele de ciment ce vor face parte din suprafata de teleportare
nu au voie sa intre in contact pe orizontala, verticala sau diagonala cu
nici o alta dala de ciment ce nu face parte din supafata.
Sa se precizeze numarul de suprafete care permit teleportarea spre fiecare
directie in parte (N,E,S,V).
INTRARE:
Datele de intrare se vor citi din fisierul INPUT.TXT cu structura:
m n * dimensiunile parcului separate
printr-un spatiu (m, n <= 100)
x1,1 x1,2 ... x1,n * xi,j, au valori egale cu:
x2,1 x2,2 ... x2,n 2 pentru dale de ciment
. . . 1 pentru dale de gazon
xm,1 xm,2 ... xm,n (numerele de pe o linie sunt separate printr-un spatiu)
p q * dimensiunile celui mai mic dreptunghi in care se
poate plasa
y1,1 y1,2 ... y1,q suprafata de teleportare, separate printr-un spatiu
(p, q <= 10)
y2,1 y2,2 ... y2,q * yi,j, au valori egale cu: 2 pentru dale de ciment
. . . 0 in rest
yp,1 yp,2 ... yp,q (numerele de pe o linie sunt separate printr-un spatiu)
IESIRE:
Rezultatele vor fi scrise in fisierul OUTPUT.TXT cu structura:
Nord - numarul de suprafete care permit teleportarea spre Nord
Est - numarul de suprafete care permit teleportarea spre Est
Sud - numarul de suprafete care permit teleportarea spre Sud
Vest - numarul de suprafete care permit teleportarea spre Vest
Fisierul OUTPUT.TXT este:
1
1
1
0
Exemplu
Pentru fisierul INPUT.TXT:
8 7
2 2 1 2 2 2 1
1 2 1 2 1 1 1
1 2 1 1 1 2 2
1 1 2 1 1 1 2
2 2 1 1 2 1 2
1 2 1 1 2 1 1
1 2 2 1 2 2 1
2 2 2 1 1 1 1
3 2
2 0
2 0
2 2
NOTA
Datele de intrare se presupun corecte.
Timp de executie 10 sec. pentru un test.
|
