PrisonCells

SRM 273 · 2005-11-21 · by supernova

SRM 273 · 2005-11-21 · by supernova · Search, Simple Math

Show categories

Class Name: PrisonCells

Return Type: int

Method Name: scatter

Arg Types: (int, int, int)

Problem Statement

You are the most popular programmer in town and the mayor needs your help. This time he wishes to reorganize the town's detention system. All the inmates are held in an underground rectangular-shaped prison, with cells situated on m rows and n columns. When opened, the cells communicate with each other vertically and horizontally. Thus, the distance between two cells is defined as the Manhattan distance:

(absolute value of difference in x-coordinates) + (absolute value of difference in y-coordinates)
The mayor's plan is to reduce the conflicts by placing the prisoners as far from each other as possible. There are nr prisoners to place and each cell can hold at most one prisoner. The goal is to put the prisoners in cells such that the minimum of all the distances between two occupied cells is as high as possible.
Given an int m, an int n and an int nr representing the number of rows, the number of columns and the number of prisoners, respectively, return an int denoting the highest possible minimum distance between two occupied cells.

Constraints

m is between 1 and 4, inclusive.
n is between 1 and 4, inclusive.
nr is between 2 and n*m, inclusive.

Examples

3
4
2
Returns: 5

The best way is to put the two prisoners in two opposing corners, like in the diagram below: * - - - - - - - - - - *

4
4
3
Returns: 4

In this case there are 3 distances to consider: between prisoner 1 and prisoner 2, between prisoner 1 and prisoner 3 and between prisoner 2 and prisoner 3. A possible solution, with none of the three distances less than 4, is given below: * - - - - - - * - - - - - * - -

4
4
4
Returns: 3

Everyone in the corner: * - - * - - - - - - - - * - - * Out of the 6 possible distances, 2 have a length of 6 and 4 have a length of 3. So, the answer should be 3.

4
4
16
Returns: 1

Every cell is occupied, so the smallest distance between two prisoners is clearly 1.

1
2
2
Returns: 1

Submissions are judged against all 99 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PrisonCells with a public method int scatter(int m, int n, int nr) · 99 test cases · 2 s / 256 MB per case