Wyjaśnienie polecenia ze skaczącą żabą

1

Otóż nie mogę pojąć tego zadania: https://app.codility.com/programmers/lessons/4-counting_elements/frog_river_one/

Jeżeli mamy znaleźć moment kiedy wszystkie pozycje są pokryte liścmi, to moim zdaniem wystarczy znaleźć czas najdluzej spadającego liścia i mamy problem z głowy, jednak rozwiązanie dla podanego przykładu jest inne, otóż rozwiązanie jest równe 6, a najdłużej liść spada w 5 sekund.
Czego tu nie rozumiem ?

0

Przeczytałeś w ogóle treść zadania? Spróbuj jeszcze raz.

1

To nie najdłużej spadający liść spada 5 sekund.
W tym przykładzie A[6] = 5 oznacza że w 6 sekundzie liść spadł na 5 pozycję.

Więc chodzi o to żeby znaleźć taki najwcześniejszy moment, w którym wszystkie X pozycji już wystąpiło.

1

W 6 tej sekundzie najwcześniej żaba może przejść - cała rzeka jest pokryta liśćmi (do X=5).

0

Znalazłem w sieci algorytm który niby generuje 100% punktów, jednak moich zdaniem jest on zły.

 private static int frog(int X, int[] A) {
        int steps = X;
        boolean[] bitmap = new boolean[steps+1];
        for(int i = 0; i < A.length; i++){
            if(!bitmap[A[i]]){
                bitmap[A[i]] = true;
                steps--;
            }
            if(steps == 0) return i;
        }
        return -1;
    }

Otóż dla
```
int X = 5;
int[] A = {1,3,1,4,2,3,5,4};

faktycznie zwraca dobrą wartość: 6, czyli A[6], jednak gdy dla X przymiemy wartość 4, powinno nam zwrócić 3 a zwraca 4. 
Czy mam rację ?
1

Nie. Nie masz racji. W sekundzie 3 nadal nie ma liścia na pozycji 2. Pojawia się dopiero w sekundzie 4.

1 użytkowników online, w tym zalogowanych: 0, gości: 1