f449. 未完成的方形數字 - 高中生程式解題系統

內容

文文參加資訊學科能力競賽，其中第六題是「方形數字」，現場想不到解法，時間也不太夠，於是隨便寫個程式撈 20% 的部份分就算了。回家以後才想到可以簡化這題的方式。

原題的「方形數字」的 1 從中間開始，往外圍遞增。如果改成從左下角開始，往右方及上方遞增，題目就變得較為簡單，甚至有可能導出公式寫出 𝑂(1) 的解。

如果我們可以找到一個方法求出左下角從 (1, 1) 開始到右上角 (𝑥, 𝑦) 的矩形內數字的和 (以下簡稱矩形和, rectangular sum)，並稱之為 𝑟𝑠(𝑥, 𝑦)，那麼所求左下角 (𝑥₁+1, 𝑦₁+1) 到右上角 (𝑥₂, 𝑦₂) 的矩形裡的數字和便是 𝑟𝑠(𝑥₂, 𝑦₂) - 𝑟𝑠(𝑥₂, 𝑦₁) - 𝑟𝑠(𝑥₁, 𝑦₂) + 𝑟𝑠(𝑥₁, 𝑦₁)。

以上圖為例，如果要求左下角 (3, 4) 右上角 (6, 9) 的紅色矩形內的數字和，可以先計算左下角 (1, 1) 到右上角 (6, 9) 那個最大的矩形和 𝑟𝑠(6, 9)，減掉左半邊的矩形和 𝑟𝑠(2, 9) 及下半部的矩形和 𝑟𝑠(6, 3)，再加上左下角的矩形和 𝑟𝑠(2, 3)，就可以得到右上角所求紅色矩形內的數字和。

可是原題裡的原點是在正中央而不是左下角。而且所求的矩形有可能橫跨不同的象限。於是文文把所求的矩形依象限切割成四個矩形和一個原點如下圖，用上面的方法可以求出第一象限內 (含 𝑋 軸) 的矩形和。

然後將座標旋轉 90°，把第二象限的矩形轉到第一象限，用同樣的方法求矩形和。

如此依序把四個象限的矩形和都求出來再加上原點就可以得到答案了。

因為文文參加資訊學科能力競賽累了一天，他只完成把所求矩形切割出第一象限的範圍並依序旋轉的程式碼。麻煩你幫他繼續完成 𝑟𝑠(𝑥, 𝑦) 的部份，也就是求左下角 (1, 1) 到右上角 (𝑥, 𝑦) 的矩形和。

文文的程式碼：

Python

n = int(input())
x1, y1, x2, y2 = (x - n for x in                #原點轉成 (0, 0)
                  map(int, input().split()))
s = int(min(x1, x2) <= 0 <= max(x1, x2) and
        min(y1, y2) <= 0 <= max(y1, y2))        #是否包含原點
for _ in range(4):                              #4 個象限
    x4 = max(max( 0, x1), max( 0, x2)) + 1      #切第一象限範圍：
    y4 = max(max(-1, y1), max(-1, y2)) + 1      #(x3+1, y3+1)-(x4, y4)
    x3 = min(max( 1, x1), max( 1, x2))          #原點轉成 (1, 1)
    y3 = min(max( 0, y1), max( 0, y2))          #不含 Y 軸
    s += rs(x4, y4) - rs(x4, y3) \
       - rs(x3, y4) + rs(x3, y3)
    x1, y1 = y1, -x1                            #轉90度
    x2, y2 = y2, -x2
print(s % 10**9)

C++

#include <iostream>
#include <algorithm>
using namespace std;
#define M 1000000000

int main() {
    int n, x1, y1, x2, y2, x3, y3, x4, y4, t, k;
    long long s;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    x1 -= n, y1 -= n, x2 -= n, y2 -= n;         //原點轉成 (0, 0)
    s = min(x1, x2) <= 0 && 0 <= max(x1, x2) &&
        min(y1, y2) <= 0 && 0 <= max(y1, y2);   //是否包含原點
    for (k = 0; k < 4; k++) {                   //4 個象限
        x4 = max(max( 0, x1), max( 0, x2)) + 1; //切第一象限範圍：
        y4 = max(max(-1, y1), max(-1, y2)) + 1; //(x3+1, y3+1)-(x4, y4)
        x3 = min(max( 1, x1), max( 1, x2));     //原點轉成 (1, 1)
        y3 = min(max( 0, y1), max( 0, y2));     //不含 Y 軸
        s += rs(x4, y4) - rs(x4, y3)
           - rs(x3, y4) + rs(x3, y3);
        t = -x1, x1 = y1, y1 = t;               //轉90度
        t = -x2, x2 = y2, y2 = t;
    }
    cout << (s % M + M) % M << endl;
}

輸入說明

高中組：𝑁 < 10 測試資料共佔 20%，另有 𝑁 < 10⁹ 測試資料共佔 80%。

輸出說明

高中組輸出末九位正確就算正確。

範例輸入 #1

6
3 9 10 6

範例輸出 #1

範例輸入 #2

5
1 9 5 6

範例輸出 #2

範例輸入 #3

1
1 1 1 1

範例輸出 #3

測資資訊：

記憶體限制： 64 MB

提示：

1. 這題的測試資料和「f432. 方形數字」完全相同，AC 這題的程式碼也可以 AC f432。

2. 這題的測試資料是高中組的範圍，AC 這題的程式碼應該也可以 AC 國中組的「f428. 高雄市109年資訊競賽國中組第六題」，但是答案要全對，而不是只比對最後九位數。

標籤:

出處:

2020 高雄市資訊學科能力競賽高中組 6 [管理者： snail (蝸牛) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」