N-K Special

We define "n-k special" set X of positive integer numbers as follows:
  • each element x that belongs to set X must meet the restriction 1 ≤ x ≤ n
  • the sum of elements of the set X must be larger than k
  • no pair of elements belonging to the set can be consecutive numbers
Write a program that reads n and k (1 ≤ n ≤ 100; 0 ≤ k ≤ 400) as its input and outputs the total number of "n-k special" sets.


5 6




1. {1, 3, 5}
2. {2, 5}
3. {3, 5}
meet the given criteria. No other sets exist.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 13, 2009

Languages Allowed:
C++03, PAS, C, ASM, C#, C++11

Comments (Search)

is there anyway to make floating points more accurate?

No. That's why the last case is worth 10 points :P
You can either a) use string math or b) use 3 longints to store the number. (You might want to try aplusb2 first)

It's worth 2 points partial now

I'm guessing numbers must be unique as well?

A member of the universe of discourse either belongs to the set or does not belong to it; a set contains no duplicates, not unlike the STL container.

This was a quiz (on dynamic programming) last year - I guess there's no time for that, so I posted it here instead.