1. Naloga

Zvončki

Imamo podano skladbo - zaporedje tonov, ki ga lahko predstavimo kot zaporedje števil med 0 in n. Podanih imamo m skupin po 10 različnih zvončkov, ki so postavljene ena ob drugi. Vsak zvonček igra nek vnaprej določen ton; v različnih skupinah so lahko zvončki, ki igrajo isti ton. Če stojimo pred skupino i, lahko zaigramo ton poljubnega zvončka iz skupin i, i-1 in i+1 (z nekaj izjemami na robovih: pri i = 1 skupina i-1 ne obstaja, pri i = m pa ne obstaja skupina i+1). Sicer se moramo premakniti do neke skupine, da tak zvonček dosežemo.  (Premaknemo se lahko do poljubne skupine, ne nujno le do sosednje.) Premikom bi se radi izognili. Opiši postopek, ki za dano zaporedje tonov ugotovi, s koliko minimalno premiki ga lahko zaigramo. Začetni položaj si lahko izberemo poljubno.

Primer: da bo manj pisanja, si oglejmo primer, v katerem imamo skupine po 3 zvončke namesto po 10 zvončkov, drugače pa je vse enako kot v zgornjem opisu naloge. Recimo, da imamo naslednjih m = 9 skupin:

i 1 2 3 4 5 6 7 8 9
zvončki v skupini i 1 5 7 2 9 8 8 7 6
2 1 3 4 4 6 9 0 5
3 4 8 5 2 1 3 5 3

In recimo, da bi radi zaigrali naslednje zaporedje devetih tonov:

7, 2, 3, 9, 0, 6, 5, 3, 2.

Potem je najmanjše potrebno število premikov enako 2. Dobimo ga na primer tako, da začnemo pri i = 2, kjer zaigramo tone 7, 2 in 3; nato se premaknemo na i = 8, kjer zaigramo tone 9, 0, 6 in 5; in nato se premaknemo na i = 1, kjer zaigramo še tona 3 in 2.