| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 14072 | We count to 24 |
|
| 14107 | Attack on Quadtrees Final Season |
|
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
The Alpha Squad is preparing for the final battle and sends out a group to scout for the enemy titans; however, when the scouts arrive, they realized that there are too many titans to keep track of and Hange's quadtree mechanism does not work with so many titans. Luckily, Sergeant Jing Yao is there to help them with this issue. He suggested that instead of splitting it into 4 quadrants, they should split it into 9 sections so that it will be easier to manage.
Similar to the original quadtree, they first transform the battlefield to a matrix and label each block of the matrix as 1 or 0 (1 if there are titans and 0 if there are no titans). Then, they must count how many homogenous areas are there.
To use this variation of the quadtree, they must first check the entire matrix to see if it is homogenous. If the entire matrix is not homogenous, then the matrix is divided into 9 sections. Then they repeat the process by checking each of the 9 sections of the matrix. The group must count how many homogenous areas there are in the matrix that are filled with titans.
One more thing to note is that because of the nature of this quadtree variation, the length and the width of the matrix must be 3P x 3P. If the original size does not fit this condition, it will be padded so that it will fit the appropriate size (For example, a matrix of 4 * 8 must be rounded to 9 * 9).
An example of the process is shown below:
- Initial matrix:
- Matrix after padding:
- Because initial matrix is not homogenous, the matrix is split and the process is repeated:
Create a code to help the group perform this quadtree variation and count how many homogenous areas there are.
Input
The first line contains the integer R and C (1 <= R, C <= 81).
The second lien contains R lines of C values of the matrix to be processed.
Output
Output the number of homogenous areas that are in the matrix followed by a newline.