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

Odpowiedz Nowy wątek
2018-11-10 14:41
1

Otóż nie mogę pojąć tego zadania: https://app.codility.com/prog[...]ting_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 ?

Pozostało 580 znaków

2018-11-10 15:13
0

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

stary, co to za głupia odzywka, myślisz że nie czytałem i zadaje pytanie ? Kolejny sfrustrowany :) - watpliwosci 2018-11-10 15:17
Myślę, że to jest poważna sugestia, że nie przeczytałeś. - enedil 2018-11-10 15:32

Pozostało 580 znaków

2018-11-10 15:13

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.

Pozostało 580 znaków

2018-11-10 15:20
1

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


edytowany 1x, ostatnio: lion137, 2018-11-10 22:24

Pozostało 580 znaków

2018-11-10 16:28
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ę ?

Pozostało 580 znaków

2018-11-10 22:23
1

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

edytowany 1x, ostatnio: nalik, 2018-11-10 22:23

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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