f449: 未完成的方形數字
Tags :
Accepted rate : 25人/29人 ( 86% ) [非即時]
評分方式:
Special

最近更新 : 2020-11-30 20:49

Content

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

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

如果我們可以找到一個方法求出左下角從 (1, 1) 開始到右上角 (x, y) 的矩形內數字的和 (以下簡稱矩形和, rectanglar sum),並稱之為 rs(x, y),那麼所求左下角 (x1+1, y1+1) 到右上角 (x2, y2) 的矩形裡的數字和便是 rs(x2, y2) - rs(x2, y1) - rs(x1, y2) + rs(x1, y1)。

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

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

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

 => 

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

 => 

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

文文的程式碼:

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)

 

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;
}
Input

高中組:N < 10 測試資料共佔 20%,另有 N < 109 測試資料共佔 80%。

Output

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

Sample Input #1
6
3 9 10 6
Sample Output #1
110
Sample Input #2
5
1 9 5 6
Sample Output #2
80
Sample Input #3
1
1 1 1 1
Sample Output #3
1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1K
公開 測資點#5 (5%): 1.0s , <1K
公開 測資點#6 (5%): 1.0s , <1K
公開 測資點#7 (5%): 1.0s , <1K
公開 測資點#8 (5%): 1.0s , <1K
公開 測資點#9 (5%): 1.0s , <1K
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1K
公開 測資點#12 (5%): 1.0s , <1K
公開 測資點#13 (5%): 1.0s , <1K
公開 測資點#14 (5%): 1.0s , <1K
公開 測資點#15 (5%): 1.0s , <1K
公開 測資點#16 (5%): 1.0s , <1K
公開 測資點#17 (5%): 1.0s , <1K
公開 測資點#18 (5%): 1.0s , <1K
公開 測資點#19 (5%): 1.0s , <1K
Hint :

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

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

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


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」