CinemaProblem | Topcoder Archive

Problem Statement

The participants of a famous programming contest have gone to the cinema. The cinema hall contains several rows, each containing exactly seatsPerRow seats. The movie is very popular, so the contestants' assigned seats are scattered all over the cinema hall, and there are no vacant seats. Because the contest participants are very sociable with each other, they want to sit together according to the following rule. They must sit in such a way that every row containing a participant contains only participants. If the total number of participants is not evenly divisible by seatsPerRow, there can be one row that is not completely filled with participants.

You are given a int[] participantsInRow. The i-th element of participantsInRow is the number of contest participants sitting in the i-th row. Return the minimal number of swaps needed to satisfy the rule. Every person in the cinema hall is willing to swap seats with anybody else.

Definition

Class:: CinemaProblem
Method:: minSwaps
Parameters:: int, int[]
Returns:: int
Method signature:: int minSwaps(int seatsPerRow, int[] participantsInRow)
(be sure your method is public)

Constraints

seatsPerRow will be between 1 and 100, inclusive.
participantsInRow will contain between 1 and 50 elements, inclusive.
Each element of participantsInRow will be between 0 and seatsPerRow, inclusive.
participantsInRow will contain at least one positive element.

Examples

```
100
```
```
{50, 100, 0, 100, 50}
```
```
Returns: 50
```
One way to get an optimal answer is to swap 50 contestants from the 0-th row and 50 non-contestants from the last row.
```
1
```
```
{1, 1, 0, 0, 0, 1}
```
```
Returns: 0
```
The rule is already satisfied.
```
30
```
```
{25, 25, 25, 0, 30}
```
```
Returns: 10
```
```
100
```
```
{73}
```
```
Returns: 0
```

{50, 50, 50, 50, 50, 50, 50, 50}

Returns: 200

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)2024, Topcoder, Inc. All rights reserved.