Matematická olympiáda – kategorie P

Řešení úloh ústředního kola (2. soutěžní den) 50. ročníku

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

Řešení této úlohy je založeno na dynamickém programování. Pro každé slovo si budeme pamatovat, kde nejlépe zalomit předchozí řádek, když toto slovo bude na konci řádku. Také si budeme pamatovat celkový počet trestných bodů textu při tomto zalomení. Když spočítáme nejlepší zalomení pro poslední slovo, můžeme ze zapamatovaných informací snadno zrekonstruovat, jak celý text zalámat. Z informací u posledního slova zjistíme, za kterým slovem měl být zalomen předposlední řádek. Z informací u posledního slova na předposledním řádku zjistíme, kde měl být zalomen předpředposlední řádek atd. Když víme, kde měly být jednotlivé řádky zalámány, stačí již jen správně doplnit mezi vypisovaná slova mezery. To uděláme tak, že pokud máme umístit M mezer mezi S+1 slov, tak vytvoříme M mod S oddělení slov s (M div S)+1 mezerami a S-(M mod S) oddělení s M div S mezerami. Tím se zjevně žádná dvě oddělení slov neliší o více jak jednu mezeru a počet mezer na řádce je také správný. Formátování posledního řádku a řádku s jedním slovem jsou triviální.

A nyní již k zajímavé části algoritmu. Jak rychle spočítat, kde nejlépe zalomit předchozí řádek, když bude aktuální slovo na konci řádku? Tuto informaci budeme postupně počítat od prvního slova. U prvního slova nastavíme počet trestných bodů i místo zalomení na nula. Když máme spočteny hodnoty pro prvních N slov, začneme je počítat pro slovo (N+1)-ní. Jdeme od N-tého slova směrem k začátku textu. Pro každé slovo si spočteme počet trestných bodů za řádek, který začíná za ním a končí (N+1)-vým slovem (pokud je (N+1)-ní slovo posledním v textu, bude jím ukončovaná řádka řádkou poslední, a tak hodnotící funkci informujeme, že hodnotí poslední řádku). K tomuto počtu trestných bodů ještě přičteme trestné body za předchozí text (ty máme již spočteny a uloženy u slova, za kterým jsme se rozhodli řádek zlomit) a zjistíme, zda jsme získali pro (N+1)-ní slovo text s menším počtem trestných bodů. Pokud ano, zapamatujeme si počet bodů pro tento text a místo zalomení. Když už je poslední řádek moc dlouhý (hodnotící funkce nám vrátila nekonečno), tak víme, že už lepší zalomení nenajdeme. Prošli jsme už totiž všechna možná zalomení předposledního řádku a vybrali z nich to nejlepší. Můžeme tedy počítat hodnoty pro další slovo. Algoritmus má časovou složitost O(T+WL), kde T je délka textu, W je počet slov a L je délka řádku. Paměťová složitost algoritmu je O(T). Správnost algoritmu plyne z popisu.

Program je přímou implementací algoritmu:

#include <stdio.h> #include <stdlib.h> #define INPUT "format.in" #define OUTPUT "format.out" #define TEXTLEN 10000 /* Maximalni delka textu */ #define MAXWORDS 5000 /* Maximalni pocet slov v textu */ #define MAXLINELEN 100 /* Maximalni delka vstupni radky */ #define MAXLINES 5000 /* Maximalni pocet radek ve vystupu */ #define LINEPENALTY 10 /* Cena radky */ #define LASTLINESMALLPEN 3 /* Cena za maly posledni radek */ #define SINGLEWORDPEN 20 /* Penalta za jedno slovo na radku */ #define INFTYPEN 30000 /* Nekonecna penalta */ typedef unsigned long price_t; int Width; /* Sirka radku */ char Text[TEXTLEN]; /* Text nacteny ze souboru */ int Words[MAXWORDS]; /* Text rozsekany na slova */ int WCnt; /* Pocet slov */ price_t WrapPrice[MAXWORDS]; /* Ohodnoceni textu, pokud zalomime za timto slovem */ int WrapPos[MAXWORDS]; /* Pozice, kde jsme zalomili, kdyz jsme pridavali toto slovo */ /* Ohodnoti radek */ int LinePrice(int WordLen, int Words, int Last) { int Pts = Width - WordLen - Words + 1; int Base = LINEPENALTY; if (Pts < 0) return INFTYPEN; if (Last) return LINEPENALTY + (((WordLen+Words-1)*4 < Width) ? LASTLINESMALLPEN : 0); if (Words == 1) Base += SINGLEWORDPEN; return Pts * Pts + Base; } /* Nacte vstup a rozdeli ho na slova */ void ProcessInput(void) { FILE *In; char Buf[MAXLINELEN]; /* Buffer na radku */ int i, TPos = 0, WPos = 0; /* ; Pozice v bufferu na text ; Cislo aktualniho slova */ int SWPos = 0; /* Pozice pocatku slova */ if (!(In = fopen(INPUT, "r"))) { puts("Can't open input file."); exit(1); } /* Nacteme delku radku */ fgets(Buf, MAXLINELEN, In); sscanf(Buf, "%d", &Width); while (fgets(Buf, MAXLINELEN, In)) { for (i = 0; Buf[i] != '\0'; i++, TPos++) { if (Buf[i] == '\n') Buf[i] = ' '; Text[TPos] = Buf[i]; if (Buf[i] == ' ') { Words[WPos++] = TPos - SWPos; SWPos = TPos + 1; } } } fclose(In); WCnt = WPos; } void FindBestSep(void) { int i, j; price_t Min, Price; /* Minimalni dosazene ohodnoceni; Cena aktualniho zlomu */ int WordsLen, MinPos; /* Celkova delka slov na radce; Pozice minimalniho zalomeni */ WrapPrice[0] = 0; WrapPos[0] = 0; for (i = 0; i < WCnt; i++) /* Postupne pridavame jednotliva slova */ { Min = INFTYPEN; MinPos = 0; WordsLen = 0; for (j = i; j >= 0; j--) /* Vyzkousime vsechna mozna zalomeni */ { WordsLen += Words[j]; Price = LinePrice(WordsLen, i - j + 1, i == WCnt - 1); if (Price == INFTYPEN) /* Uz jsem prekrocili velikost radku? */ break; Price += WrapPrice[j]; if (Price < Min) { Min = Price; MinPos = j; } } WrapPrice[i+1] = Min; WrapPos[i+1] = MinPos; } } /* Vytiskne dalsi slovo */ void PrintWord(FILE *Out) { static int WPos = 0; /* Pozice slova k vypsani */ int WStart; for (WStart = WPos; Text[WPos] != ' '; WPos++); fwrite(Text + WStart, 1, WPos - WStart, Out); WPos++; } /* Vytiskne radku */ void PrintLine(FILE *Out, int First, int Cnt) { int i, j; int Len = 0, TotSpc; /* Pocet znaku na radce; Celkovy pocet mezer */ int Spc; /* Pocet mezer v aktualni mezere */ /* Spocteme pocet znaku ve slovech */ for (i = 0; i < Cnt; i++) Len += Words[First+i]; TotSpc = Width - Len; if (Cnt == 1) /* Jedno slovo? */ { for (j = 0; j < TotSpc; j++) fputc(' ', Out); } else for (i = 0; i < Cnt-1; i++) { PrintWord(Out); /* Vytiskne dalsi slovo */ /* Spocteme a vytiskneme potrebny pocet mezer */ Spc = TotSpc / (Cnt - 1) + (i < TotSpc % (Cnt-1)); for (j = 0; j < Spc; j++) fputc(' ', Out); } PrintWord(Out); /* Jeste vytiskneme posledni slovo */ fputc('\n', Out); } /* Vypiseme nejlepsi vysledek */ void PrintBestText(void) { FILE *Out; int Lines = 0, ActWord; /* Pocet radek vysledneho textu; Aktualni slovo */ int LB[MAXLINES], i; /* Pozice jednotlivych zalomeni */ /* Zjistime pozice jednotlivych zalomeni */ for (ActWord = WCnt; ActWord > 0; Lines++, ActWord = WrapPos[ActWord]) LB[Lines] = ActWord; LB[Lines] = 0; if (!(Out = fopen(OUTPUT, "w"))) { puts("Can't open output file."); exit(1); } /* Nechame vytisknout radku */ for (i = Lines - 1; i > 0; i--) PrintLine(Out, LB[i+1], LB[i] - LB[i+1]); /* Ted jeste vytiskneme posledni radku */ for (i = LB[1]; i < LB[0] - 1; i++) { PrintWord(Out); fputc(' ', Out); } PrintWord(Out); fputc('\n', Out); fclose(Out); } int main(void) { ProcessInput(); /* Nacte vstup a rozdeli ho na slova */ FindBestSep(); /* Nalezneme nejlepsi rozdeleni na radky */ PrintBestText(); /* Vypise text podle spoctenych zalomeni */ return 0; }

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

Nejprve si rozmysleme, že platí následující tvrzení: Trasy linek městem lze navrhnout právě tehdy, pokud ze všech křižovatek vychází sudý počet ulic. Kdybychom si trasy jednotlivých linek vyznačili různými barvami v plánu města, potom by každá z nich tvořila cyklus. Každá ulice by měla jednoznačně určenu svou barvu. Pokud si trasy linek zakreslíme do mapy, bude z každé křižovatky vycházet buď žádná nebo právě dvě ulice od jedné určité barvy - žádná, pokud trasa příslušné barvy křižovatkou neprochází, a dvě, pokud ano; více ulic stejné barvy nemůže z křižovatky vycházet, neboť každá linka projíždí křižovatkou nejvýše jedenkrát. Obarvení ulic v mapě tedy "páruje" ulice vycházející z křižovatky a tudíž počet ulic vycházejících z jedné křižovatky musí být sudý.

Nyní si naopak rozmysleme, že pokud z každé křižovatky vychází sudý počet ulic, potom lze navrhnout trasy linek tak, aby splňovaly požadavky zadání úlohy. Postupně obarvujme ulice ve městě tak, aby ulice stejné barvy tvořily cyklus (tj. odpovídaly nějaké autobusové lince). Ulice, které jsme již obarvili, nebudeme nadále považovat za součást města; tím zmenšíme počet ulic vycházejících z jedné křižovatky o sudé číslo (o nulu nebo o dvě), takže počet ulic vycházejících z každé křižovatky bude stále sudý. Vyberme si nějakou křižovatku ve městě a označme si ji na mapě (položme do ní kamínek); vydejme se z této křižovatky po libovolné (dosud neobarvené) cestě a položme do křižovatky, do které jsme dorazili, kamínek. Z každé křižovatky lze vždy pokračovat alespoň jednou ulicí - do křižovatky jsme po jedné ulici přišli, a protože počet neobarvených ulic, které z ní vedou, je sudý, musí z ní vést tedy alespoň dvě neobarvené ulice - tou druhou můžeme pokračovat. Skončíme, pokud bychom na nějakou křižovatku měli položit druhý kamínek - tehdy jsme našli cyklus z ulic a tento cyklus obarvíme nějakou dosud nepoužitou barvou (a prohlásíme ho za novou autobusovou linku). Kamínky odstraníme z mapy a celý proces opakujeme tak dlouho, dokud mapa města obsahuje nějaké neobarvené ulice.

Předchozí důkaz nám dává návod k vytvoření algoritmu, který řeší zadanou úlohu. Nejprve ověříme, zda z některé křižovatky vychází lichý počet ulic; je-li tomu tak, potom rovnou vypíšeme Nelze. V opačném případě začneme aplikovat postup z minulého odstavce; kamínky samozřejmě nahradíme nastavováním vhodného příznaku v programu. Pokud nalezneme cyklus, příslušné ulice z mapy rovnou vymažeme a cyklus vypíšeme na výstup. Abychom ušetřili čas, ponecháme v mapě "kamínky" na křižovatkách, které jsou mezi výchozí křižovatkou a křižovatkou, kam jsme měli položit dva kamínky; na tyto křižovatky bychom mohli položit kamínky i ve městě, ve kterém by byl vynechán právě nalezený cyklus. Pokládání kamínků budeme realizovat jednoduchou rekurzivní funkcí. Zbývá vyřešit, jak právě obarvené ulice rychle odstraňovat z mapy města uložené v paměti počítače. Ulice spojující dvě stejné křižovatky si budeme pamatovat jako jednu ulici s uvedením počtu ulic, které vedou paralelně s touto ulicí (tj. spojují dvě stejné křižovatky). Ulice si uložíme do dvojrozměrného pole; jeden jeho index bude představovat číslo křižovatky a jeho druhý index bude představovat pořadové číslo ulice vycházející z dané křižovatky. Rozměry tohoto pole tedy budou počet křižovatek "krát" maximální počet ulic vycházejících z jedné křižovatky. U každé křižovatky jsou uvedeny všechny ulice, které z ní vycházejí. U každé ulice si pamatujeme, kam vede, kolik ulic s ní vede paralelně a index do pole určující, kde jsou informace o této ulici rovněž uloženy u křižovatky na jejím opačném konci. Příslušnou ulici vymažeme jednoduše tak, že upravíme informace o ní u obou křižovatek, které spojuje, což lze provést v konstantním čase, neboť si pamatujeme její index u druhé křižovatky.

Paměťové i časové nároky našeho algoritmu jsou O(N+M), kde N je počet křižovatek ve městě a M je počet ulic ve městě. Paměťové nároky algoritmu lze reprezentací pouze jedné z paralelních hran (viz minulý odstavec) snížit na O(N+H), kde H je maximální počet ulic, z nichž žádné dvě nejsou paralelní.

program okruzni; { P-III-5 } const MAXN=120; { Maximální hodnoty dle zadání } MAXD=MAXN-1; { ... počet ulic z jedné křižovatky } MAXM=200; { ... počet paralelních ulic mezi dvěma křižovatkami } type tkriz=byte; { typy pro data } tulic=byte; tmult=byte; type ulice=record { záznam o skupině paralelních ulic } kam:tkriz; ind:tulic; mul:tmult; end; var mapa:array[1..MAXN,1..MAXD] of ulice; { mapa města } ulicdo:array[1..MAXN] of tulic; { počet neparalelních ulic do jedné křižovatky } ulicsudy:array[1..MAXN] of boolean; { je počet ulic vycházejících z křižovatky sudý? } navst:array[1..MAXN] of boolean; { "kamínky" při budování nové linky } kriz:tkriz; ulic:longint; i,j:tkriz; k:longint; vstup,vystup:text; procedure vybuduj(od:tkriz;var posl:tkriz); { kamínkovací procedura } var pokr:tkriz; begin if navst[od] then begin posl:=od; write(vystup,od,' ') end else repeat navst[od]:=true; pokr:=mapa[od,ulicdo[od]].kam; if mapa[od,ulicdo[od]].mul>1 then begin dec(mapa[od,ulicdo[od]].mul); dec(mapa[pokr,mapa[od,ulicdo[od]].ind].mul); end else begin mapa[pokr,mapa[od,ulicdo[od]].ind]:=mapa[pokr,ulicdo[pokr]]; mapa[mapa[pokr,ulicdo[pokr]].kam,mapa[pokr,ulicdo[pokr]].ind].ind:= mapa[od,ulicdo[od]].ind; dec(ulicdo[pokr]); dec(ulicdo[od]); end; vybuduj(pokr,posl); navst[od]:=false; if posl<>od then begin write(vystup,od,' '); exit end; writeln(vystup,od) until ulicdo[od]=0 end; begin assign(vstup,'okruzni.in'); assign(vystup,'okruzni.out'); reset(vstup); rewrite(vystup); { Nejprve načteme vstup ... } readln(vstup,kriz,ulic); for i:=1 to kriz do begin ulicdo[i]:=0; navst[i]:=false; ulicsudy[i]:=true; end; for k:=1 to ulic do begin readln(vstup,i,j); ulicsudy[i]:=not ulicsudy[i]; ulicsudy[j]:=not ulicsudy[j]; if (ulicdo[i]>0) and (mapa[i,ulicdo[i]].kam=j) then begin inc(mapa[i,ulicdo[i]].mul); inc(mapa[j,ulicdo[j]].mul); end else begin inc(ulicdo[i]); inc(ulicdo[j]); mapa[i,ulicdo[i]].kam:=j; mapa[i,ulicdo[i]].ind:=ulicdo[j]; mapa[i,ulicdo[i]].mul:=1; mapa[j,ulicdo[j]].kam:=i; mapa[j,ulicdo[j]].ind:=ulicdo[i]; mapa[j,ulicdo[j]].mul:=1; end end; { Má úloha řešení? } for i:=1 to kriz do if not ulicsudy[i] then begin writeln(vystup,'Nelze'); close(vstup); close(vystup); halt end; { Pokud ano, tak ho nalezneme ... } for i:=1 to kriz do if ulicdo[i]>0 then vybuduj(i,j); close(vstup); close(vystup) end.