Dec05 TopCoder Problem Statement: Round Table (Level 1, Intermediate)

Problem Statement: Round Table

There are countA representatives of a company A and countB representatives of a company B that are having a meeting at a round table. There are chairs chairs around the table and they want to sit down in such a way that no representative of company A is sitting closer than minDistance to a representative of company B (minDistance=1 means any seating is allowed, minDistance=2 means there must be at least one empty chair between representatives of different companies, etc.).

Return the number of ways that such a seating arrangement is possible. Two seating arrangements are different if at least one person is sitting in different chairs in the two arrangements (i.e., include in the count all possible rotations of each seating arrangement). Note also that two different representatives of the same company are to be treated as different persons, see example 5.

Definition

Class:	RoundTable
Method:	arrangements
Parameters:	int, int, int, int
Returns:	long
Method signature:	long arrangements(int countA, int countB, int chairs, int minDistance)
(be sure your method is public)

Notes

- The return value will fit in a 64 bit signed int.

- The input values are not guaranteed to allow a valid seating arrangement; if there is no seating arrangement that satisfies the input, return 0.

Constraints

- countA and countB will each be between 1 and 5, inclusive.

- chairs will be between 1 and 50, inclusive.

- minDistance will be between 1 and 50, inclusive.

Examples

Returns: 90

Each company sends one representative. The first one can sit in any of the 10 chairs, the second one in any of the remaining 9 chairs (since minDistance=1 he may sit arbitrarily close to the other one). So there are a total of 10 * 9 = 90 arrangements.

Returns: 70

The same as example 0, but now the second one can not sit next to the first one, so only 7 chairs remain that he can choose from. This gives a total of 10 * 7 = 70 arrangements.

Returns: 14

Company A sends one representative, who sits down in one of the 7 possible chairs. Since minDistance=3, two chairs next to him at each side must remain empty. This leaves only 2 chairs that the 2 representatives from company B have to share (2 possible combinations for which one takes which of the two chairs). This gives a total of 7 * 2 = 14 arrangements.

Returns: 0

There are not enough chairs (5 + 3 = 8 representatives in total, but only 7 chairs).

Returns: 0

Now there would be enough chairs, but since minDistance=3, we have to keep 2 chairs empty between the groups at each side, thus requiring at least 5 + 3 + 2 + 2 = 12 chairs.

Returns: 6

Note that the two representatives of company A are treated as different persons, so there are a total of 3! = 6 possibilities to assign the three representatives to the three available chairs.

Returns: 180000

Back to TopCoder Challenge Page

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2005, TopCoder, Inc. All rights reserved.