UVa 10642 – Can You Solve It?
In the following diagram, each circle has a coordinate. According to the Cartesian coordinate system, you can move from one circle to another following the arrow paths shown below.
total_number_of_step(s)_needed = number_of_intermediate_circles_you_pass + 1
For example, to move from (0, 3) to (3, 0), you must pass through two intermediate circles, (1, 2) and (2, 1). So, in this case, the total number of steps required is 2 + 1 = 3.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line is an integer N representing the number of test cases. Following are N lines, each containing 4 integers x1, y1, x2, y2 (0 ≤ x1, y1, x2, y2 ≤ 100000). (x1, y1) represents the starting coordinates. (x2, y2) represents the target coordinates. | For each test case, please output the test case number and the minimum number of steps required in the following format. |
| 3 0 0 0 1 0 0 1 0 0 0 0 2 | Case 1: 1 Case 2: 2 Case 3: 3 |
Thought Process
If we mark the steps, we can observe that the steps along the Y-axis (vertical axis) are 0 → 1 → 3 → 5 → 9, and so on. For example, when x + y equals 2, we can see that these points all lie on the diagonal passing through (0, 2). Furthermore, we can observe that the step count at (1, 1) is one more than the step count at (0, 2), which is its x-coordinate. Similarly, the step count at (2, 0) is two more than the step count at (0, 2).
You can start by setting up an array and storing numbers like 0, 1, 3, 6, 10, and so on at positions corresponding to the Y-coordinate (vertical axis). While receiving the data, determine the value of x + y and find the step count at that position, then add the value of the x-coordinate.
Sample Code－ZeroJudge I859: Can You Solve It?
#include <iostream>
#include <vector>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
vector<long long int>Chueh;
long long int count = 0, add = 0;
for (int i = 0; i<=200000; i++)
{
count += add;
Chueh.push_back(count);
add++;
}
int N;
cin >> N;
for (int i = 0; i<N; i++)
{
long long int a, b;
cin >> a >> b;
long long int start = Chueh[a+b] + a;
cin >> a >> b;
long long int finish = Chueh[a+b] + a;
cout << "Case " << i+1 << ": " << finish-start << "\n";
}
}
//ZeroJudge I859
//Dr. SeanXD