ACM RTK - 1. skupina

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 a_i znakov. Opiši postopek, ki iz teh podatkov (torej števil n, a₁, a₂, ... , a_n) 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 a_i 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 ^.