Annettuna on lista, jossa on n alkiota. Jokainen alkio on kokonaisluku väliltä 1 \dots n.

Lähdet liikkelle listan alusta, ja aina kun olet alkion x kohdalla, saat hypätä x askelta vasemmalle tai oikealle. Et saa kuitenkaan tehdä hyppyä, joka veisi listan ulkopuolelle. Tavoitteesi on päästä listan loppuun niin, että hyppyjen kokonaismatka on mahdollisimman pieni.

Esimerkiksi listassa [3,5,2,2,2,3,5] paras ratkaisu on hypätä ensin 3 askelta oikealle, sitten 2 askelta vasemmalle ja lopuksi 5 askelta oikealle. Tässä askelia on yhteensä 3+2+5=10.

Voit olettaa, että n on enintään 10^5. Jos mitään ratkaisua ei ole olemassa, palauta -1.

Python

Toteuta tiedostoon listjump.py funktio calculate, joka antaa pienimmän kokonaismatkan.

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

Java

Toteuta tiedostoon ListJump.java metodi calculate, joka antaa pienimmän kokonaismatkan.

public class ListJump {
    public long calculate(int[] t) {
        // TODO
    }

    public static void main(String[] args) {
        ListJump l = new ListJump();
        System.out.println(l.calculate(new int[] {1,1,1,1})); // 3
        System.out.println(l.calculate(new int[] {3,2,1})); // -1
        System.out.println(l.calculate(new int[] {3,5,2,2,2,3,5})); // 10         
        System.out.println(l.calculate(new int[] {7,5,3,1,4,2,4,6,1})); // 32
    }
}