Problem Statement
There is a classroom with seats arranged into a rectangle. There are R rows of seats. Each row consists of C seats.
An exam is going to take place in the classroom. There are R*C students waiting to take the exam: one in each seat.
The teacher has prepared N different versions of the exam. The versions are labeled using the first N uppercase English letters: 'A', 'B', 'C', ...
In order to prevent cheating, no two students who are adjacent (either horizontally or diagonally) should have the same version of the exam.
You are given R, C and N. Determine whether it is possible to distribute the exam versions to the students in such a way that cheating is prevented.
If yes, return a String[] with any one valid arrangement. (R elements, each containing C characters. In element r, character c should be the exam version for the student sitting in row r, column c.) If no, return an empty String[].
Definition
- Class:
- ExamVersions
- Method:
- distribute
- Parameters:
- int, int, int
- Returns:
- String[]
- Method signature:
- String[] distribute(int R, int C, int N)
- (be sure your method is public)
Notes
- Formally, a student in row r1, column c1 and another student in row r2, column c2 are adjacent if and only if both abs(r1-r2) <= 1 and abs(c1-c2) <= 1.
- You can use arbitrarily many copies of each exam version, including zero.
Constraints
- R will be between 1 and 50, inclusive.
- C will be between 1 and 50, inclusive.
- N will be between 1 and 26, inclusive.
Examples
1
8
25
Returns: {"TOPCODER" }You are not required to use all available exam versions. There are many other valid solutions.3
5
7
Returns: {"CAGEB", "FDCFG", "EBAED" }The classroom corresponding to the return value looks as follows: CAGEB FDCFG EBAED We can easily verify that only letters 'A'-'G' are used and no two equal letters are horizontally or diagonally adjacent.5
1
3
Returns: {"B", "A", "C", "B", "C" }7
4
2
Returns: { }Two exam versions are not enough to prevent cheating in this classroom.