Stavljenje besedila

 

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 dosežemo, 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.

Vhodni podatki

Tvoj program bo dobil na vhodu vec testnih primerov. V prvi vrstici vsakega testnega primera sta števili M in K, loceni s presledkom (M pove, kako širok stolpec besedila bi radi postavili); ta vrstica ne bo daljša od 30 znakov Naslednjih K vrstic vsebuje besedilo, ki ga moraš razlomiti. Zagotavljamo ti, da ne bo v tem besedilu nobena beseda daljša od M znakov. Pri tem je beseda definirana kot strnjeno zaporedje ne-presledkov, ki leži v celoti na eni vrstici in ga na obeh straneh obdajajo presledki ali pa zacetek/konec vrstice. Ce je torej med besedami v vhodni datoteki vec presledkov ali pa je kakšna vrstica celo prazna, moraš takšne presledke pac ignorirati. Veljalo bo 1 <= M <= 1000, 1 <= K <= 1000, vsaka od tistih K vrstic pa bo dolga najvec 1000 znakov (ne vštevši znaka za konec vrstice). Vhodna datoteka se konca z vrstico, ki vsebuje dve nicli namesto dopustnih vrednosti M in K. To ne šteje kot testni primer.

Izhodni podatki


Za vsak testni primer izpiši vrstico, v kateri je ocena najboljšega razloma besedila pri tistem testnem primeru. Zagotavljamo, da ta ocena pri nobenem testnem primeru ne bo presegala 1000000000.

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

Pripadajoca izhodna datoteka

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.