| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11710 | GCD(recursive) |
|
| 14070 | Road Roller V2 |
|
Description
Given two positive integers a and b, compute the greatest common divisor (GCD) of a and b. The GCD of a and b is the biggest integer that can divide a and b with no reminder.
Input
First line contains a positive integer t (t<=10000), which indicates the number of test cases in the input. In the next t lines, each line contains two positive integers a, b, which are smaller than or equal to 10^6.
Output
For each case, output the GCD of a and b in a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
After Koying flattened the road, he realised that he still falls over often while walking on the NTHU streets. He believe that there is an issue with his road-constructing strategy, so he did some modifications to the program and simulated its process.
His program simulates the following environment:
There is a grid of N × M cells, representing the map of Hsinchu City. Each cell has a bumpy value (崎嶇值).
A higher bumpy value means a more bumpy, and a bumpy value of 0 represents a flat (平整的) area.
Whenever the road roller passes over a cell, the ground becomes flattened, and the cell's bumpy value is set to 0.
After the modifications, Koying's movement rules are as follows:
- Koying will start from the grid with the highest Bumpy Value.
- Koying will not drive outside the boundaries of Hsinchu City, which range from (1, 1) to (N, M).
- Koying will choose the moving direction first.
Let X be the neighboring cell in one of the eight directions (up, down, left, right, up-left, up-right, down-left, down-right) with the highest bumpy value and has not been flattened (bumpy value > 0). Koying will choose the direction of X as his moving direction. - Koying will start driving the road roller to the direction of X.cKoying will stop until he is on a cell with a higher bumpy value than X or he is on the last cell in that direction. When Koying stops on a cell, he will flatten it. After flattening the cell he stopped on, he will find a new direction to move on (go to step 3).
(Hint: in this step, Koying won't stop when he reaches a cell with a bumpy value of 0, or all his surrounding cells' bumpy values are 0.) - Koying will ulternatively stop rolling the road when all eight neighboring directions around Koying have been flattened.
Your task is to calculate the total sum of flattened ground's bumpy values.
Note that if a cell is passed over multiple times, it's bumpy value should not be accumulated more than once since each area can only be flattened once.
If Koying manages to flatten all the roads in Hsinchu City, you should output "Road Roller Da!!".
As Koying is currently occupied with helping the power plant at National Tsing Hua University generate electricity, and his absence might lead to a power outage, he has requested you to finish this program so that he can focus on power generation.
No recursion is required in this problem! :)
Input
The first line contains two positive integers, N and M, representing the size of the grid.
Following that, there are N lines, each containing M positive integers Ai, j, indicating the bumpy value of the grid cell at row i and column j.
Constraints:
- testcases 1 ~ 2: N = 1
- testcases 3 ~ 6: 1 ≤ N ≤ 100
- For all testcases : 1 ≤ N, M ≤ 100, 1 ≤ Ai, j ≤ 10,000
- It is guaranteed that no two grid cells have the same bumpy value.
Output
In the first line, please output a positive integer, representing the total sum of flattened ground's bumpy values.
If the road roller manages to pass over every grid cell, please output "Road Roller Da!!" (without quotation marks) on the second line.
Remember to print a ‘\n’ at the end of the output.