The Number of N-k-special Sets
Time limit1sMemory limit128 MB
Count subsets of {1,...,n} with no two consecutive numbers whose sum exceeds k, for n up to 100.
- Level
Medium5 of 10
- Topics
- Dynamic programming, Combinatorics
- Solved
- No attempts yet
Problem
A set of natural numbers is called --special when all of the following hold:
- every element satisfies ,
- the sum of all elements of is strictly greater than ,
- contains no pair of consecutive natural numbers, that is, no two elements differ by exactly .
Given two natural numbers and , write a program that computes the number of --special sets.
Input
The first line contains two natural numbers and separated by a single space, with and .
Output
Print one non-negative integer: the number of --special sets for the given and .