Ř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.