Zadanie z programowania dynamicznego

Odpowiedz Nowy wątek
2018-02-13 00:11
Nieposkromiony Lew
0

https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/pir/

Proszę o wskazówki jak się za to zabrać, rozumiem, że każda kolejna obliczona wartość musi bazować na poprzednich, ale póki co stworzyłem kilka rozwiązań dających podobny rezultat i duże odchylenie od poprawnych odpowiedzi ;v

Pozostało 580 znaków

2018-02-13 04:12
0

Na pole n możesz wskoczyć z każdego z sześciu poprzednich pól, o ile na żadnym z nich nie ma pułapki. Liczba możliwości wskoczenia na pole n to suma możliwości wskoczeń na te sześć poprzednich pól.

Pozostało 580 znaków

2018-02-13 13:03
Krwawy Samiec
0

Właśnie tez do tego doszedłem :/ ale mimo wszystko wyniki mam zle

Pozostało 580 znaków

2018-02-13 15:51
0

Mocno nieoptymalne (tak sądzę), ale mam nadzieję, że poprawne dla małych wejść ;)
Spróbuj sobie podmieniać dane wejściowe (kliknij klonuj i edytuj stdin):

https://ideone.com/k1g2H3

edytowany 1x, ostatnio: Spine, 2018-02-13 15:51

Pozostało 580 znaków

2018-02-13 17:15
0
Krwawy Samiec napisał(a):

Właśnie tez do tego doszedłem :/ ale mimo wszystko wyniki mam zle

a nie zapominałeś robić modulo k po każdym sumowaniu, a nie tylko na samym końcu?

bo sam algorytm(bez wczytywania) to będzie miał z 5 linijek i ciężko gdzieś indziej zrobić błąd, no chyba że indeksy ...

Pozostało 580 znaków

2018-02-13 17:27
1
Spine napisał(a):

Mocno nieoptymalne (tak sądzę), ale mam nadzieję, że poprawne dla małych wejść ;)

Można dodać memoization przez wstawienie dwóch linii

import functools
 
@functools.lru_cache()
def rek(s, idx):

Pozostało 580 znaków

2018-02-13 17:38
Uczynny Jeleń
0

Robię wszędzie modulo k, mój algorytm jest iteracyjny i wykorzystuje sumy prefiksowe żeby można było się rozeznać ile wcześniejszych 6 pozycji nie zawiera w sobie pułapki.

Z resztą pokażę swój kod:

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
int getSum(vector<int> & prefix, int a, int b)
{
    if(a < 0)//gdyby sie okazalo ze i-6 jest ujemne
        a = 0;
 
    return prefix[b+1] - prefix[a];
}
 
int main(int argc, const char * argv[]) {
 
    int n,k;
    cin >> n >> k;
 
    char jumps[n];
    vector<int> prefix(n+1);
    prefix[0] = 0;
 
    for(int i = 0; i < n; i++)
    {
        cin >> jumps[i];
        if(jumps[i] == '1')
           prefix[i+1] = prefix[i] + 1;
       else
           prefix[i+1] = prefix[i];
    }
 
    vector<int> ways(1);//kolejne ilosci sposobów dojscia
    ways[0] = 1;//tj. start
 
    for(int i = 1; i < n; i++)
    {
        if(jumps[i] == '1')
        {
            ways.push_back(0);//nowa pozycja
            for(int j = 1; j <= getSum(prefix, i-6, i-1); j++)
                ways[ways.size()-1] = (ways[ways.size()-1]+ways[ways.size()-j-1])%k;//ilosc dojsc do nowej pozycji = suma dojsc do poprzednich pozycji oddalonych na odleglosc nie wieksza niz 6
        }
    }
 
    cout << ways[ways.size()-1] % k << endl;//ostateczny wynik
 
    return 0;
}
 

Pozostało 580 znaków

2018-02-13 17:43
Uczynny Jeleń
0

Już rozwiązane, problem polegał na tym, że przedtem ustawiałem zakres <i-6,i> zamiast <i-6,i-1> co zawierało w sobie obecną pozycję, ten kod wyżej jest poprawny, dziękuję wszystkim za zaangażowanie :D

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