切換
舊版
前往
大廳
主題

ZeroJudge - a264: 骰子疊疊樂 解題心得

Not In My Back Yard | 2019-08-16 22:41:48 | 巴幣 0 | 人氣 309

題目連結:


題目大意:
給定一正整數 n (1 ≦ n ≦ 1000000000),求至少要多少個骰子疊在一起,才能骰子有漏出來的那幾面之總和恰好為 n 。如果不可能湊出總和為 n ,輸出「-1」。

骰子的剖面圖:

骰子的疊法:
(最下面的那一面也算在總和裡,但是夾在骰子間的不算)



範例輸入:
50
7
32


範例輸出:
3
-1
2


解題思維:
首先觀察不同骰子的數量,其可能的總合為多少:
一顆骰子,六面皆露出,所以總和為 21 。

兩顆骰子,中間夾住的面有兩面而各自都可以為 1 ~ 6 。因此總和可為 30 (2 × 21 - 12)~ 40 (2 × 21 - 2)。

三顆骰子,此時開始出現一些特別的狀況 —— 中間的骰子不管怎麼擺,沒有露出來的那兩面總和必為 7 。這是因為骰子的點數有經過設計,相對面的點數之和必為 7 。例如點數 1 的對面即是 6 、點數 2 的對面是 5 ……(不是題目特別,一般的骰子皆有此特性)
因此,中間那顆骰子表面總和必為 14 。所以三顆骰子的可能總和為 44 ~ 54 。(另外兩顆骰子的情況跟只有兩顆骰子的情況一致)

四顆骰子,同三顆骰子,中間兩顆各自的總和必為 14 。因此可能的總和必為 58 ~ 68。

……以此類推。

以上,我們可以看到若 n 小於 30 但不等於 21 時,一定不可能湊出。而當 n - 2 取 14 的餘數 > 10 (把 30 ~ 40 、 44 ~ 54 、 58 ~ 68 等區間以餘數的形式表示為:n - 2 取 14 的餘數 ≦ 10)時,同樣也不可能湊出。

剩下的可以湊出的 n 值,其需要的骰子即為 (n - 2) ÷ 14 (取整),除了 n = 21 時,此時只需一顆骰子。

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

創作回應

更多創作