切換
舊版
前往
大廳
主題

ZeroJudge - a097: PARKET 解題心得

Not In My Back Yard | 2019-04-05 22:58:47 | 巴幣 0 | 人氣 146

題目連結:


題目大意:
現有兩種顏色 1 × 1 的地磚,一為白、一為黑。而有一種地磚的拼法是中間的矩形由 R 個黑色地磚拼成,外圍由 B 個白色地磚圍繞著。其中,中央矩形周圍的白色邊框之厚度四周皆相同。

給定 B 、 R (皆小於 2 ^ 30),求這個地磚拼法佔的長 L 與寬 W (L ≧ W)。若有多組可能的 L 、 W 值,請輸出 L 、 W 相差最大的那一組。



範例輸入:
8 1
10 2


範例輸出:
3 3
4 3


解題思維:
因為給定了中間的矩形之面積,所以我們可以對其做因式分解為兩整數之積 x × y 。每窮舉出一組 x 、 y 時,試試看邊框的面積是否可以為 B 。驗證方法如下:

設邊框的厚度為 T ,因為 B = 2(x + y)T + 4T ^ 2,所以
T = (((x + y) ^ 2+4B)之平方根 - (x + y)) ÷ 4
檢查 T 是否為整數,即可知道這組 x 、 y 可否有解。

當 x 由小到大跑過,且遇到有一組 x 、y 有解時,此時 L = y + 2T、 W = x + 2T 即為題目所求。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作