# UVa 10328

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