Seat Arrangement
Time limit2sMemory limit128 MB
Count the ways to seat N-1 ticket holders into N seats, given one free seat, so that each person sits in their own, adjacent, or the free seat.
- Level
Medium6 of 10
- Topics
- Dynamic programming, Combinatorics, Math
- Solved
- No attempts yet
Problem
A theater has N seats arranged in a single row, numbered from 1 to N from left to right. Among these N seats, N-1 are sold as assigned seats, and the remaining one seat is designated as a free seat. A person with an assigned-seat ticket may sit according to the following rules.
- They may sit in the seat whose number is written on their ticket.
- They may sit in the seat immediately to the left or right of that seat.
- They may sit in the free seat.
For illustration, suppose a theater has 4 seats, seats 1, 2, and 4 are sold as assigned seats, and seat 3 is the free seat. In the figure below, the gray seat is the free seat.
Figure 1
In the figure below, the number i represents the person holding the assigned-seat ticket for seat i. The arrangements in Figure 2(a), (b), (c), and (d) satisfy the rules above.
Figure 2
The following four arrangements do not satisfy the rules.
Figure 3
Figure 3(a) is invalid because the person holding the assigned-seat ticket for seat 4 is not seated. In Figure 3(b), (c), and (d), the person holding the ticket for seat 1 or seat 4 sits at least two seats away from their assigned seat, so those arrangements are invalid.
Given the total number of seats N and the free seat number K, compute the number of seat arrangements that satisfy the rules above.
Input
The first line contains the number of seats N. (3 ≤ N ≤ 40)
The second line contains the free seat number K. (1 ≤ K ≤ N)
Output
Print the number of seat arrangements that satisfy the rules on the first line. This value is an integer not greater than 2^31 - 1.