Cegły (omówienie)

Podstawą do rozwiązania tego zadania było rozpoznanie cech charakterystycznych wszystkich możliwych do osiągnięcia podziałów. Okazuje się, że podział stosu wielkości n jest możliwy do osiągnięcia wtedy i tylko wtedy, gdy składa się z parzystej liczby stosików o wielkościach będących liczbami pierwszymi. Przekładając to na język liczb, podział liczby n jest możliwy, jeśli składa się z parzystej ilości pierwszych składników. Oto dowód tego faktu:

Łatwo zauważyć, że każdy dopuszczalny podział musi składać się z parzystej liczby składników. Jeśli więc podział składa się z nieparzystej liczby składników lub któryś ze składników nie jest liczbą pierwszą, to od razu widać, że taki podział jest niemożliwy do osiągnięcia. Z drugiej strony, załóżmy że mamy dany podział liczby n na składniki p₁, p₂, ..., p_2k. Chłopcy mogli osiągnąć go np. dzieląc najpierw stos na: p₁ + p₂ + ... + p_k oraz: p_k+1 + ... + p_2k. Następnie każdy z nich w k-1 dalszych samodzielnych podziałach wydziela kolejne wartości p_i.

Pozostaje więc obliczyć ilość podziałów liczby na parzystą liczbę składników pierwszych. Do tego
celu można wykorzystać programowanie dynamiczne. Szczegóły można znaleźć w poniższym kodzie:

1
2
3
4
5
6
7
8

// vector p zawiera kolejne liczby pierwsze mniejsze niż 20000
// dp[k][0] = liczba podziałów liczby k na parzystą ilość składników pierwszych
// dp[k][1] = liczba podziałów liczby k na nieparzystą ilość składników pierwszych
dp[0][0] = 1;
for(int i=0; i<(int)p.size(); ++i)
        for(int j=p[i]; j<=20000; ++j)
                dp[j][0] = ( dp[j][0] + dp[j-p[i]][1] ) % MOD,
                dp[j][1] = ( dp[j][1] + dp[j-p[i]][0] ) % MOD;