XChiChiX


這不是很戲劇化的發展嗎

UVA-10642: Can You Solve It?

  • 1353 字
  • 次閱讀
  • 則評論
  1. 1. 內容
  2. 2. 範例輸入
  3. 3. 範例輸出
  4. 4. 想法
  5. 5. 程式碼

CPE 一顆星選集 49 道必考題

題目連結:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1583

內容


給定兩座標(y, x)，求出從一點走到另一點所需的步數。

輸入第一列 n (0 < n <= 500) 代表測資數，接著為兩點座標(0 <= y, x <= 100000)。

範例輸入

3
0 0 0 1
0 0 1 0
0 0 0 2

範例輸出

Case 1: 1
Case 2: 2
Case 3: 3

想法

觀察後發現，如果從 (0, 0) 開始，到(0, x) 的步數為
到 (0, 1) = 1
到 (0, 2) = 3
到 (0, 3) = 6
到 (0, 4) = 10

因此可以先將 y = 0 的點到 (0, 0) 的步數用陣列存起來

1
2
mp[0] = 0;
for(int i = 1; i < 100001; ++i) mp[i] = mp[i-1] + i;

接著繼續觀察後發現，可以按照 y + x 的值來分組
y + x = 1
(0, 1) = 1
(1, 0) = 2

y + x = 2
(0, 2) = 3
(1, 1) = 4
(2, 0) = 5

y + x = 3
(0, 3) = 6
(1, 2) = 7
(2, 1) = 8
(3, 0) = 9

經由上述觀察，可以先找出此座標的組別(y + x 的值)，接著利用已知的(0, x)步數 + 座標的 y 值，得到此座標到原點的步數，兩座標到原點的步數相減即為所求。

程式碼

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int main(){
    fastio;
    int n, y1, x1, y2, x2, mp[100001];
    mp[0] = 0;
    for(int i = 1; i < 100001; ++i) mp[i] = mp[i-1] + i;
    cin >> n;
    for(int c = 1; c <= n; ++c){
        cin >> y1 >> x1 >> y2 >> x2;
        int step1 = mp[y1+x1] + y1, step2 = mp[y2+x2] + y2;
        cout << "Case " << c << ": " << step2 - step1 << "\n";
    }
    return 0;
}
,