Need help for this question #271 Div 2 D

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

Can someone help me please ?

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[i] 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[i]=dp[i-1]+dp[k-1].

2 Likes

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