We have to create a binary sequence from left to right .
Each $'0'$ gives 1 point to person-'B' and each $'1'$ gives 1 point to person 'A'.
Length of the sequence will be $n$
We are also given an integer $k$ such that $n>=k>=1$
(Maximum possible value of 'n' in this problem:-1000)
The binary sequence should satisfy the following condition :-
1)At each point(index) of the binary sequence(we start from the leftmost index) the total score of person 'A' should be greater than or equal to $k$ times the score of person 'B' .
Example :- n=4 and k=2 .
Possible sequences :-
(1)1111
(2)1110
(3)1101 (At the third step of sequence (3) , score of 'A'=2, and score of 'B'=1 ,as 2>= k*(score of 'B') , 3rd index is valid, similarly we check for all the indices , and the sequence is valid only if all the indices are satisfied from left to right)
Given any n and k , how to find the number of possible binary sequences ?
I am trying to find an efficient algorithm which can solve the problem in $O(N)$ or a closed-form(formula) for this question.
Quadratic DP will also be fine for me.
What have I figured out :-
1)Whenever, $k=1$ , this formula works for any 'n' :- https://oeis.org/search?q=1+2+3+6+10+20+35&sort=&language=english&go=Search
2)Whenever $k=2$, this formula always works for any 'n' : - https://oeis.org/search?q=1+2+3+4+8+13+19+38+64+98+196&sort=&language=english&go=Search
How to figure out the common formula for other(any) values of $k$ ?