Warning, the subtasks are not in order of difficulty.
Rar wants to impress Jacq the Dinosaur and wants to show her how good he is with kids. As such he has invited an entire kindergarten to his wedding. Rar also wants to impress Jacq with his computing skills. So, he wants to make his kindergarteners compute things.
Rar will arrange the kindergarteners in an N × M grid. Each cell of the grid will either contain a wall, or a kindergartener. Each kindergartener can choose to raise up an object, or not raise up anything. This is represented by a number that ranges from 0 to 3. The meaning of those numbers are:
Flags will only be used in subtask 5. Do not use it in any other subtask.
Rar will first instruct each kindergartener to raise up a specific object (or nothing), based on the problem he wishes to solve (this will be further elaborated below). In other words, Rar will set the initial configuration of the grid.
Every second, the kindergartener will look around themselves, observe their surroundings and what their fellow friends are holding up, after which Rar will blow a whistle, and every kindergartener will simultaneously raise an object (or show nothing) based on their observations. Their objective is to transform the grid to the answer of the specific case.
Each kindergartener can only see the X × Y grid surrounding them (X and Y are odd numbers) as they are very short. Any cells not in the grid is assumed to be a wall, and will contain the value "2".
For example, in this grid:
1 1 1 0
There are 4 kindergarteners, and if X = Y = 3, these are their views:
2 2 2 2 2 2 2 1 1 1 1 2 2 1 0 1 0 2 2 1 1 1 1 2 2 1 0 1 0 2 2 2 2 2 2 2
In this grid:
1 0 1
There are 3 kindergarteners, and if X = 3, Y = 5, these are their views:
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 1 2 1 0 1 2 1 0 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
Help them complete their task by coding the functions subtask1, subtask2, subtask3, subtask4 and subtask5 for the respective subtasks. The function will be of the form:
int subtaskX(std::vector< std::vector<int> > grid){
return 0;
}
The variable grid will be the X × Y grid visible by the kindergarteners. grid[0][0] will be the top left cell, and grid[X-1][0] will be the bottom left cell. The value returned will be what that kindergartener will raise up. Do not return a value not in the range of 0-3, such an object does not exist. Also, kindergarteners cannot raise up walls (that would be mildly terrifying). Please make sure that this function will return the same value if the function is called multiple times with the same input, otherwise it might give you a "Wrong Answer". Basically, 2 kindergarteners who see the same thing should raise up the same object.
Once the grid is stable (the grid no longer changes after an iteration), the program will terminate and you will be given full credit if the final grid is identical to the answer. The max number of iterations the kindergarteners are allowed to run for is 500 for all subtasks, otherwise the kindergarteners die of exhaustion, and Rar will be deemed to be bad with kids.
For all subtasks, 1 ≤ N, M ≤ 30
There are M numbers, A0, A1, ..., AM-1. The grid in the initial configuration will be a histogram. More specifically, each column will represent a number Ai, and will contain Ai down-justified objects. Sort the columns in descending order.
Before: A = [3, 4, 1, 0, 2]
0 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1
After: A = [4, 3, 2, 1, 0]
1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 0
There are M numbers, A0, A1, ..., AM-1. The grid in the initial configuration will be a histogram. More specifically, each column will represent a number Ai, and will contain Ai down-justified objects. In the result, leftmost column should contain the sum of all Ai, and every other column should contain only blanks. It is guaranteed that the number of objects that can fit in one column is strictly greater than the sum of all Ai.
Before: A = [1, 0, 0, 0, 2]
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1
After: A = [3, 0, 0, 0, 0]
0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0
There are 2 numbers, A0 and A1. Each column will represent a number Ai, and will contain objects that will represent Ai in binary, with the most significant bit at the top. In the result, leftmost column should contain A0 - A1, and the rightmost column should contain only blanks.
Before: A = [10, 7]
1 0 0 1 1 1 0 1
After: A = [3, 0]
0 0 0 0 1 0 1 0
Now, the kindergarteners' eyesights are upgraded to a 3 × 5 grid.
There are M numbers, A0, A1, ..., AM-1. Each column will represent a number Ai, and will contain objects that will represent Ai in binary, with the most significant bit at the top. In the result, leftmost column should contain the sum of all Ai, and every other column should contain only blanks. It is guaranteed that the maximum value one column can represent is strictly greater than or equal to the sum of all Ai.
Before: A = [3, 0, 2, 9]
0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1
After: A = [14, 0, 0, 0]
1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
The kindergarteners' eyesights are again downgraded to a 3 × 3 grid :(
Rar has created a maze for the kindergarteners. The maze has a property that there is exactly one possible way to reach any blank cell from any other blank cell moving only horizontally or vertically (note that people cannot pass through walls!). This is such a possible grid:
0 2 0 0 0 0 0 2 2 2 0 2
Rar then takes this grid, and adds two flags (labeled 3) on two different blank cells. Rar will be standing at one of the flags, and Jacq at the other. They have to find each other through the maze. To ensure that they do not get lost, the kindergarteners are tasked to raise an apple on the cells that they should not walk over, because an apple a day keeps the programmers away.
Before:
3 2 3 0 0 0 0 2 2 2 0 2
After:
3 2 3 1 0 0 0 2 2 2 1 2
Download the files under attachments. Compile the code with the command:
g++ grader.cpp rarkids.cpp -o rarkids
The first line of the input will contain the subtask number.
The second line will contain N and M separated by a space.
The next N lines will contain M numbers, the type of the cell. This will be the initial grid given to the kindergarteners.
The next N lines will contain M numbers, the type of the cell. This is the final grid the kindergarteners should make.
| Subtask | Score |
|---|---|
| 1 | 10 |
| 2 | 15 |
| 3 | 15 |
| 4 | 40 |
| 5 | 20 |
| 6 | 0 |