說明
我們可以將這個題目分成兩個部份:
一、剪開紙張,做成骰子
二、判斷有幾種不同的骰子
然而在做這兩件事之前,必須先決定出表示一個骰子的方式,
通常是用一個序列來表示,在本文接下來的部分將此稱作「編碼」。
第一部分
對紙張的每一個位置,將展開圖貼上去,
只要展開圖沒有超出紙張,就可記錄成一個骰子。
骰子展開圖的基本款有十一個,分三類:
(1) 中間四格
X | X | X | X | X | X
XXXX | XXXX | XXXX | XXXX | XXXX | XXXX
X | X | X | X | X | X
(2) 中間三格
XX | XX | XX
XXX | XXX | XXX
X | X | X
(3) 點對稱但不屬於第一類
XX | XXX
XX | XXX
XX |
可以算出扣除旋轉、鏡射前共有64種。
分成三類是因為第一、二類可以透過開迴圈省去不少程式碼。
第二部分
在第一部分中,有可能編碼相異,卻仍代表相同的骰子。
因此,我們要把原本的編碼轉換成「標準」編碼,
讓同樣的骰子有相同的標準編碼,
不一樣的骰子的標準編碼會相異。
提供兩種作法:
(1) 同rockwyc992所說,互不相鄰的兩個面分在同一組,
然後每組中編號較小(或較大)的排到第一個,
這三組再依字典序排成小到大(或大到小)。
然而,我們在做排序時用到許多的「交換」,
而任何一種交換都能對應到一種「鏡射」,
因此我們要記錄在此過程中交換的次數,
模2之後記錄在骰子上。
還要注意的是,有兩種類型的骰子做鏡像後仍和自己一樣,
交換次數要算做零:
1.有任何一組中的兩個面相同。Ex:a-a, b-c, d-e.
2.有兩組以上相同。Ex:a-b, c-d, c-d.
(2) 旋轉骰子,各個方向都試一遍,會得到6*4=24種序列。
挑字典序最小(或最大)的序列取代原本的序列。
轉換成標準編碼之後,
便可透過一些簡單的方法算出有幾種不同的骰子。
提供三種作法:
(1) 排序
(2) 使用樹狀結構
(3) Hash Table
時間複雜度
第一部分:
我們令第一部分做出了X顆骰子
──X約為N*M*64(高度*寬度*展開圖數目)──
這樣是O(X)。
第二部分:
取決於用的排序方式或樹狀結構或Hash方式,
盡量是O(X)或O(XlogX),O(X^2)恐怕會TLE。