SP4456 AIRLINES - Jumbo Airlines

The new catchphrase of Jumbo Airlines is "No annoying neighbors, each flight a unique experience!" And as in most cases, the advertisement was produced by the marketing department, without ever consulting the engineers. They only learned about it after the boss asked them to "handle it ASAP". There are M seats in each row, and there are N rows of seats in the airplane. Hence the seats form an M \* N grid. (For the purpose of this problem we will ignore the presence of aisles.) The airline sells exactly K tickets for each flight. To make sure that the "no annoying neighbors" part of the motto is satisfied, the seating must obey the following rule: Whenever a seat is occupied, the seats immediately in front of it and behind it, as well as the seats immediately to the left and to the right must remain free. An allowed arrangement is a set of K occupied seats that obeys the rule above. The "unique experience" part of the motto is then satisfied by using a different arrangement of occupied seats for each flight. (Two seating arrangements are different if there is at least one seat which is occupied in one arrangement and free in the other.)

N/A

N/A