UVa 10328

From Algorithmist
Jump to navigation Jump to search

UVa 10328 - Coin Toss[edit]

https://uva.onlinejudge.org/external/103/p10328.pdf

Summary[edit]

How many distinct sequences of coin tosses of length n there are so that it contains at least k consecutive heads?

Explanation[edit]

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).

Notes[edit]

The answer does not fit in a 64bit integer. It's a good idea to use Java's BigInteger class.

Optimizations[edit]

A small optimization is to preprocess all powers of two less than 101.

Input[edit]

4 1
4 2
4 3
4 4
6 2

Output[edit]

15
8
3
1
4