TopCoder problem "PrisonCells" used in SRM 273 (Division II Level Three)



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.
 

Definition

    
Class:PrisonCells
Method:scatter
Parameters:int, int, int
Returns:int
Method signature:int scatter(int m, int n, int nr)
(be sure your method is public)
    
 

Constraints

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

Examples

0)
    
3
4
2
Returns: 5
The best way is to put the two prisoners in two opposing corners, like in the diagram below: 
* - - -
- - - -
- - - *
1)
    
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: 
* - - -
- - - *
- - - -
- * - -
2)
    
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.
3)
    
4
4
16
Returns: 1
Every cell is occupied, so the smallest distance between two prisoners is clearly 1.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4526

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8070&pm=4526

Writer:

supernova

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Search, Simple Math