ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1763. Expert Flea

Sheer bliss!
Posted by Yermak 3 Feb 2011 05:33
I did it! I figured out this formula!
Re: Sheer bliss!
Posted by xurshid_n 8 Jun 2012 19:53
give any hint: F[n] = summa(a[i] * F[n-i], i=1..k) are right? (here a[i], and k - are consts).
k=?
a[]- easy generate, iff k - know.
Re: Sheer bliss!
Posted by bsu.mmf.team 4 Dec 2012 16:51
Yes, you are right. k = 19.
Good luck! :-D
Re: Sheer bliss!
Posted by Shen Yang 24 Oct 2017 05:37
(n-19>=7)  start from 7...
Re: Sheer bliss!
Posted by xurshid_n 31 Dec 2019 16:31
Hint: solve system equation with Gauss method (19x19).

Edited by author 31.12.2019 16:33

static constexpr int results[] =
{ // 0  1  2  3  4  5
0, 0, 0, 0, 0, 0,
/*Answer for n = 6 is*/  12,
/*Answer for n = 7 is*/  46,
/*Answer for n = 8 is*/  144,
/*Answer for n = 9 is*/  110,
/*Answer for n = 10 is*/ 312,
/*Answer for n = 11 is*/ 290,
/*Answer for n = 12 is*/ 670,
/*Answer for n = 13 is*/ 706,
/*Answer for n = 14 is*/ 1538,
/*Answer for n = 15 is*/ 1732,
/*Answer for n = 16 is*/ 3504,
/*Answer for n = 17 is*/ 4288,
/*Answer for n = 18 is*/ 8098,
/*Answer for n = 19 is*/ 10568,
/*Answer for n = 20 is*/ 19044,
/*Answer for n = 21 is*/ 26042,
/*Answer for n = 22 is*/ 45222,
/*Answer for n = 23 is*/ 64220,
/*Answer for n = 24 is*/ 108382,
/*Answer for n = 25 is*/ 158324,
/*Answer for n = 26 is*/ 261754,
/*Answer for n = 27 is*/ 390314,
/*Answer for n = 28 is*/ 635666,
/*Answer for n = 29 is*/ 962282,
/*Answer for n = 30 is*/ 1550244,
/*Answer for n = 31 is*/ 2372372,
/*Answer for n = 32 is*/ 3792560,
/*Answer for n = 33 is*/ 5848746,
/*Answer for n = 34 is*/ 9299148,
/*Answer for n = 35 is*/ 14419296,
/*Answer for n = 36 is*/ 22838014,
/*Answer for n = 37 is*/ 35548790,
/*Answer for n = 38 is*/ 56153296,
/*Answer for n = 39 is*/ 87640646,
/*Answer for n = 40 is*/ 138180196,
/*Answer for n = 41 is*/ 216065986,
/*Answer for n = 42 is*/ 340223834,
/*Answer for n = 43 is*/ 532680994,
/*Answer for n = 44 is*/ 838025410,
/*Answer for n = 45 is*/ 1313251780,
/*Answer for n = 46 is*/
};

Edited by author 31.12.2019 16:33
Re: Sheer bliss!
Posted by Gilles Deleuze 31 Dec 2019 18:39
Thanks for the sequence! The problem is indeed solved with linear recurrence (your message from 2012). Although, it seems k=20 here, and one needs to run Gauss on 20x20 matrix. I got by solution by using Berlekamp—Massey though.

I wonder, how could you guess there is a linear recurrence and that K is small enough to brute force the sequence in finite time (I assume that's how you got it).

Edited by author 31.12.2019 18:41