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

prof. Emanuela Cerchez
Liceul de Informatica "Grigore Moisil" Iasi


propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Articole recomandate

De acelaşi autor:

Hashing, Suffix arrays, Arbori de compresie Huffman, Gomory-Hu Cut Trees, Determinarea clicilor, Reprezentarea mulţimilor disjuncte, Heap-uri

Probleme recomandate

De la .campion 2003:	newcomp, rima, algebra, turn1, aparitii, carti1, program1, tgraf, ceas1, spioni, kgb, tabara1, romane, stop, hanoi, lift, pic, sms, fibo, bac, parc, circular, logn, lex, joc7, cuburi1, sant, mobile, pattern, produs, mutare, viteza, concurs2, furnici, homeless, subsir
De acelaşi autor:	celule, scp, vedete, film, ab, supertri, inginer, camp, sl, detinut, simetric, egal, gropi, ruleta, carti, tgv, uscat, afise, dezbateri, bunici, rv, onu, nspecial, secvop, cadou, chimie, reteta, piticot, petrol, checkin, teanc, index, teren, pizza, ecran, drum, text, lbd, aven, spam, pluricex, tren2, gray, pasi, mgo, joc, anagrame, vecini, criptmat, maxim, cutie, party, friends, net, sablon, hd, pc, sir2, aztec, scara, nr, robot2, sah, formule, ed, bilete, hanoig, flood, matrice3, erdos, grup, cd, kfactor, np, cuc, radio, honest, ref, nr01, scor2, convert, auto2, compress, politics, pm, playlist, barbie, firma1, submatrix, ham, pizza1, exam, ants, teatru1, cifre1, bile1, caini, secvreg, pasune, remi, m01, sir23, tren1, joc5, pachete, aedaro, windows, renju, latime, mere1, piloti, peste, pitici, sirag1, stive, turn1, carti1, program1, spioni, kgb, lift, apel, lex, homeless, subsir, dist, harta1, adevar, joc10, bare, zapezi, masina2, perechi1, raft, joc11, joc12, ferma, fni, tunel, lover, pepsi, transport, avion, monkey, premii1, garaj, carti2, tv, pact, fat, cafea, echipe1, secvente, petrom, peg, scara1, lant, ecuatii, stiva, bile4, jungla, rj, poli, text1, compus1, rez, politie, anag, codul, coment, muzeu, seti, basm, timer, secvsir, dp, placa, prod3, bursa, submdisj, sotron1, fazan, secvpar, joker, lego, medalii, cfr, antipatie, figura, links, segm, colorare, brazi, mobil, distsir, guess, greiere, pestera, conferinta, chei, ny, nx, ghinion, sumb, drenaj, telecomanda, grupuri, mahjong, rotund, viena, sport2, cos, monoton, micro, valet, nr0, maxviz, anagramabil, nrpal, lista, dame, consiliu, adprod, arme, deal, prodnr, compar, latin, interviu, vintage, prize, nrdiv, arrows, tdrept, agenda, reziston, vot2, tema, smiley, relatii, ech, scadere, nebuni, castig, expand, wb, prime2, virgule, b210
Despre vector:	trei, simetric, egal, ruleta, pod, uscat, afise, an, bunici, cursa, onu, tramvai, cadou, kpal, expresie, piticot, roci, petrol, grad, ruleta2, ecran, palma, concurs, holo, ab2, tren2, cifre, mgo, firma, anagrame, joc2, br, maxim, astre, numere2, baby, zapada, hd, startrek, vecini2, drept, teatru, tir, patrate2, nr, cifra, repeat, unu, criptare, ratb, placi, sume3, turist, matrice3, pavaj, sume, kafka, bacan, spair, grup, friends2, bitslang, fisc, scor2, cat, nr3, chimie2, zid, politics, submat, reteta2, rezervatie, creioane, felinare, 2numere, exp, scoici, patrate1, playlist, sqr, carte, oua, turn, ants, div3, jeton, politic, trecere, maraton, zaruri, suma1, mere1, agitatie, lacuri, secv, sotron, triunghi, carti1, spioni, kalah, excursia, matricea, maxq, furnici, baschet, ingerasi, numar1, prieteni, aritma, cezar, bifo, pal, seceta, bare, soricel1, antena, avere, paianjen, bloc, schi, suma3, fractie, tunel, pepsi, prefix, tren3, avion, premii1, csir, top, bsir, secvente, cod4, cuburi3, limbaj, panouri, sant1, zumzi, sport1, baschet1, mere3, powerpuff, placare, sir4, volei1, tabel, ocr, numere7, lacusta, flori, pluton, elfi, mare, grupe1, maroco, cartonas, cabina, case, cod5, furnica, numere8, paritate, comoara1, exponent, control, exp1, joc13, popas, reactivi, siruri1, vanatoare, submult, text1, taxe1, visul, paranteze, puncte3, cub3, numere9, panglica, pietre, poartas, sume2, bal, secvsir, vot, prefix1, accesibil, palc, standard, bursa, meteo, jetoane, printesa, palindrom, joker, matriosca, loto, cuvant, cladiri1, secvente1, zar, tren4, asociativ, lego, medalii, figura, joc14, neuroni, char, dartz, turism1, calorii, xor1, paltrei, album, livada1, colorare, greutati, brazi, submatrix1, plaja, cd1, cifru3, permutare, miere, tetris1, conferinta, atelier, radical, bileprime, nx, atletism, sumb, minmax, sumacifre, jocprim, sircifre, cmmdcsecv, secvb, siruri3, cifru4, vase, carte1, grad1, litere, magic6, macheta, butoane, ec, stalpi2, fagure, goe, papusa, taburet, mesaj3, zar1, joc16, talent, joc18, cos, punctfix, risipa, liste, triburi, nr0, oneton, nor, nrpomi, paisprezece, anagramabil, zuma, joc20, dale, perechi2, consiliu, becuri2, codpatrat, adprod, qtri, reconst, arme, triunghi4, deal, ozn1, cifru5, flori1, elicop, roata, trifoi, maxbin, culori2, numar5, bile6, proiecte, alune, cuburi4, sstabil, intersectii, copaci2, 7segmente, amedie, drept2, divider, eliminare, matd3, prodnr, fraze, vectori1, compar, unific, galbeni, clepsidru, calcule, puncte6, maxp, cursa1, secvp, swap, extraprime, onigim, divizori1, remi1, tetris3, amestec, eoliene, split, momente, secvente2, ausoara, aranjare2, vintage, binremove, sminus, subsets, interclasare, palindromuri, colina, doitrei, rebus1, tcif, munte3, triunghi6, schi1, rascoala, solitar, praslea, vot2, tema, sprime, sir2dif, aperm, unudoi, prajituri, tan, concurs4, ech, arc, dominant, ordine, tv1, nebuni, sort2dist, lightbot, iepuras1, castig

Software recomandat

De acelaşi autor:

Drumuri minime în graf, Elemente de bază ale limbajului C/C++, Permutări, APM, Heap Interactiv, Algoritmul lui Lee, Recursivitate, Arbori de intervale