ZeroJudge I859: Can You Solve It?

同題：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.

ZeroJudge I859 題目敘述用圖

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

如果把步數標出來的話，可以發現 Y 軸 (橫軸) 的步數是 0 –> 1 –> 3 –> 5 –> 9，以此類推。舉例來說，當 x + y 等於 2 的時候，可以發現這些點都落在 (0, 2) 這個點的斜線上，更可以發現 (1, 1) 這個點是 (0, 2) 的步數＋1，也就是其x座標。同理，(2, 0) 的步數就是 (0, 2) 的步數＋2。

ZeroJudge I859 解題思路解說用圖

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
Tags

Related Posts

Comments