Matematická olympiáda – kategorie P

Zadání úloh ústředního kola (2. soutěžní den) 50. ročníku

P-III-4 Formátování textu

Program: FORMAT.PAS / FORMAT.C / FORMAT.CPP
Vstup: FORMAT.IN
Výstup: FORMAT.OUT

Pro textový editor potřebujeme napsat program sloužící k formátování textu. Editor pracuje ve znakovém režimu s neproporcionálním písmem. Všechny znaky tedy mají stejnou šířku a také mezera má pevnou šířku stejnou jako každý jiný znak. Rovněž pomocné symboly obsažené v textu (jako jsou interpunkční znaménka, závorky či uvozovky) se zpracovávají stejně jako jakékoliv jiné znaky. Editor je poměrně jednoduchý, takže dělení slov nepřipouští. Program budeme používat vždy k formátování jednoho odstavce textu.

Pro potřeby formátování rozumíme slovem každou souvislou posloupnost nemezerových znaků, která je na obou koncích ukončena mezerou nebo začátkem či koncem řádku. Pomocné symboly obsažené v textu jsou tedy součástí těch slov, od nichž nejsou odděleny mezerou.

Cílem formátování textu je vhodné rozložení slov na jednotlivé řádky tak, aby byl celý text zarovnán "do bloku" (tzn. k levému i pravému okraji) při zadané šířce řádku. Přitom mezery mezi slovy musí být co možná nejmenší a v textu co nejrovnoměrněji rozloženy. Tyto obecné požadavky si nyní upřesníme: Velikosti mezer mezi slovy na témže řádku (kromě posledního řádku odstavce) se mohou lišit maximálně o 1, před prvním a za posledním slovem na řádku nesmí být mezera. Pokud je na řádku pouze jedno slovo, je rozložení mezer libovolné. Na posledním řádku odstavce musí být slova oddělena právě jednou mezerou a před prvním slovem nesmí být mezera.

Splńuje-li text tyto závazné požadavky, potom kvalitu zformátování odstavce hodnotíme trestnými body. Ohodnocení odstavce je součtem ohodnocení jednotlivých řádků. Ohodnocení jednoho řádku je dáno výsledkem funkce F(Width, Chars, Words, Last), kde Width je šířka stránky (tj. počet znaků na řádce zformátovaného textu včetně všech mezer), Chars je počet nemezerových znaků na řádce, Words je počet slov na řádce a Last značí, zda se ohodnocuje poslední řádek odstavce či nikoliv.

Ohodnocovací funkce F zapsaná v programovací jazyce C vypadá následovně:

int F(int Width, int Chars, int Words, int Last) { int Spaces = Width - Chars - Words + 1; /* Počet zbytečných mezer */ int BasePen = LINEPENALTY; /* Základní trestné body za řádek */ if (Spaces < 0) /* Nevejde se text na řádek? */ return INFTYPEN; if (Last) /* Poslední řádek? */ { if (4*(Chars + Words - 1) <= Width) /* Je poslední řádek moc krátký? */ BasePen += SMALLLINEPEN; return BasePen; } if (Words == 1) /* Pouze jedno slovo na řádku? */ BasePen += SINGLEWORDPEN; return Spaces * Spaces + BasePen; /* Ohodnocení celého řádku */ } V Pascalu je zápis funkce F obdobný: function F(Width, Chars, Words: Integer; Last: Boolean): Integer; var Spaces : Integer; { Počet zbytečných mezer na řádku } BasePen : Integer; { Základní trestné body za řádek } begin BasePen := LINEPENALTY; Spaces := Width - Chars - Words + 1; if Spaces < 0 then { Nevejdou se slova na řádek? } F := INFTYPEN else if Last then begin { Ohodnocujeme poslední řádek? } if 4*(Chars + Words - 1) <= Width then { Je řádek moc krátký? } Inc(BasePen, SMALLLINEPEN); F := BasePen; end else begin if Words = 1 then { Je jen jedno slovo na řádku? } Inc(BasePen, SINGLEWORDPEN); F := Spaces * Spaces + BasePen; { Spočteme výsledné ohodnocení } end; end; Hodnoty konstant jsou: LINEPENALTY=10 SMALLLINEPEN=5 SINGLEWORDPEN=20 INFTYPEN=30 000 Vaším úkolem je zformátovat odstavec textu při zadané šířce řádku co nejkvalitněji, tzn. splnit všechny závazné požadavky kladené na formátování a přitom dosáhnout co nejnižšího ohodnocení odstavce trestnými body podle funkce F.

Vstup

Ve vstupním souboru FORMAT.IN je na prvním řádku zadána požadovaná šířka stránky po zformátování. Na dalších řádcích se nachází text odstavce určený ke zformátování. Můžete předpokládat, že žádný z těchto řádků není delší než 100 znaků, na začátku ani na konci žádného řádku není mezera a mezi jednotlivými slovy na řádku je vždy právě jedna mezera. Vstupní soubor nebude delší než 10 000 znaků (počítáno včetně mezer mezi slovy).

Výstup

Do výstupního souboru FORMAT.OUT zapište zadaný text odstavce zformátovaný co nejkvalitněji podle výše uvedených zásad (tj. s nejnižší možnou hodnotou ohodnocovací funkce).

Příklad

FORMAT.IN 40 Each section in this document will have the string "<section>" at the right-hand side of the section title. Each subsection will have "<subsection>" at the right-hand side. These strings are meant to make it easier to search through the document. FORMAT.OUT (jedno z možných řešení; symbol `_' označuje mezeru) Each__section__in__this__document___will have__the__string__"<section>"__at___the right-hand_side_of__the__section__title. Each_subsection_will_have_"<subsection>" at_the_right-hand__side.__These__strings are_meant_to_make_it__easier__to__search through_the_document.

P-III-5 Okružní jízdy

Program: OKRUZNI.PAS / OKRUZNI.C / OKRUZNI.CPP
Vstup: OKRUZNI.IN
Výstup: OKRUZNI.OUT

Ve městě Turiststadt začal vzkvétat turistický ruch. Aby podpořili jeho další rozkvět, rozhodli se moudří radní založit společnost City-tour. Posláním této společnosti je provozovat ve městě několik vyhlídkových okružních autobusových linek. Vaším úkolem je vytvořit program, který navrhne trasy vyhlídkových autobusových linek městem podle požadavků radních, popřípadě zjistí, že autobusové linky nelze dle jejich požadavků vytvořit.

Město je tvořeno křižovatkami, které jsou navzájem spojeny ulicemi. Každá ulice spojuje právě dvě křižovatky. Dvě stejné křižovatky mohou být spojeny více různými ulicemi. Křižovatkou rozumíme i místo, do kterého vede jen jedna nebo dvě ulice. Radní kladou na plánované trasy autobusových linek následujíci požadavky: Aby si turisté mohli pohodlně prohlédnout každou ulici ve městě a přitom se zbytečně neplýtvalo náklady na provoz autobusových linek, musí každou ulicí projíždět právě jedna autobusová linka. Žádná z linek nesmí projet některou z křižovatek více než jednou. Trasy linek musí být navrženy tak, aby první a poslední křižovatka na trase byla stejná - jinak by se linky provozované touto společností daly jen stěží nazývat okružní.

Vstup

První řádek vstupního souboru OKRUZNI.IN obsahuje dvě čísla oddělená mezerou -- počet křižovatek (N, 1<=N<=120) a počet ulic (M). Křižovatky jsou očíslovány čísly od 1 do N. Následujících M řádků vstupního souboru obsahuje popis jednotlivých ulic ve městě: Každý z těchto řádků obsahuje dvě čísla představující čísla křižovatek, které příslušná ulice spojuje. První číslo na každém z těchto řádků je menší než druhé z nich. Tyto řádky jsou v souboru setříděny podle prvního čísla; v případě, že se shoduje více ulic v prvním čísle, jsou setříděny podle druhého čísla. Můžete předpokládat, že počet různých ulic spojujících dvě stejné křižovatky je nejvýše 200.

Výstup

Výstupní soubor OKRUZNI.OUT obsahuje tolik řádků, kolik má společnost provozovat autobusových linek. Každý řádek obsahuje popis právě jedné autobusové linky. Trasa autobusové linky je popsána jako posloupnost čísel křižovatek, kterými linka projíždí. První a poslední číslo uvedené na řádku je tedy stejné (linka začíná a končí na stejné křižovatce). Jednotlivá čísla jsou na každém řádku oddělena právě jednou mezerou. Pokud nelze trasy linek navrhnout tak, aby vyhovovaly podmínkám ze zadání úlohy, potom výstupní soubor obsahuje jediný řádek se slovem "Nelze".

Příklad 1

OKRUZNI.IN 5 12 1 2 1 2 1 2 1 2 1 3 1 3 2 3 2 5 3 4 3 5 3 5 4 5 OKRUZNI.OUT 1 2 3 1 2 1 2 3 4 5 3 2 5 3 1 2

Příklad 2

OKRUZNI.IN 3 4 1 2 1 2 1 3 2 3 OKRUZNI.OUT Nelze