4. naloga

Pisalni stroj

Imamo pisalni stroj, ki deluje tako, da se ob vsakem izpisu znaka nujno pomakne za eno mesto v desno. (Eden od teh znakov je tudi presledek, ki sicer ne izpiše ničesar, nas pa ravno tako premakne za eno mesto v desno.) Poleg tega obstaja tudi tipka za pomik na začetek trenutne vrstice (carriage return). Drugih možnosti za premik v levo nimamo. Radi bi napisali neko vrstico tako, da bo ponekod na istem mestu več črk ena čez drugo (npr. da kaj podčrtamo z znakom _, prekrižamo z znakom x, dodamo kakšno naglasno znamenje nad črko in podobno). Recimo, da bo vrstica na koncu dolga n znakov, pri čemer hočemo na mestu i natipkati ai znakov. Opiši postopek, ki iz teh podatkov (torej števil n, a1, a2, ... , an) izračuna, kolikšno je najmanjše število pritiskov na tipke (med pritiske šteje tudi pomik na začetek vrstice), ki jih potrebujemo, da natipkamo to vrstico. Pri tem ni pomembno, kje v vrstici se nahajamo na koncu tipkanja. Tvoja rešitev naj bo čim bolj učinkovita, da bo delovala hitro tudi v primerih, ko so n in števila ai zelo velika.

Primer. Recimo, da hočemo natipkati takšno vrstico dolžine n = 6:

Tabela a bi bila torej v tem primeru takšna:

i 1 2 3 4 5 6
ai 2 1 3 0
2 1
Minimalno potrebno število pritiskov na tipke je v tem primeru 16. Primerno zaporedje (ni pa edino) tipk je: a, b, c, presledek, d, e, pomik na začetek,  ̈, presledek, vejica, presledek, _, pomik na začetek, presledek, presledek in ^.