Program | STAVLJENJE.C, STAVLJENJE.CPP, STAVLJENJE.PAS |
Odstavek besedila bi radi natisnili v pisavi, kjer so vsi znaki enako široki. Besedilo bo najbr predolgo, da bi celega napisali v eni vrstici, zato ga bo treba razlomiti na vec vrstic. Pri tem si elimo, da bi bile vse enako dolge, npr. po M znakov (izjema je zadnja vrstica, saj le-ta pri odstavkih obicajno nima poravnanega desnega roba); da to doseemo, bomo med besede po potrebi vrinili po vec kot en presledek (ce je med dvema besedama x presledkov, pravimo, da smo vrinili x – 1 dodatnih presledkov). Recimo torej, da smo besedilo razlomili v N vrstic, pri cemer je bilo treba v prvi vriniti P1 dodatnih presledkov, v drugi P2, itd., v predzadnji PN–1, v zadnji pa nobenega, saj smo rekli, da pri zadnji vrstici odstavka desnega roba pac ne poravnavamo. Na primer: ce imamo M = 15 in bi radi v neko vrstico postavili besede ena, dve in tri, imamo tu v osnovi devet crk in dva presledka (enega med ena in dve ter enega med dve in tri), tako da bo treba vriniti še štiri dodatne presledke (Pi = 4), da pridemo do 15 znakov. Ce v neko vrstico postavimo eno samo besedo, dolgo recimo L znakov, je treba v tako vrstico vriniti Pi = M – L dodatnih presledkov.
Nekateri razlomi so za oko prijetnejši, drugi manj (elimo si enakomerne gostote besedila); na primer: bolje je, ce moramo v dve vrstici vriniti po pet presledkov, kot ce jih vrinemo v eno deset in v drugo nobenega. Zato je dobro, ce veliki Pi na oceno razloma vplivajo veliko bolj kot majhni. Definirajmo oceno razloma kot vsoto kubov P13 + P23 + ... + PN–13 ; manjša ko je ta ocena, boljši je razlom. Tvoja naloga je napisati program, ki bo znal za dano besedilo dolociti oceno najboljšega razloma.
Primer vhodne datoteke
20 4
aaa bbb ccc dddd eee fffffff g
hh i jjj kk lll mm nnn oooo
pp
qq rrr ss tttt uu
vvvv www xxx yy zzz
aa bbb
cccc dd eee ff ggg hh
0 0
25
To, mimogrede, ustreza naslednjemu razlomu besedila:
aaa bbb ccc dddd eee
(0 dodatnih presledkov = 0 kazenskih toek)
fffffff g hh i jjj (2 dodatna presledka= 8 kazenskih toek)
kk lll mm nnn oooo (2 dodatna presledka= 8 kazenskih toek)
pp qq rrr ss tttt uu (0 dodatnih presledkov = 0 kazenskih toek)
vvvv www xxx yy zzz (1 dodaten presledek
= 1 kazenska toeka)
aa bbb
cccc dd eee (2 dodatna presledka= 8 kazenskih toek)
ff ggg hh (0 dodatnih presledkov
= 0 kazenskih toek)
Skupaj torej res dobimo oceno razloma 25.