Press to Unlock
Time limit1sMemory limit128 MB
Count the number of ordered sequences of disjoint nonempty subsets (a set partition of any subset of buttons into an ordered sequence of blocks) for given B up to 11.
- Level
Medium6 of 10
- Topics
- Combinatorics, Math, Dynamic programming
- Solved
- No attempts yet
Problem
A door lock has B buttons numbered from 1 through B, where 1 <= B <= 11. A password is entered by pressing one or more button combinations in a fixed order, then turning the handle.
A button combination is a nonempty set of buttons pressed at the same time. If a button is used in one combination, it cannot be used again in another combination of the same password. Some buttons may be left unused.
When B=8, (1-2-3)(4)(7-8) is a valid password made of the three combinations (1-2-3), (4), and (7-8) in that order. Buttons 5 and 6 are unused. In contrast, (1-2-3)(2-4)(5-6) is invalid because button 2 appears in two combinations.
Given the button count B for several door locks, compute how many distinct passwords can be made for each one.
Input
The first line contains an integer N, the number of door locks. 1 <= N <= 100.
Each of the next N lines contains one integer B, the number of buttons on a door lock.
Output
For each door lock, output the number of possible passwords on its own line, in input order.