Problema de mai jos se adreseaza in special elevilor din clasele a 9-a si
a 10-a care consider ca au fost un pic neglijati pana acum. Problema s-a dat
intr-o forma asemanatoare la IOI Suedia 1994. Nu trebuie sa va mire ca o
propun la clasele mici, deoarece problema face parte din categoria problemelor
"expirate" (din cate ati observat si la olimpiada pe sector din Bucuresti la
clasa a 9-a s-a dat o problema de IOI).
----------------------------------
| PROBLEMA 8: Vila de Senator |
| PUNCTAJ: 40 Dexteri |
| DEADLINE: Luni, 15 Martie |
| TIMP DE IMPLEMENTARE: 60 minute |
| TIMP DE EXECUTIE: 1 sec./ |
| Pentium 166 Mhz. |
----------------------------------
Vila de Senator
---------------
Un senator are o vila, reprezentata printr-o matrice ce contine numai
caracterele "1" si "-" (minus), unde 1 reprezinta "zid", iar 0 "spatiu liber".
Spre exemplu o vila modesta, cu doar 3 camere arata in felul urmator:
1111111111111
1-------1---1
1---111111111
1-------1---1
1111111111111
Problema cere sa aflati:
a) Cate camere are vila senatorului
b) Care este camera cu suprafata cea mai mare
c) Ce perete trebuie indepartat (prin perete se intelege un singur
caracter de '1') astfel incat sa se obtina o cea mai mare camera.
(se cere o singura solutie).
Datele de intrare se citesc din fisierul "vila.in" ce are urmatorul
format:
- pe prima linie se gasesc doua numere naturale n si m despartite
printr-un spatiu (1<=n,m<=100), care reprezinta numarul de linii (n),
respectiv numarul de coloane (m) al matricii
- pe urmatoarele n linii se gasesc cate m caractere "1" sau "-"
Datele de iesire se scriu in fisierul "vila.out", in urmatorul format
- prima linie contine numarul de camere
- a doua linie contine aria camerei de suprafata maxima
- a treia linie contine coordonatele zidului eliminat si aria camerei
de suprafata maxima rezultata
Exemplu:
1)
vila.in vila.out Observatie:
5 13 4 Camerele nu se invecineaza
1111111111111 17 pe diagonala.
1-------1---1 4 9 22
1---1111-1111
1-------1---1
1111111111111
2)
vila.in
4 12 vila.out Observatie:
111111111111 2 Vila se considera
-----11----- 10 inconjurata de ziduri
-----11----- 1 1 11
111111111111
|
|