Salut,
problema suna in felul urmator:
O broasca sta pe piatra nr. 1. El vrea sa visiteze fiecare piatra exact odata, in final ajungand pe piatra n. Broasca poate sari de pe o piatra pe alta daca se respecta urmatoarea conditie: piatra poate fi la 3 unitati distanta. In alte cuvinte, de pe piatra i, poate ajunge pe piatra j daca 1<=j<=n si j este in setul {i-3,i-2,i-1,i+1,i+2,i+3}
sa zicem ca f(n) este numarul total de rute posibile. Pentru f(6) avem 14 rute de mai jos
1 → 2 → 3 → 4 → 5 → 6
1 → 2 → 3 → 5 → 4 → 6
1 → 2 → 4 → 3 → 5 → 6
1 → 2 → 4 → 5 → 3 → 6
1 → 2 → 5 → 3 → 4 → 6
1 → 2 → 5 → 4 → 3 → 6
1 → 3 → 2 → 4 → 5 → 6
1 → 3 → 2 → 5 → 4 → 6
1 → 3 → 4 → 2 → 5 → 6
1 → 3 → 5 → 2 → 4 → 6
1 → 4 → 2 → 3 → 5 → 6
1 → 4 → 2 → 5 → 3 → 6
1 → 4 → 3 → 2 → 5 → 6
1 → 4 → 5 → 2 → 3 → 6
f(6)=14
alte exemple:
f(10) = 254 si f(40) = 1439682432976.
Sa zicem ca S(L) = ∑ f(n)^3 pentru 1 ≤ n ≤ L.
exemple:
S(10) = 18230635
S(20) = 104207881192114219
S(1 000) mod 10^9 = 225031475
S(1 000 000) mod 10^9 = 363486179
calculeaza S(10^14) mod 10^9.
Am creat u program care calculeaza rutele posibile. Calcularea tuturor rutelor e foarte costisitoare de aceea cred ca se poate calcula o formula pentru aflarea numarului rutelor.
de exemplu pentru n=40 calcularea tuturor rutelor dureaza 3 minute si creste exponential.
Ceva idei de plecare? Ce as putea cauta?
In general problemele de pe projecteuler nu se pot face doar cu o formula matematica. Exceptand 2-3 probleme din primele 100.
M-am gandit prima data la un PD, dar nu prea merge.
M-a pus pe ganduri cazul n=10 cu solutia 1–>4–>7–>9–>6–>3–>2–>5–>8–>10.
PS: Cate probleme ai rezolvate in total?