| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14071 | Attack on Quadtrees |
|
| 14072 | We count to 24 |
|
| 14074 | Report on Quadtrees |
|
Description
While scouting outside the wall, the Survey Corps spotted a wide open field filled with a lot of titans. In order to maneuver around the titans, commander Hange recommends using a quadtree structure to scan the area. When viewing the field, it can be divided into a matrix where each block represents whether an area has any titans. Each block can either contain a 0 or a 1. If the given number is 0, then there are no titans in the block. If the given number is 1, then there are titans in the block. An example can be given below:
To use the quadtree structure, we must first divide the initial area to 4 separate quadrants (upper left, upper right, lower left, lower right). In the example, the upper left quadrant is completely homogenous (all areas inside have the value of 0 or 1) while the other quadrants are not; therefore the upper left quadrant can be ignored while the others must be divided further. Non-homogenous quadrants will then be divided further until it each area in the quadrant is homogenous.
Alongside this structure, Hange also applied a specific naming procedure for each homogenous area:
- The first digit of an area's ID will be the homogenous value within the quadrant.
- Every following digit represents the location of the current block corresponding to the previous ones. (e.g. if the current block is the upper left quadrant of the previous block then the next digit will be 0.)
Following these rules the result of the given example would look as follows:
One more thing to note is that because of the nature of the quadtree, the length and width of the area must be equal and have the value of 2P. If is does not follow this condition, the area must be padded with 0's so it fits the dimensions accordingly. (e.g. 3 * 5 area must be rounded to a 8 * 8 area).
Create a code to perform Hange's quadtree structure with the aforementioned conditions to find the areas that contains titans.
P.S.
Input
The first line contains the integer R and C (1 <= R,C <= 128).
The following R lines contain C values of the matrix to be processed.
Output
The first line contains the number (N) of homogenous areas with the value of 1.
The following N lines contain the ID of each area with the homogenous value of 1.
Don't forget to put a newline character at the end.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a programmer and you are doing a programming test but this time there is a mistake counter. For every mistake you, the online judge will give a value for your mistake. Once 4 mistakes are made, the value of the 4 mistakes are computed to see if you are disqualified.
How the computer decides if you are disqualified is by checking if the 4 numbers can be put into an equation where the resulting value is 24. The computer can use any basic operators ( '+', '-', '*', '/', '()') in any order. Every operation is a binary operation which means that they have to be done between two numbers (converting a 1 to a -1 is not allowed). Concatentation of two numbers is also not allowed.
For example:
values: 4, 1, 8, 7
equation: (8 - 4) * (7 - 1) = 24
values: 1, 2, 3, 2
equation: no equation can result in 24
Write a program that could do the same as the computer in the Online Judge!
* abs() function does not work on float values *
Input
The first line contains the number of sets of values (1 <= q <= 100).
The following q lines containing 4 positive integers (1 <= a, b, c, d <= 1000).
Output
"Safe" if the numbers can result in 24. "Disqualified" if not. Both followed with a newline.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After gathering a lot of data, the Survey Corps returned to discuss their strategy. However, because they use the quadtree structure, all their data comes in the form of numbers; therefore they have to reverse their quadtree algorithm in order to retrieve the battlefield data they had just collected.
* It is recommended to finish the "Attack on Quadtree" question beore attempting this one **
As a referesher, to use the quadtree structure, we must first divide the initial area to 4 separate quadrants (upper left, upper right, lower left, lower right). In the example, the upper left quadrant is completely homogenous (all areas inside have the value of 0 or 1) while the other quadrants are not; therefore the upper left quadrant can be ignored while the others must be divided further. Non-homogenous quadrants will then be divided further until it each area in the quadrant is homogenous.
In this scenario the reconstruction of the original data would look like this:
The collected data comes in forms of an ID for each area that are homogenous (all areas inside have a value of 0 or 1). They also recorded the original dimension of the area. The ID is recorded as follows:
- The first digit of the ID will be the homogenous value within the quadrant.
- Every following digit represents the location of the current block corresponding to the previous ones. (e.g. if the current block is the upper left quadrant of the previous block then the next digit will be 0.)
Help the team reconstruct the original data with the data they have right now.
* The array size will not exceed 128 * 128 *
** Remember that the dimension of the area must be in the form of 2P*2P for the quadtree structure to work **
Input
The first line contains the number (N) of homogenous areas with the value 1.
The following N lines contain the ID of each area with the homogenous value of 1.
The final line contains the number of number of row and columns in the data.
Output
R lines containing C values of the matrix.
Don't forget to put a newline at the end.
* The last digit of every line must not have a space *
** the last row must not have a new line "