CSES - Listahyppy

Annettuna on lista, jossa on nn positiivista kokonaislukua. Lähdet liikkelle listan alusta ja tavoitteesi on päästä listan loppuun.

Kun olet alkion xx kohdalla, saat hypätä xx askelta vasemmalle tai oikealle. Et saa kuitenkaan tehdä hyppyä, joka veisi listan ulkopuolelle. Sinun tulee päästä listan loppuun niin, että hyppyjen kokonaismatka on mahdollisimman pieni.

Voit olettaa, että nn on enintään 10510^5, ja algoritmisi tulee toimia tehokkaasti kaikissa tapauksissa.

Toteuta tiedostoon listjump.py funktio calculate, joka antaa pienimmän kokonaismatkan (tai 1-1, jos ei ole mahdollista päästä listan loppuun).

def calculate(t):
    # TODO

if __name__ == "__main__":
    print(calculate([1, 1, 1, 1])) # 3
    print(calculate([3, 2, 1])) # -1
    print(calculate([3, 5, 2, 2, 2, 3, 5])) # 10
    print(calculate([7, 5, 3, 1, 4, 2, 4, 6, 1])) # 32

Selitys: Listassa [3,5,2,2,2,3,5][3,5,2,2,2,3,5] paras ratkaisu on hypätä ensin 33 askelta oikealle, sitten 22 askelta vasemmalle ja lopuksi 55 askelta oikealle. Tässä askelia on yhteensä 3+2+5=103+2+5=10.