963 Nkbiti

[•stef2n]

Aici puteti discuta despre problema Nkbiti.

[•savim]

In enunt nu prea sunt respectate conventiile de formatare...http://infoarena.ro/documentatie/conventii-de-formatare

[•pauldb]

Cred ca acum arata ceva mai bine.

[•Badu]

Salut, am gasit la aceasta problema o solutie bazata pe recurente gen sirul lui fibonacci, dar se pare ca iau decat 20 de puncte astfel.
Daca k = 1 atunci este generat sirul lui fibonacci, pentru k = 2 recurenta este B(n,2) = B(n-1,2) + B(n-2,2) + B(n-3,2) , B(n,k) = B(n-1,k) + B(n-2,k) + ... + B( n-k-1, k ), unde initializez primii k termeni cu primele k puteri ale lui 2.  Mie imi da corect pe exemple.Va rog sa-mi spuneti daca gresesc undeva . Multumesc.

[•stocarul]

E bună ideea ta.
Eu așa am luat 100 cu ridicare la putere în timp logaritmic.
Vezi, poate uiți de modulo

[•Badu]

Multumesc foarte mult Cosmin !  .

[•S7012MY]

cat trebuie sa dea pt n=3, k=2?
2

[•gabitzish1]

7

[•S7012MY]

k = 2 recurenta este B(n,2) = B(n-1,2) + B(n-2,2) + B(n-3,2)

pentru n=3,k=2 nu merge  

edit: nu am citit cuvantul maxim:)) acum stiu sa o fac

[•stocarul]

Păi, dacă n<=k avem 2ⁿ șiruri, deoarece practic nu avem nicio limitare.
Conform formulei spusă de tine =>
B(3,2)=B(2,2)+B(1,2)+B(0,2)
  =>B(3,2)=2² + 2¹ + 2⁰
    =>B(3,2)=4+2+1
      =>B(3,2)=7

[•stardust]

La problema asta am o solutie O(n) si iau 60 cu restul TLE. Sa inteleg ca se poate mai bine ? Am vazut ca a mai scris cineva o idee de rezolvare pe topic dar mi se pare ca tot O(n) este.