Need help for this question #271 Div 2 D

codeforces

#1

How to solve this problem ? I cant even understand the sample input.


#2

Can someone help me please ?


#3

This is a DP problem. Since a and b can be atmost 10^5 and k is fixed you can precompute all values upto 10^5 . For i< k dp* is 1 and for i>=k you can add a R or W at the end. If you add R the previous value can be R or W.If you add a zero the previous k-1 must be zero for valid configuration. So

dp*=dp[i-1]+dp[k-1].


#4

Read the editorial here :
http://codeforces.com/blog/entry/14136