Úloha: Formát textu
Je zadán vstupní text, který máme podle zadaných parametrů přeformátovat a vytisknout. Hlavním požadavkem je, aby výstupní text zabíral co nejméně řádků při dodržení dále uvedených pravidel.Slovo je každá maximální souvislá posloupnost znaků na jednom řádku, která neobsahuje znak mezera. Vstupní text obsahuje alespoň jedno slovo a obsahuje jeden nebo více řádků s pouze tisknutelnými znaky (vč. mezer). Každá posloupnost mezer oddělující dvě sousední slova na řádku vstupního textu je chápána jako mezera jediná, úvodní a koncové mezery vstupního řádku se ignorují. Prázdný řádek neobsahuje žádná slova, může obsahovat libovolný počet mezer. Prázdné řádky se neignorují a přenášejí se do výstupního textu, jen pokud nejsou na konci vstupního textu.
Pro každé slovo napsané na začátku jednoho výstupního řádku platí, že se nevejde celé na konec předchozího výstupního řádku. Pokud se určité slovo W vstupního textu nevejde na řádek výstupního textu (označme tento řádek indexem j), protože v tomto řádku už není dostatek místa, zapíše se W na další řádek R (s indexem j+1) výstupního textu, a to jen tehdy, pokud řádek j již obsahuje jiné slovo (nebo jeho část) a zároveň R je alespoň stejně dlouhý jako W. Pokud je délka R menší než délka W, nebo řádek j neobsahuje ještě žádné jiné slovo ani jeho část, postupuje se takto: Slovo W se rozdělí na slova W0..Wk tak, že slova W0 až Wk napsána za sebou dávají přesně slovo W a zároveň Wi naplní celou kapacitu řádku j+i pro 0 < i < k. Slovo W0 obsadí veškerý volný zbytek řádku j a slovo Wk obsadí začátek řádku j+k. Pokud se slovo W nebo jeho část do řádku nevejde a přitom je tento řádek poslední na stránce, vloží se do něj alespoň nejdelší možná aktuální část slova W.
Konečný výtisk přeformátovaného textu budeme nazývat výstupním otiskem. Představujeme si, že výstupní otisk je rozdělen pravoúhlou síti na jednotlivé buňky, kde každá buňka obsahuje právě jeden znak. Souřadnice levé horní buňky jsou (0, 0), doprava a dolů souřadnice rostou.
Pokud se alespoň jedno slovo nebo jeho část na výstupní otisk nevejde, vystoupí těsně pod otiskem hlášení [Some text missing] bez úvodních mezer.
Výstupní text může být zalomen do sloupců. Řádky výstupního textu zaplňují nejprve první sloupec shora dolů, pak druhý sloupec atd, sloupce se číslují odleva. Sloupec probíhá výstupním otiskem odshora až dolů a to i tehdy, je-li někde přerušen obrázkem. Ve výstupním otisku počítáme i s volným místem pro obdélníkové obrazky, prostor pro každý obrázek je vyplněn určitým zadaným znakem. Text obtéka obrázky co nejtěsněji.
Formát vstupního souboru
Vstupní soubor je formátován podle následujícího schématu
[Page] <height> <width> <k> <col_1_b> <col_1_e> <col_2_b> <col_2_e> ... <col_k_a> <borders> [Pictures] <m> <pic_1_TL_y> <pic_1_TL_x> <pic_1_BR_y> <pic_1_BR_x> <fillchar_1> <pic_2_TL_y> <pic_2_TL_x> <pic_2_BR_y> <pic_2_BR_x> <fillchar_2> ... <pic_m_TL_y> <pic_m_TL_x> <pic_m_BR_y> <pic_m_BR_x> <fillchar_m> [Text] ... [Align] left | right | centerNadpisy
[Page], [Pictures], [Text], [Align] jsou povinné a vyskytují se vždy
ve vstupním souboru. Položky <width> a <height> jsou celá čísla udávající počet sloupců a řádků
výstupního otisku, kladné celé číslo <k> udává počet sloupců textu ve výstupním otisku,
<col_i_b> resp. <col_i_e>
označují čísla sloupců výstupního otisku ve kterých začíná resp. končí i-tý sloupec textu.
První a poslední řádek a sloupec výstupního otisku jsou rezervovány pro rámec stránky.
Položka <borders> je vždy přítomna a představuje řetězec osmi znaků z1 ... z8 uzavřený v uvozovkách.
Znaky z2, z4, z5, z7 představují po řadě znaky horního, levého, pravého, dolního okrajů
rámce, znaky z1, z3, z6, z8 představují znaky v rozích rámce, po řadě to jsou levý horní, pravý horní,
levý dolní, pravý dolní.
Počet obrázků je dán nezáporným celým číslem <m>, i-tý odbdélník pro obrázek je zadán
číslem řádku a číslem sloupce svého levého horního rohu <pic_i_TL_y> <pic_i_TL_x>
a číslem řádku a číslem sloupce svého pravého dolního rohu <pic_i_BR_y> <pic_i_TL_x>.
Položka <fillchar_i> je jediný znak ve dvojitých úvozovkách, jímž je prostor pro
příslušný obrázek vyplněn ve výstupním otisku.
Za řádkem s nadpisem
[Text] následuje libovolný neprázdný počet řádků s textem, který máme
přeformátovat. Předpokládáme, že tento text obsahuje pouze tisknutelné znaky, žádný řádek
textu nezačíná (po případných úvodních mezerách) řetězcem [Align].
Za řádkem s nadpisem [Align] následuje jediný řádek s jediným slovem z množiny
{left, right, center}, které určuje zarovnání. Při zarovnání doleva leží všechna slova
ve výstupním řádku co možná nejvíce vlevo v tomto řádku, při zarovnání doprava
leží co možná nejvíce vpravo, při zarovnání na střed obsahuje výstupní řádek
buď stejný počet úvodních a koncových mezer nebo je počet koncových mezer o jedna
větší než počet úvodních mezer.
Řádek určující zarovnání je posledním řádkem vstupního souboru.
Předpokládáme, že všechny údaje jsou zadány korektně, sloupce výstupního textu se nepřekrývají, jednotlivé obrázky se rovněž nepřekrývají, žádný z uvedených objektů nekoliduje s rámcem výstupního otisku. Žádný řádek výstupního textu (i s uvážením případného omezení obrázky) nemá délku 1. Velikost výstupního otisku je alespoň 3 řádky krát 4 sloupce včetně rámce (v minimálním případě tak zbývají pro text dva znaky). Pro udržení jednoznačného plynutí textu na stránce také předpokládáme, že žádný obrázek není obsažen celý uvnitř jednoho sloupce tak, aby mohl být obtékán textem zleva i zprava.
Každý řádek vstupního souboru může obsahovat úvodní mezery, pokud řádek obsahuje více údajů, jsou odděleny alespoň jednou mezerou. Ty buňky výstupního otisku, které neobsahují ani text ani obrázek ani rámec, jsou vyplněny mezerami.
Příklad:
Vstup:[Page] 20 45 2 2 20 25 42 "o-o||o-o" [Pictures] 2 6 10 9 32 ":" 17 38 18 43 ":" [Text] Algorithm In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Starting from an initial state and initial input (perhaps null), the instructions describe a computation that, when executed, will proceed through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. [Align] leftVýstup:
o-------------------------------------------o | initial input | | Algorithm (perhaps null), | | the instructions | | In mathematics and describe a | | computer science, computation that, | | an algor:::::::::::::::::::::::when | | ithm is :::::::::::::::::::::::executed, | | an effec:::::::::::::::::::::::will | | tive :::::::::::::::::::::::proceed | | method expressed as through a finite | | a finite list of number of | | well-defined well-defined | | instructions for successive states, | | calculating a eventually | | function. producing "output" | | and terminating at | | Starting from an a final ::::::| | initial state and ending state.::::::| o-------------------------------------------o
Testovací data
Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.