ExamVersions
SRM 852 · 2024-01-23 · by misof
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
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.
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.
7
4
3
Returns: { }
Submissions are judged against all 21 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ExamVersions with a public method vector<string> distribute(int R, int C, int N) · 21 test cases · 2 s / 256 MB per case