Cegły - jak rozwiązać

ďťż

Rafał Stafański - 6 sie 2010, o 17:05
" />Bardzo interesuje mnie rozwiązanie zadania Cegły. Bardzo mi się to zadanie spodobało, niestety zdołałem wymyślić algorytm, który działa w czasie kwadratowym, więc nie zmieści się w limicie czasowym. Jakie są wasze rozwiązania?

Przemysław Derengowski - 6 sie 2010, o 17:06
" />O(ilePierwszych*n) to jest problem wydawania reszty na różną liczbę sposobów, za pomocą parzystej liczby monet - sprytnie zakamuflowany

Łukasz Kalinowski - 6 sie 2010, o 17:12
" />A że ilość liczb pierwszych mniejszych od n jest rzędu n / log n, więc jest O(n^2 / log n) a ja nie miałem skojarzenia z problemem wydawania reszty, ale możliwe, że mamy ten sam algorytm

Łukasz Solak - 6 sie 2010, o 17:13
" />Też mam wydawanie reszty w O(n^2/lgn)

Kamil Wajda - 6 sie 2010, o 17:22
" />A mógłby ktoś szerzej o tym algorytmie powiedzieć? Bo zwyczajne wydawanie reszty of cuz znam, ale problemu w postaci 'na ile sposobow mozna' to nie znam, a widze ze gogle tez za bardzo nie.

Łukasz Solak - 6 sie 2010, o 17:31
" />f(n, d) = liczba sposobów przedstawienia N, za pomocą parzystej liczby, pierwszych d liczb pierwszych.
k(n, d) = liczba sposobów przedstawienia N, za pomocą nieparzystej liczby, pierwszych d liczb pierwszych.
p[d] - d-ta liczba pierwsza
I mamy równanie rekurencyjne
f(n,d) = f(n, d - 1) + k(n-p[d], d)
k(n,d) = k(n, d - 1) + f(n-p[d], d)

Odpowiedź wymagana w zadaniu to właśnie f(n,d_max), które obliczamy rekurencyjnie.
Kawałek kodu:

Kamil Wajda - 6 sie 2010, o 17:39
" />O jejusku, byłem blisko, tylko nie wiedzieć czemu, sumowanie k(n-p[d], d) chciałem robić po wszystkich p[d] <= n... cóż życie

Darmowy hosting zapewnia PRV.PL