ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1260. Nudnik Photographer

Pages: Previous 1 2
<font color="#BA0018">Another idea</font>
Posted by sylap 2 May 2013 19:14
My idea is : (a bit complicated)

definition :

dp[x][0][0] = [...] , x   , x-1 , [...]
dp[x][0][0] = [...] , x-1 , x-1 , [...]
dp[x][1][0] = [...] , x   , x-1
dp[x][1][0] = [...] , x-1 , x
dp[x][1][0] = [...] , x-2 , x
(dp[x][i][j] is number of sequences satisfying the corresponding rule)

recurrence :

dp[i][0][0] = dp[i-1][0][1];
dp[i][0][1] = dp[i-1][0][0] + dp[i-1][1][0];
dp[i][1][0] = dp[i-1][1][1];
dp[i][1][1] = dp[i-1][1][1] + dp[i-1][1][2];
dp[i][1][2] = dp[i-1][1][0];

answer (to be printed is) :

dp[n][0][0] + dp[n][0][1] + dp[n][1][0] + dp[n][1][1] + dp[n][1][2]

proof :

left for you :)

Edited by author 02.05.2013 19:18
Re: <font color="#BA0018">Another idea</font>
Posted by neko13 12 Aug 2013 17:24
I have observed the answers.I found that a[i]=a[i-1]+a[i-2]-a[i-5];
I still don't know why!
Re: <font color="#BA0018">Another idea</font>
Posted by mjolner 13 Aug 2013 21:37
Above has been shown:
a[i] = a[i-1] + a[i-3] + 1

this holds for each i, then also:
a[i-2] = a[i-3] + a[i-5] + 1

So
a[i-2] - a[i-3] - a[i-5] = 1

and (substitute this result in the first equation)
a[i] = a[i-1] + a[i-3] + a[i-2] - a[i-3] - a[i-5]

which reduces to
a[i] = a[i-1] + a[i-2] - a[i-5]
Re: How to slove it?? Any hints?
Posted by Pegasus 1 Sep 2013 16:32
I use dfs to find the regular for some test
n  =   1 2 3 4 5 6 7   8    9    10   11
ans=   1 2 2 4 6 9 14  21   31   46   68
then I found f[n] = f[n-1] + f[n-2] - f[n-5]
then I got AC.
Re: How to slove it?? Any hints?
Posted by webeseit 12 Nov 2018 11:39
cool, note that we can unite 3rd and 4th cases as one case when n >= 4.
Pages: Previous 1 2