|  |
|
Katedra počítačů ČVUT FEL & Czech ACM Chapter Soutěž v programování 1997 Cestovní kancelář ACMCZPo přechodu na tržní hospodářství začalo v našem státě vznikat velké množství společností podnikajících v různých oborech. Jedním z nejvýnosnějších oborů se stal cestovní ruch, především pak zájezdy do zahraničí. Jednou z nově založených cestovních kanceláří je i agentura Amatérské cestování mezi cizokrajnými zvířátky (ACMCZ), která se snaží mezi konkurencí prosadit především díky svým originálním službám. Provoz takové cestovní kanceláře je ale velice náročný a majitele stojí vedení agendy mnoho času a nervů. Proto zakoupil nový výkonný osobní počítač, na který hodlá přesunout většinu organizační práce. Bohužel však stále nemá k dispozici potřebné programové vybavení. Vaším úkolem bude pomoci při vytváření několika základních programů nutných pro správný chod celé společnosti. Protože majitel kanceláře je v práci s počítači velmi zběhlý, není pro něj důležitá ani tak grafická stránka, jako spíš rychlost provádění všech výpočtů. Všechny programy, které máte vytvořit, tedy dostanou všechna potřebná data na svůj standardní vstup a potřebné výsledky mají poslat v předepsané formě na standardní výstup. Ve všech případech budou čísla na vstupu i na výstupu tak velká, aby se vešla do standardního typu integer nebo int (není-li stanoveno jinak). Přejeme všem mnoho úspěchů při plnění tohoto úkolu.
LetištěPři vykládání zavazadel cestujících používá naše cestovní kancelář Supervýkonný ultrazdvihující natáčecí hydraulický ekologický pohyblivý elektrický nízkoplošinový vozíkový dopravník SUN-HEPEN-VD-31789/48WQ, lidově zvaný též ještěrka. Na tento vozík se naloží část zavazadel a odveze se od letadla do prostoru určeného k naložení na nákladní automobil. Na letišti Guiliama Watese ve státě Muctonsofie je mezi přistávací dráhou a stanovištěm nákladních automobilů postaven poměrně úzký, ale velmi dlouhý průjezd, který je po obou stranách ohraničen vysokými zdmi. Přestože na to majitel cestovní kanceláře ACMCZ již několikrát písemně upozorňoval, je po celé délce tohoto průjezdu neustále nepořádek. Na všech možných i nemožných místech jsou různě poházené bedny, přístroje, vraky aut, letadel a počítačů a jiné nepotřebné předměty. Majitel letiště Guiliam Wates však veškerou kritiku odmítá s odůvodněním, že zatím bylo vždy možné projet. Jedinou změnou k lepšímu, která byla na letišti od roku 1981 provedena, je to, že byla plocha průjezdu rozdělena na čtvercové díly, opticky zvýrazněné pomocí velkých čtvercových dlaždic. Všechny dlaždice jsou k sobě skládány celými stranami a jsou přesně tak velké, aby jedna volná dlaždice stačila na projetí ještěrky ve všech čtyřech směrech a také na její otočení o 90 stupňů. Průjezd je ve všech místech stejně široký, takže dlaždice vytvářejí obdélník o stranách S (kratší strana) a L (delší strana). Pomocí stacionární družice zakoupené vedením letiště speciálně k tomuto účelu je celá plocha každou hodinu snímkována a s pomocí počítače je registrováno, které dlaždice jsou neprůjezdné a které nikoli. Majitel kanceláře ACMCZ je s takovým stavem hrubě nespokojen, protože při průjezdu se ztratí mnoho času různým zatáčením a hledáním správné cesty. Také se velmi často řidičům stává, že vůbec nenajdou volný průjezd na druhou stranu a musí dlouhé desítky minut bloudit a čekat, až se některé místo uvolní. Právníkům ACMCZ se víceméně legálním způsobem podařilo získat několik okamžitých situací na průjezdové cestě, které byly zaznamenány družicí a počítačem. Protože by rádi dokázali majiteli letiště to, že v některých okamžicích vůbec nebylo možné projet od letadla k nákladnímu automobilu, potřebují program, který dokáže průchodnost takové cesty určit. Specifikace vstupuVstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání obsahuje na prvním řádku celé kladné číslo S, S <= 10000. Toto číslo udává počet dlaždic tvořících jednu řadu (tedy velikost kratší strany obdélníka měřenou na dlaždice). Dále následuje L řádků, na každém z nich je popsána jedna řada dlaždic (postupně, od začátku cesty). Každý takový řádek obsahuje S znaků, kde 1 znamená volnou dlaždici (je možno projet) a 0 obsazenou dlaždici (není možné projet). Počet řádků (a tedy délka celého průjezdu) není omezen. Každé zadání je ukončeno jedním prázdným řádkem. Prázdný řádek obsahuje pouze znak pro přechod na nový řádek. Specifikace výstupuPro každé z N zadání musí program vypsat právě jeden řádek, na kterém bude věta Cesta je prujezdna., jestliže je pro dané zadání možné projet z horní strany obdélníka na spodní, nebo věta Cesta neni prujezdna., jestliže průjezd není žádným způsobem možný. Ještěrka se může pohybovat pouze po prázdných dlaždicích, přejíždět může pouze na sousední dlaždice a nesmí vyjet mimo cestu. Sousední dlaždice jsou pouze takové, které se dotýkají celou stranou a nikoli pouze vrcholem. Příklad vstupu3 7 0000110 0111010 0101010 0101010 1101110 1000000 1100000 0100000 10 0010010000 0100001111 0100001101 0111001000 0000000111 0000001010 10 0010010000 0110000000 0100001111 0000001101 0000011001 0000001010 0000000000 Příklad výstupuCesta je prujezdna. Cesta neni prujezdna. Cesta neni prujezdna.
TermínKaždoročně pořádá agentura ACMCZ dovolenou na břehu Buflíkova jezera. Tyto zájezdy jsou zvláštní tím, že cestovní kancelář nezajišťuje žádný program a zákazníci tak nejsou ničím vázáni a mohou si dělat, co se jim zachce. Další výhodou takové akce je i nižší cena. Agentura připraví pouze chatičky a stany pro různé počty osob, zajistí jednoho nebo dva správce, jeden autobus a to jsou spolu s pronájmem tábora veškeré její náklady. Tábor si ACMCZ pronajímá od společnosti BSA (Buflíkova Stanovací Agentura), která má ovšem mnoho dalších zájemců, a tak může poskytnout prostory pouze na omezený počet dní. Aby mohla cestovní kancelář zvolit nejlepší termín pro rezervaci tábora, pořádá mezi svými zákazníky anketu. Cílem takového průzkumu je zjistit, kolik rekreantů by mělo zájem o účast na zmíněném zájezdu v jednotlivých dnech celé sezóny. Váš program má být schopen z výsledků této ankety určit nejvhodnější termín pro konání akce, tj. najít takové období, které netrvá více než je zadaný počet dnů a během něhož je maximální součet zájemců pro všechny dny. Období musí být souvislé, protože společnost BSA chce z pochopitelných důvodů minimalizovat počet střídání různých nájemců. Specifikace vstupuVstup se skládá z N zadání. První řádek obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání začíná jedním řádkem, který obsahuje celé kladné číslo K, K <= 1000. Číslo K vyjadřuje maximální počet dní, na který je BSA ochotna tábor pronajmout. Na druhém řádku zadání je posloupnost celých nezáporných čísel, navzájem oddělených mezerou. Počet čísel není nijak omezen. Tato čísla nejsou nikdy vyšší než milion a reprezentují zájem o jednotlivé dny během celé sezóny. Za posledním číslem na řádku následuje bezprostředně znak přechodu na nový řádek, tj. nejsou za ním žádné mezery. Specifikace výstupuPro každé zadání musí výstup obsahovat jediný řádek textu s větou: Nejvhodnejsi termin zacina XX. dnem., kde XX je číslo prvního dne (dny jsou číslovany od začátku posloupnosti od jedné) takového souvislého období, pro které je součet zájemců ze všech dnů maximální a které netrvá déle než K dnů. Pokud má úloha více řešení, vypište první termín splňující zadání. Příklad vstupu3 3 6 2 3 2 9 2 1 1 3 1 1 2 1 1 2 1 3 2 8 1 Příklad výstupuNejvhodnejsi termin zacina 3. dnem. Nejvhodnejsi termin zacina 1. dnem. Nejvhodnejsi termin zacina 6. dnem.
PřekladačCestovní kancelář ACMCZ má samozřejmě mnoho konkurentů, ale největším z nich je zcela určitě Nepolitická asociace pro turistická odvětví (NATO), která mimo jiné vlastní veliké výpočetní středisko. Protože se majitel ACMCZ dozvěděl o plánech svého konkurenta, podplatil jednoho ze zaměstnanců střediska, aby mu získal zdrojové texty použitých programů. Zjistil, že většina výpočtů, které se ve výpočetním středisku provádějí, se týká budoucnosti něžného pohlaví na naší planetě. Protože výsledky těchto výpočtů jsou pro cestovní kancelář životně důležité, hodlá ACMCZ získané programy použít pro vlastní potřebu. Aby nemohl být nezákonně nabytý software zjištěn na disku počítače, budou se výpočty provádět s použitím programovatelného kapesního kalkulátoru. Bohužel, ukradené programy jsou psány výhradně v programovacím jazyce miniBASIC a kalkulátor umí pouze zásobníkový jazyk miniFORTH. Společnost by tedy potřebovala překladač mezi těmito dvěma jazyky. Příkazy miniBASICu jsou tyto:
Identifikátor proměnné je jedno z písmen A až Z. Aritmetický výraz je jedna z následujících možností:
Program v miniBASICu se skládá z posloupnosti příkazů LET, za níž následuje jediný příkaz PRINT. Ten je posledním příkazem programu. Každý příkaz je uveden na samostatném řádku. Všimněte si, že každý výraz může obsahovat maximálně jeden operátor. Jazyk miniFORTH je jazyk zásobníkového počítače s těmito příkazy:
Aritmetické operace se provádějí vždy s hodnotami na vrcholu zásobníku (pravý operand je na vrcholu zásobníku, levý pod ním), výsledek je uložen opět na vrchol zásobníku a operandy jsou odstraněny. Příkazy programu jsou odděleny libovolným počtem mezer. Specifikace vstupuVstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následuje N programů v miniBASICu. Délka programu v miniBASICu není nijak omezena. Za posledním příkazem každého programu je jeden prázdný řádek. Prázdný řádek obsahuje pouze znak 'přechod na nový řádek'. Specifikace výstupuPro každé zadání musí výstup obsahovat právě jeden řádek textu, na kterém bude program v miniFORTHu ekvivalentní zadanému programu v miniBASICu. Programy jsou ekvivalentní, jestliže pro libovolné počáteční hodnoty proměnných produkují stejný výstup (na výstupu je stejná hodnota). Složitější výrazy můžete libovolně optimalizovat, není to však podmínkou. Příklad vstupu2 LET A=12*A LET B=A-5 LET C=67+B PRINT C LET D=A-B LET E=C+D LET F=D*E LET G=D/E PRINT G Příklad výstupu: 67 12 A @ * 5 - + . ; : A @ B @ - C @ A @ B @ - + / . ;
PísařkaSekretářka cestovní agentury musí psát mnoho různých dopisů: nabídky zájezdů, pozvánky, oznámení o změnách, poděkování a v neposlední řadě i omluvy za připálené jídlo, hotelový bazén v rekonstrukci nebo zavřenou internetovou kavárnu v místě pobytu. K psaní všech takových dopisů se v agentuře ACMCZ samozřejmě používá osobní počítač a textový editor Tornádo 713-111. Ředitel společnosti by chtěl své pohledné a mladé sekretářce práci co nejvíce usnadnit, protože by ji pochopitelně rád využíval také k jiným činnostem. Svůj návrh založil na skutečnosti, že slovní zásoba použitá ve všech dopisech, které píše sekretářka, je omezená. Není problém sestavit seznam všech slov, které se v takových dopisech vyskytují, a sekretářce potom bude stačit psát začátky těchto slov, čímž si může ušetřit mnoho písmen. Vaším úkolem je napsat program, který takový zkrácený text převede na jeho plnou verzi. Specifikace vstupuVstup se skládá z N zadání. První řádek obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání se skládá ze dvou částí. První část obsahuje slova, která sekretářka zná, druhá část začátky slov určené k doplnění. První řádek první části obsahuje celé kladné číslo X, udávající počet slov, která sekretářka zná. Následuje postupně X řádků, z nichž každý obsahuje právě jedno slovo. V tomto seznamu se žádné slovo nevyskytne více než jednou. První řádek druhé části obsahuje celé kladné číslo Y a za ním následuje postupně Y řádků, každý obsahuje jeden řetězec -- začátek slova, které má být doplněno. Každé slovo může být 1 až 100 znaků dlouhé, může obsahovat malá i velká písmena a číslice. Počet známých slov X je z intervalu <1, 1000>, počet zadávaných slov Y je z intervalu <1, 10000>. Velká a malá písmena jsou považována za různá. Specifikace výstupuPro každý začátek slova musí výstup obsahovat právě jeden řádek textu. Je-li možné daný řetězec jednoznačně doplnit na existující slovo ze seznamu na začátku zadání, bude mít výstup tvar Doplneno slovo XX., kde za písmena XX se samozřejmě dosadí úplný tvar slova. Pokud daným řetězcem začíná více různých slov, vypište na řádek větu Detekovana kolize. a pokud neexistuje žádné slovo, které by začínalo zadaným řetězcem, větu Slovo nelze doplnit.. Za doplnění se považuje i doplnění prázdného řetězce. Příklad vstupu1 5 skola skolnik skoda volkswagen voltamper 10 sko skod skop skoln skolni skolnikovo v volper volk volt Příklad výstupuDetekovana kolize. Doplneno slovo skoda. Slovo nelze doplnit. Doplneno slovo skolnik. Doplneno slovo skolnik. Slovo nelze doplnit. Detekovana kolize. Slovo nelze doplnit. Doplneno slovo volkswagen. Doplneno slovo voltamper.
LékařNa ostrově Fujutimoru v Karibském moři se objevila epidemie nové, dříve zcela neznámé nemoci Philuktirus Pendoxis (filuktůra). Ačkoli tato nemoc není životu nebezpečná, je pro postiženého i jeho okolí velmi nepříjemná. Projevuje se totiž takovými příznaky, jako jsou malátnost, žaludeční nevolnost, časté depresivní stavy, nadměrná kousavost, prudké záchvaty zuřivosti a používání MS-Windows. Vědci zjistili, že filuktůra se může vyskytnout pouze u některých lidí, neboť většina jedinců je proti ní zcela imunní. Skutečnost, zda se daný člověk může nebo nemůže touto nemocí nakazit, lze spolehlivě zjistit mikrobiologickým testem, nazvaným podle svého objevitele, kterým, jak již zajisté tušíte, není nikdo jiný než řecký vědec Postolomlatos. Protože cestovní kancelář ACMCZ by nerada způsobila svým zákazníkům traumata spojená s filuktůrou, provádí před každým odjezdem na ostrov Fujutimoru vyšetření všech cestujících. Při Postolomlatově testu se vyšetřovanému pacientovi odebere vzorek krve, který se dále velmi složitým způsobem zpracovává. Tento postup přesahuje rámec tohoto textu, takže se o něm nebudeme blíže zmiňovat. Důležité však je, že do upraveného preparátu se přidá určitý počet bakterií Pendoxia Vulgaris, které filuktůru způsobují. Některé z těchto bakterií po krátké době odumřou díky přítomnosti obranných látek v krvi. A právě z poměru odumřelých a přeživších bakterií se stanovuje stupeň obranyschopnosti zkoumaného organismu. Speciálně školený laborant tedy připraví preparát, přidá do něj odměřené množství roztoku s bakteriemi, nanese jej na mikroskopické sklíčko, sejme CCD kamerou jeho obraz, upraví ho a digitalizuje pomocí softwaru dodaného výrobcem kamery. Výsledkem je černobílá bitmapa, obsahující bílé pixely pozadí a černé pixely znamenající části buňky. Buňka živé bakterie vypadá vždy jako souvislá černá oblast s jednou bílou dírou uprostřed, buňka odumřelé bakterie se jeví jako souvislá černá oblast bez díry. Můžeme předpokládat, že žádné dvě buňky se nedotýkají, že v bitmapě nejsou žádné jiné objekty než buňky a že všechny pixely mimo bitmapu jsou bílé, tj. všechny buňky leží v bitmapě celé a nedotýkají se jejího okraje. Vaším úkolem je napsat program, který z dané bitmapy určí, kolik je v preparátu buněk typu A (živé bakterie, tj. oblast s dírou) a kolik buněk typu B (odumřelé bakterie, tj. oblast bez díry). Pro účely úlohy provedeme neformální definici použitých pojmů:
Specifikace vstupuVstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání, každé začíná řádkem obsahujícím dvě celá kladná čísla R a S, (R <= 1000000 a S <= 200), reprezentující počet řádků a sloupců bitmapy. Dále následuje R řádků obsahujících samotnou bitmapu. Každý z těchto řádků obsahuje S znaků. Znak 'X' znamená černý pixel, znak '.' bílý pixel. Poté ihned následuje znak 'přechod na nový řádek'. Specifikace výstupuPro každé zadání vypište jediný řádek, který bude obsahovat text Nalezeno XX bunek typu A a YY bunek typu B., kde XX a YY nahradíte odpovídajícími čísly. Příklad vstupu1 3 7 XXX..XX X.X.XX. XXX.... Příklad výstupuNalezeno 1 bunek typu A a 1 bunek typu B.
FarmaNejdražší a bezkonkurenčně nejžádanější atrakcí cestovní kanceláře ACMCZ je bezesporu letecký zájezd do státu Komolu, kdesi uprostřed Tichého oceánu. Tento zájezd je proslaven především tím, že na tamější farmě Naopsi pěstují domorodci velmi vzácného a zvláštního živočicha, který se jmenuje Vertecholustosaurus a který se množí dělením. Za jeden den se vždy počet živočichů zvětší K-krát. Poslední den dovolené je servírována specialita v podobě stehýnek z Vertecholustosaura. Jeho maso je velmi chutné, zdravé a výživné a samozřejmě také pěkně drahé. Farmu Naopsi však bohužel velmi často navštěvují různí zloději, kteří Vertecholustosaury kradou. Od zlodějů vykupují tyto vzácné živočichy překupníci, ale vždy výhradně po baleních o velikosti X. Jelikož jsou zloději velmi chamtiví, ukradnou vždy takové největší možné množství živočichů, které je celistvým násobkem čísla X, a zbytek nechají na farmě. Aby měla cestovní kancelář jistotu, že v poslední den jejího zájezdu bude dostatek Vertecholustosaurů na závěrečnou hostinu (a ještě po ní zbyde takové množství, aby nedošlo k ohrožení chovu), potřebuje vytvořit počítačový program, který dokáže spočítat, kolik živočichů v Naopsi zůstane, když víme, že farmu navštíví různé tlupy zlodějů celkem C-krát, a to v časech T1, T2, ..., TC. Vaším úkolem je napsat právě takový program, který zjistí, kolik živočichů zůstane na farmě po poslední "návštěvě" zlodějů, jestliže v čase 0 bylo na farmě Z živočichů. Specifikace vstupuVstup se skládá z N zadání. První řádek vstupního souboru obsahuje celé kladné číslo N. Dále následují jednotlivá zadání. Každé zadání je tvořeno dvěma řádky čísel, ta jsou vždy oddělena právě jednou mezerou. Na prvním řádku jsou umístěna celá čísla Z, K, X, C, na druhém pak C čísel T1 až TC, která tvoří neklesající posloupnost nezáporných celých čísel o délce C. Ta udávají časy příchodů zlodějských tlup ve dnech. Program může využít těchto omezení na obor hodnot:
Specifikace výstupuPro každé zadání musí výstup obsahovat právě jeden řádek textu, na kterém bude věta Na farme zbylo XX zivocichu., kde XX je počet Vertecholustosaurů, kteří zbyli po poslední návštěvě zlodějů. Příklad vstupu2 6 2 10 1 2 1 2 20000 2 4 15 Příklad výstupuNa farme zbylo 4 zivocichu. Na farme zbylo 12768 zivocichu.
ZavazadlaCestovní kancelář ACMCZ zajišťuje při leteckých zájezdech svým klientům přepravu všech zavazadel, aniž by se o ně museli nějak starat. Pro zjednodušení své práce ukládá zavazadla všech cestujících do jednotných kontejnerů, které mají tvar rotačního válce s velmi malou výškou (jedná se tedy téměř o takzvanou placku). Společnost vlastní celkem 30 kontejnerů a každý z nich má jinou velikost. Tyto kontejnery se naplní zavazadly, označí se nálepkou se jménem cílové stanice a naloží se do letadla. K nakládání se přitom používá letištní jeřáb, za který se musí platit drahý pronájem. Aby se ušetřilo na těchto poplatcích, vypravují se vždy tři letecké zájezdy současně. Jeřáb má při nakládání k dispozici tři plošiny, které jsou ovšem tak malé, že se na ně vejde pouze jediný kontejner. Naštěstí jsou kontejnery konstruovány tak, že se dají skládat na sebe (takže jich tímto způsobem můžeme na jednu plošinu umístit i více). Při pokládání musíme dávat velký pozor na to, aby vždy ležel menší kontejner na větším. Jinak by totiž mohlo dojít k jejich deformaci, a tím i k možnému poškození zavazadel cestujících. A taková dáma v letech se spoustou vlivných přátel, rozlícená tím, že se jí při přepravě do alpského lyžařského letoviska pomačkala její oblíbená večerní toaleta, to není nic příjemného. Na začátku nakládky jsou vždy všechny kontejnery položeny na jedné plošině. Největší je úplně dole, nejmenší nahoře. Prvním úkolem jeřábníka je rozdělit tyto kontejnery podle jejich cílové stanice. Během celého manévru (stejně tak jako po jeho skončení) se nesmí nikdy ocitnout větší kontejner na menším. Vaším úkolem je určit, jaký nejmenší počet přesunů musí jeřábník provést, aby rozdělil kontejnery na jednotlivé plošiny tak, že na každé z nich budou ležet kontejnery určené pro jedno cílové místo. Specifikace vstupuPrvní řádek obsahuje celé kladné číslo N udávající počet zadaných úloh. Následuje N řádků definujících jednotlivé úlohy. Každá z nich je zadána počtem kontejnerů X a dále X čísly z množiny {0, 1, 2}, která označují, kam se mají kontejnery dopravit. Cílové stanice jsou zadány postupně podle velikosti počínaje spodním (největším) kontejnerem. Všechna čísla jsou od sebe oddělena mezerou, číslo X nebude nikdy větší než 30. Specifikace výstupuPro každou úlohu program vygeneruje právě jeden řádek, který bude obsahovat větu Je treba XX presunu., kde místo XX bude číslo udávající minimální počet přesunů, který je nutný pro takové rozdělení, aby všechny kontejnery určené do stejné cílové stanice ležely vždy na jedné plošině a aby na takové plošině nebyly žádné kontejnery určené pro stanici jinou. Příklad vstupu3 5 1 1 1 1 1 2 1 2 3 0 1 1 Příklad výstupuJe treba 0 presunu. Je treba 1 presunu. Je treba 3 presunu.
SoutěžJedním z nejžádanějších zájezdů pořadaných cestovní kanceláří ACMCZ je poznávací výlet spojený s účastí na soutěži v programování, která se koná každoročně v Praze. Pravidla této soutěže jistě všichni znáte, takže je zde nemusíme uvádět. Adam a Karel se rozhodli letos tohoto zájezdu zúčastnit a chtěli by na soutěži uspět co nejlépe. Vymysleli proto novou strategii: Adam bude všechny programy pouze analyzovat, Karel je bude pouze kódovat (tj. zapisovat do počítače v programovacím jazyce miniFORTH). Začne-li jeden z nich pracovat na úloze, vždy svou část úkolu dokončí, než začne pracovat na jiné, tj. nepracuje nikdy na dvou úlohách současně, ani svou práci nepřerušuje. Karel nemůže začít úlohu kódovat dříve než ji Adam zanalyzuje. Specifikace vstupuPrvní řádek vstupního souboru obsahuje celé kladné číslo N znamenající počet zadání. Následuje N bloků, každý pro jedno zadání. Každý blok začíná řádkem obsahujícím celé kladné číslo M (M <= 100000), které reprezentuje počet úloh, které mají Adam s Karlem vyřešit. Dále následuje M řádek, každá z nich náleží jedné úloze a obsahuje dvě celá kladná čísla A a B (A,B <= 1000000) udávající postupně časy v minutách potřebné na analýzu a na kódování dané úlohy. Specifikace výstupuPro každé zadání vypište jeden řádek ve formátu: Adam s Karlem budou hotovi nejdrive za XX minut., kde XX nahraďte odpovídajícím časem v minutách. Tento čas by měl udávat minimální dobu, za kterou mohou mít Adam a Karel vyřešeny všechny úlohy při dodržení všech uvedených podmínek. Příklad vstupu1 3 4 5 2 1 1 4 Příklad výstupuAdam s Karlem budou hotovi nejdrive za 11 minut. |
