Problem Statement |
| | A closed box (modeled as a rectangle of cells, R rows x C columns) contains A randomly placed atoms.
Each atom has a type from 0 to T-1, inclusive.
You can't see the atoms, but you can figure out their positions by shooting rays of types 0..T-1 through the box
and checking where they exit the box.
The ray is shot from a center of a cell outside of the box adjacent to one of the borders of the box (i.e. row=-1, row=R, col=-1 or col=C) and its direction is perpendicular to this border.
A ray of type Tj moves inside of the box using the following rules:
-
the borders of the box don't influence the ray;
-
the ray moves parallel to the borders of the box;
-
atoms of types Ti < Tj don't influence the ray;
-
if the ray hits an atom of type Tj directly, it is absorbed and doesn't return from the box;
-
if the ray hits the atom of type Ti > Tj directly, it is reflected;
-
if the ray enters a cell which is diagonally adjacent to the atom of type Ti >= Tj and the ray is heading towards the atom, it is deflected: its direction changes by 90 degrees "away from the atom"; note that atoms which are diagonally adjacent to the cell but are behind the ray don't affect its movement;
-
if the ray is reflected or deflected before it enters the field, it is detected in the cell from which it was shoot;
-
the precedence of ray-atom interactions is as follows: absorbtion/reflection has higher priority than deflection, and if two atoms deflect the ray in the same cell, they affect it simultaneously, resulting in reflection.
The image above illustrates the rules for ray reflection.
The rays on the image move as follows (yellow, orange and brown
mark types 0, 1 and 2, respectively):
- ray 1 and doesn't interact with nearby atoms of types 0 and 1;
- ray 2 doesn't interact with the atom of type 0 and is deflected four
times by atoms of type 1;
- ray 3 is deflected twice by atoms of types 0 and 1 and finally is
absorbed by an atom of type 0;
- ray 4 is reflected by an atom of type 1;
- ray 5 is deflected by an atom near the border of the box, so it is
detected in its starting cell;
- ray 6 is absorbed by an atom near the border of the box.
Your code should implement a method scan. Its parameters give you number of rows and columns in the box R and C, the number of atoms in the box A and the number of atom types T. You can call a static library function ray(row, col, typ) in class RayScanner which shoots a ray of type typ from cell (row, col). This method returns "A" if the ray was absorbed and didn't return from the box, and otherwise returns the coordinates of the cell in which it was detected after leaving the box (formatted as "ROW COL"). You must eventually return your guess for the locations and types of the atoms in the box as a String[]. Your return must contain R elements, each having C characters, exactly A atoms, and only '.' and '0'..('0'+T-1) characters in it.
Your score for an individual test case will be calculated as follows: your return will be compared with the actual contents of the box cell by cell; for each cell which contains an atom of the correct type you will score 1, and for each cell which contains an atom of a different type you will score 0.5. The sum of scores over all cells is divided by A and multiplied by 2*(1-M/T/(R+C)), where M is the number of measurements you have done. Your overall score will be the sum of scores over all test cases.
A visualizer is available for offline testing. You can also play this game (with one type of atoms) here. |
| |
Definition |
| | | Class: | BlackBox | | Method: | scan | | Parameters: | int, int, int, int | | Returns: | String[] | | Method signature: | String[] scan(int R, int C, int A, int T) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The test cases are generated as follows: R, C and T are chosen randomly from their domains; atoms density is chosen randomly in [0.3,1] * sqrt(T) / min(R,C); for each cell of the board it stays empty with probability (1-density) and gets an atom of one of the types with probability density/T. If the described process produces a box without atoms, it is repeated with the same R, C, T and density. |
| - | The memory limit is 1024 MB and the time limit is 10 seconds (which includes only time spent in your code). There is no explicit code size limit. |
| - | There are 10 example test cases and 200 full submission test cases. |
| |
Constraints |
| - | R and C will be between 10 and 100, inclusive. |
| - | T will be between 1 and 10, inclusive. |
| - | You can do at most T*(R+C)/2 measurements. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
R = 10
C = 10
T = 3
A = 15
..........
....1.....
........2.
.0.....1.2
1.....1.0.
..........
...0....2.
0.........
..2.......
..1...2.1.
" | |
|
| 1) | |
| | | Returns:
"seed = 2
R = 23
C = 50
T = 2
A = 36
.....1...............................0..........1.
...........1...........1............1.............
.........................................1........
0.......1.........................................
..................................................
....1...........................0.................
................................1..1..............
..................................................
.................................1................
....1...............1......................0......
....................................1..........1..
.....1............................................
........0............0............................
................0.................................
..1.............0.................................
......0...........................................
..................................................
..................................................
1.................................................
............................0...0..0..............
........1....................0..1.................
................................0................1
...............1..................................
" | |
|
| 2) | |
| | | Returns:
"seed = 3
R = 99
C = 29
T = 3
A = 157
......1.................2....
...................2..0......
..............0....1.........
.........................0...
.............................
.........1........20........0
..................1..........
.........21.......00..1......
.............................
...........22................
..........1..................
..................0........2.
.....................2.......
.2.......1................0..
.............................
.............................
.............................
.1..............1............
.............2.....0..2......
.............................
......2.....................2
...12........0.............20
.............................
.................1...........
..1....2..........1..........
..2...........0..............
.........0.2.................
...........................1.
..1...0......................
.............................
.............................
...................1.....0...
........1.............1.....0
............................2
....2..................2.1...
...................2.........
0................0...........
.12.....2....................
.........1...................
..........1..................
.............................
.....1.......................
...........................0.
..................1..........
.......0.....................
..............2..0...........
................1............
..0.........0......0.........
1......0.....................
0......................0.....
.1........................0.0
..2...2....1.........1.......
...................1..1......
.......1....................1
............1..........2.....
.............................
............2................
......2......................
......0................1...1.
.............................
0............................
.2..0.....0..................
...0....1....................
..........2..................
....01.......................
.............................
...............2.............
........2........1.........0.
...0.........................
.............................
.............................
.....2......0..0.............
...1..2.....2..........1.2...
...........2...0.............
.........1...................
.............1....2..........
...00..........1.............
......1......................
........2..................0.
..........10.................
...............0.............
.........0.00................
..........1....1.............
.............11..............
....................1........
...2.........................
..0...............2..........
.0....................2......
.............................
0...............2............
.............................
0....2.................2.....
..........1..................
..........0..................
.............................
.............................
...............2.............
.0...........................
.........................1...
" | |
|
| 3) | |
| | | Returns:
"seed = 4
R = 52
C = 83
T = 10
A = 203
..........1.....................................................................0..
...............................................2...................................
......6........4.5..............8.....................6......................8..1..
.........................9....4.6....8.............................................
...........8...............7....................1..................................
................2.....................................3.........9..................
.........................0....................................7....................
...5............................9........................................1......1..
...3.....8..6...........................................8....................5.....
.............................7.....3.................0.........8...............5..4
...............................7.................4.................2........8......
....8.....................2........................6.............................7.
.............................................1......5....................6...4..1..
0.....................................5........................4...................
.............2....................8...........1.0.....0.....6......4...............
..............................................................................2....
...................................5...2..............5............................
.....0...........1.........................8...............6.4........3...........5
............6.............0.............................6.......1..................
....8........................................2...................7.....0......0....
................................................2..................................
..........6.......4..0...3............4......0.....1..................9............
.........7.............................5........7..........................7.......
..............................................................7..................6.
............................2......................................................
............7........3.................0............................4..............
.0..............0.........................................9.....................2..
......................8.....................................1...................2..
.4...8.............4................5......3.......3........................2......
........................................3.......................................4..
..............................................................................2....
6.3...2...............3..................5..............6..........................
8.....5....7......6........8......................................7................
........7.....................8.....41....7.......4........22.0........9..........4
...............................8.........................1.........................
...................................................................................
............................................246....................................
......................1..6.......9.....5..............8.9..........................
....0......0........................0........................................16....
......................8.....................................1.......8.6............
.........9......12.....9...........................................................
........................................8..3....8........9.......8.......9.....8...
5.................................1.....................7..3........2..............
.........4...........................2........................6.4..8.0.............
............................1....................................................8.
.....................................................................1.9.......7...
0.....6............................................................................
.................7............7...............6......4.....25......................
.........3.........9....8..........................................................
.............................4.............2.......................................
...........................4.............................................4.........
.......................................................5...........................
" | |
|
| 4) | |
| | | Returns:
"seed = 5
R = 83
C = 59
T = 2
A = 124
...........................................................
......................................................0....
.1....................1..............0.....................
...........................................................
.............................................0.............
.............1.....................................0.......
..................0........................................
....1.........1............................................
.........0.............................................1...
.............1.............................................
..1........................................................
.............0........1....................................
......................................0...........1....0...
...10...............1......................................
........................1..................................
...........................................................
....................................1......................
....................................1......................
...........................................................
.......1...........1.......................................
......................1.................................0..
.......................1...................1...............
....1......................................................
............................................1..............
...........................................................
..........1.....................0.....1....................
.....................1.....................................
..1...............................0........................
...........................................................
1........................1.....0.......................1...
..........0..............0..................1..............
.........................1.................................
.................1.............1................0..........
............................................1..............
.............1..............................0..............
..0........................................................
..................................................0........
...................................................0.......
...........................................................
...............................1........0..................
...0................0......................................
..................................1........................
.......0....................................0.1....0.......
...........................................................
......0.1..................................................
...........................................................
....................1..0...........1.....0.................
.............................1..0..........................
0......11.........................................1...1....
.............1...........1.....................1...........
.................................1........0.1........1.....
.....1.1...................................................
...0.......................................................
...........................................................
...........................................................
...................................0.......................
..1.............................................0..........
.......................................................0...
...........................................................
.....................0.....................................
..........1...............1................................
...........................0...............................
...............................1...........................
...........................................................
.......................1....................1..............
...................0.......................................
...........................................................
...............0................................0........0.
.........................................................0.
...........................................................
.......................0...................................
.....................................1.....................
....................0.................1....................
..............1.......1...............................0....
..........................................................1
..........................0.....0..........................
...........1..........................0....................
...........................................................
...........................................................
.............0....................1........................
.....1.............0....................................1..
...........................................................
....................0..............0..0....................
" | |
|
| 5) | |
| | | Returns:
"seed = 6
R = 34
C = 36
T = 3
A = 22
....................0...............
..2.................................
.....2..............................
.....0..............................
....................................
....................................
....................................
....................................
....................................
.........................0..........
....................................
....................................
......2................1...........2
....................................
....................................
........0............0..............
....0...............................
....................................
....................................
....................................
....................2...0...........
..................2...........1.....
....................................
....2..............1................
....................................
...............................2....
....................................
...........2...1....................
......2.............................
.....1..............................
....................................
....................................
....................................
....................................
" | |
|
| 6) | |
| | | Returns:
"seed = 7
R = 98
C = 54
T = 2
A = 78
......................................................
...................................................1..
......................................................
...............1......................................
.....................................................0
......................................................
..0.........1.........................................
.............................1........................
.........................1............................
......................................................
...............1......................................
......................................................
.......0.............................0.....1..........
......................................................
......................1...............................
......................................................
.....................0................................
......................................................
.................0....................................
......................................................
........................0.0...........................
......................................................
......................................................
.................................0....................
..1.........................................1.........
......................................................
......................................................
......................................................
.................0....................................
......................................................
....1...0.............................................
.........................0............................
......................................................
......................................................
......................................................
.........0............................................
......................................................
.............1.....................................0..
..................................................1.0.
......................................................
..............................0.......................
..........................1...........................
............................................1.........
.................1....................................
......................................................
................0.........................0........1..
......................................................
....0.................................................
......................................................
......................................................
................................0............1........
.....................................0................
......................................................
...............0......................................
......................................................
......................0...............................
.........0.1..........................................
......................................................
................................................0.....
.............1............0...........................
.................................0....................
....................1.................................
.....................................0................
......................................................
......................................................
......................................................
.............................................1........
......................................................
.......................1..............................
......0...............................................
......................................................
.......................................0..............
......................................................
......................................................
......................................................
............................................1.........
...........................................1.......0..
.............1........................................
......................................................
......................................................
.............1........................................
......................................................
..............1.......................................
....0.................................................
......................................................
......................................................
...............................................0......
....................0.................................
......................................................
..............................0....................1..
..1...................................................
.............1........................................
................................1..1..................
......................................................
..1.......1...........................................
..................................1...........1.......
.........................0.........1........0...0.....
..............1...0...................................
" | |
|
| 7) | |
| | | Returns:
"seed = 8
R = 49
C = 30
T = 8
A = 113
............................5.
......62......................
..............................
.............................4
.............0........2.......
..........5...7...3...........
........6...6........7........
......25........2.............
..............................
..............61...........5..
...........5.5................
..................3...1....66.
.....2......7.........5.......
............4........2........
...6..........................
............1.......6...4.....
4...................3...1.....
.....5.................2......
........1.....................
...............4.2............
......7....................4.7
........3.2....7..............
...1......3...................
.......15.....................
...7..........................
1........0........6...........
...............1.............0
..............................
................7...4.1......2
.....2....6...0.6..2.........3
..............................
......................4.......
..6...........................
6...........72................
4...0.1...............6.......
..............................
.....5............4....4......
..................0.....6.....
...5.....................117..
..............23.2........3...
......3.3......2..0...........
..................0...........
.....03...04..................
........2.........4.......4...
5.....0..........2............
.....25............3..........
.......7......................
.....7...........3............
...........5.....02...........
" | |
|
| 8) | |
| | | Returns:
"seed = 9
R = 55
C = 74
T = 2
A = 91
................................................1..............1..........
..............................0...................................0.......
1.........................................................................
..........................................................................
.0..0................................1.................1..................
.......1.............................................1....................
..........................................................................
..........................................................................
............1............0...........0...........................0........
...............1.......1.....................................0............
..............0...........................................................
..........................................................................
1..................................................1..................0...
............1.............................................................
...............................................1.........1................
..........................................................................
...1.............................................................0........
..................1...........................................0...........
..........................................................................
..............................1.................1..................1......
..........................................................................
........1.................................................................
...............................................................0..........
..............................................................1...........
.................1.1..............................1.....................1.
.....................................1........................0...........
....................................................0.....................
........0.....0...............................0..............1............
..............................0...................1...1...................
..........................................................................
..................................11....1...........................1.....
......0..............1....................................................
..........................................................................
..........................................................................
..........................................................................
..........0...............................................................
.......................................1..................................
.....................1....................................................
..........................................................................
...0......1.........................................1.....................
..........................................................................
.0......................0.........1.....................................1.
...............................................0........1.................
......................0...................................................
......0..............................................0....................
...........1.....0..........................1.............................
..........1..............................1................................
..........................................................................
........................1..............................................1..
..........................................................................
......1...........................................................1.....1.
...............11.1........................0...................1..........
..0...................................1..1................................
..........................................1...............................
........0..................................1..............................
" | |
|
| 9) | |
| | | Returns:
"seed = 10
R = 84
C = 41
T = 1
A = 78
.............................0...........
........................................0
.........................................
......................0..................
........0................................
.........................................
...................0.....................
...................................0.....
.....0...................................
0................0...................0...
.....................................0...
...................................0.....
.........................0...............
.........................................
.........................................
.........................................
.........................................
...................00....................
.......0.................................
0...............0........................
.........0...............................
.......0.................................
.........................................
.......................0.................
......0..................................
..0......................................
..............0..........................
.........................................
.......0.......0.........................
.........................................
.........................................
.................0.......................
...0.....................0...............
.........................................
.......0.................................
...0...............................0.....
..................0.......0..............
...........................0.............
.0.......................................
.........................................
0........................................
.........................0...............
.........0...............................
...........0.............................
........0.......................0........
.......................................0.
.........................................
.........................................
.........................................
.........................................
.........................................
..........................0..............
.........................................
.............................0...........
.........................................
.0...........0...........0....0..........
.0.......................................
.............................0...........
......................0...0..............
0.............................0.0........
.........................................
........................0................
....0...........0......0..0........0.....
.........................................
..................................0......
........................................0
..................0................0.....
...........0............................0
.........................................
.0..............................0........
.........0...............................
.........................................
.........................................
.........................................
...........................0.............
............0............................
.........................................
..........0..0...........................
..........0..............................
.........................................
..0..........................0...........
.........................................
.........................................
.........................................
" | |
|