Katedra počítačů ČVUT FEL & Czech ACM Chapter
Soutěž v programování 1999 Stavitel stavitel.p, stavitel.c, stavitel.C
Matěj se vždy chtěl stát architektem a již jako malý
se vyžíval ve stavbě různých architektonických skvostů. Vzhledem
ke svým možnostem byl však značně limitován a pro vytváření svých
budov používal dřevěné kostky, které stavěl na sebe. Tyto sloupce
kostek vždy umístil na šachovnicovou podložku tvaru čtverce obsahující
Zde je příklad jednoho z jeho děl. Podložka měla rozměr
![]() Byl hrdý na to, jaké budovy postavil, ten řád a dokonalost z nich přímo čiší. Ostatní to neviděli a považovali jeho výtvory za nesmyslné. Co chudák Matěj zmůže, jeho genialitu ocení lidé až mnohem později. Aby se jeho dílo dochovalo, rozhodl se, že své budovy nakreslí na papír a pečlivě uschová. Protože kreslení třírozměrných budov pro něj bylo příliš náročné, dělal dva nákresy: jeden zepředu (bylo možné vidět pouze přední stěny kostek) a jeden zprava (bylo možné vidět pouze pravé stěny kostek). Nákresy byly ve skutečnosti dvourozměrnými průměty objektů, které Matěj postavil (tzv. nárys a bokorys). Toto jsou Matějovy nákresy vztahující se k výše uvedenému příkladu.
![]()
Matěj byl přesvědčen, že pomocí těchto nákresů bude kdykoli schopen budovy znovu postavit. Po delší době objevil své nákresy z dětství a zjistil, že se mýlil. Z většiny párů nákresů byl schopen postavit více než jednu budovu, která odpovídala nákresům. Objevil, že z každé dvojice nákresů, které udělal, je možné postavit tzv. minimální budovu (tj. budovu, která se skládá z minimálního počtu kostek L, přičemž obrysy zepředu a zprava odpovídají nákresům) a tzv. maximální budovu (tj. budovu, která se skládá z maximálního počtu kostek M, přičemž obrysy zepředu a zprava odpovídají nákresům). Z výše uvedených nákresů je možné postavit minimální budovu složenou pouze ze L = 7 kostek a maximální budovu složenou ze M = 17 kostek například takto:
![]() Matěj začal pro každou dvojici nákresů určovat hodnoty L a M, ale brzy zjistil, že je velice zdlouhavá a nudná práce. Vaším úkolem je napsat program, který tuto práci udělá za něj. Specifikace vstupu Vstup se skládá z N zadání. První řádek vstupu obsahuje pouze celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání se skládá ze tří řádků. Na prvním řádku zadání je jedno kladné celé číslo K (ne větší než 100) udávající rozměr podložky. Druhý resp. třetí řádek zadání obsahuje popis nákresu zepředu resp. zprava. Popis nákresu se skládá z posloupnosti K nezáporných celých čísel vzájemně oddělených mezerou. Každé číslo udává výšku příslušného sloupce kostek. Z uvedených nákresů je vždy možné postavit alespoň jednu budovu. Specifikace výstupu Pro každé zadání program vypíše `Minimalni budova obsahuje L kostek, maximalni M kostek.', kde L a M budou nahrazeny příslušnými číselnými hodnotami.
Příklad vstupu 2 4 2 0 3 1 1 1 2 3 1 1 1Příklad výstupu Minimalni budova obsahuje 7 kostek, maximalni 17 kostek. Minimalni budova obsahuje 1 kostek, maximalni 1 kostek. |