oras
In general, copiilor le place sa construiasca turnuri din cuburi de lemn, dar Vasile planuieste sa construiasca un intreg oras. Tatal sau i-a cumparat o tabla de joc dreptunghiulara; pe latimea tablei incap exact K cuburi de lemn, iar pe lungime exact L cuburi. Inainte de a incepe constructia orasului, Vasile intentioneaza sa-l proiecteze cu mare atentie. In acest scop, a desenat pe tabla de joc un caroiaj format din KxL patratele. In unele dintre aceste patratele el va construi turnuri din unul sau mai multe cuburi, celelalte ramanand goale. Tabla de joc fiind foarte mare, el nu va stabili exact cate cuburi va plasa in fiecare patratel. El va proiecta numai aspectul orasului vazut din fata si din dreapta. A desenat pe o foaie de hartie aspectul orasului sau vazut din fata si aspectul orasului sau vazut din dreapta.
In figura este ilustrat un exemplu (aspectul orasului vazut din fata, aspectul orasului vazut din dreapta si 3 variante posibile de constructie a unui oras cu acest aspect fata-dreapta):
Tatal lui Vasile este ingrijorat ca nu vor fi suficiente cuburi pentru constructia orasului pe care il doreste Vasile.
Cerinta
Scrieti un program care sa determine numarul minim si numarul maxim de cuburi de lemn necesare pentru a construi un oras care sa corespunda proiectului lui Vasile, daca este posibil.
Date
de intrare
Fisierul de intrare oras.in contine pe prima linie doua numere naturale K (numarul de cuburi care incap pe latimea tablei de joc) si L (numarul de cuburi care incap pe lungimea tablei de joc), separate prin spatiu. Urmatoarele K linii contin descrierea aspectului orasului vazut din fata. Pe cea de a i-a linie dintre cele K se afla inaltimea (exprimata in numar de cuburi) a turnului vizibil din directia celui de al i-lea patratel de pe tabla (patratelele fiind considerate de la stanga la dreapta). Urmatoarele L linii contin descrierea aspectului orasului vazut din dreapta. Pe cea de a i-a linie dintre cele L se afla inaltimea (exprimata in numar de cuburi) a turnului vizibil din directia celui de al i-lea patratel de pe tabla (patratelele fiind considerate din fata catre spate).
Date
de iesire
Fisierul de iesire oras.out va contine o singura linie. Pe aceasta linie se afla mesajul imposibil, daca nu este posibila constructia unui oras care sa aiba aspectul din fata si aspectul din dreapta desenat de Vasile, sau o pereche de numere naturale min max, separate printr-un singur spatiu, reprezentand numarul minim si numarul maxim de cuburi pe care le poate utiliza Vasile pentru a construi un astfel de oras.
Restrictii
2 <= K,
L <= 100000
Inaltimea
oricarui turn este<= 5000
Numarul
maxim de cuburi necesare pentru constructia unui oras <=2000000000.
Exemple
| oras.in | oras.out | oras.in | oras.out |
|
4 3 1 3 4 2 1 4 2 |
10 21 |
2 2 4 1 1 3 |
imposibil |
Timp maxim de executie/test:
0.1 secunde
prof. Emanuela
Cerchez
Liceul de
Informatica "Grigore Moisil" Iasi
Contact:ema
at mail.dntis.ro