UVa 10328 - Coin Toss
How many distinct sequences of coin tosses of length n there are so that it contains at least k consecutive heads?
It might not be easy to directly answer the question. But it is easy to answer how many sequences there are with no k consecutive heads. To do that, one can simply run a DP solution, with the states (toss, consecutive heads until now).
dp(i, c) = 1 if i == n, = dp(i+1, 0) if c + 1 < k, = dp(i+1, 0) + dp(i+1, c+1) otherwise.
The answer to the problem is the total number of sequences (2^n) subtracted dp(0, 0).
The answer does not fit in a 64bit integer. It's a good idea to use Java's BigInteger class.
A small optimization is to preprocess all powers of two less than 101.
4 1 4 2 4 3 4 4 6 2
15 8 3 1 4