題目連結:
數字 0 ~ 9 於七段顯示器的圖形如下:
也就是數字都變為由 3 × 3 個字元組成,字元是空白、「_」或是「|」。
給定一正整數,代表接下來有多少組的七段顯示器數字要處理。每組一共九個數字,形式則是按照上面的圖示給定,但是可能會有一個數字會糊掉(少掉線段,不會多出來)。其代表一組可能的帳號。
檢查帳號是否合法的方式則是將數字由左至右編號為 d9 、 d8 、 d7 …… 、 d1 ,並計算檢查碼,公式為
d9 × 9 + d8 × 8 + …… + d1 × 1 取 11 的餘數是否為 0
餘數為 0 ,代表此帳號是合法的;反之,帳號不合法。
但是可能會有糊掉的數字(保證糊掉的數字只會有一個,且糊掉後不會是其他的數字),所以要盡可能地還原。
如果此組帳號合法或是可以還原出原本的合法帳號,請輸出帳號數字本身(以字元表示即可);如果無法還原,則輸出「failure」;如果有多組可能的帳號,則輸出「ambiguous」。
(在巴哈看會歪掉,建議去原題目觀看)
5
_ _ _ _ _ _ _
| _| _||_||_ |_ ||_||_|
||_ _| | _||_| ||_| _|
_ _ _ _ _ _
| _| _||_||_ |_ ||_| |
||_ _| | _||_| ||_| |
_ _ _ _ _ _ _
|_||_|| || ||_ | | || |
| _||_||_||_| | | | _|
_ _ _ _ _ _ _ _ _
|_||_||_||_||_||_||_||_||_|
|_||_||_||_||_||_||_||_||_|
_ _ _ _ _ _ _ _ _
|_| |_||_||_||_||_||_||_|
|_| ||_||_||_||_||_||_||_|
123456789
failure
490067719
failure
878888888
首先,先說明一下不會有「ambiguous」的狀況發生(這個只是題目用來混淆視聽)。因為如果沒有任何數字糊掉(輸入的每個七段顯示數字都能找到正確對應),則表示這組數字即是帳號的真實樣子(不管合不合法);就算有糊掉的數字,也不會有多組解的狀況發生(因為只有一個數字糊掉)。
剩下的就是判斷每個七段顯示器的文字實際對應的數字是哪些(糊掉的字所在之位置就特別記起來),然後按照檢查方式計算檢查碼(略過糊掉的數字)。
如果沒有任何數字糊掉,則直接看檢查碼是否為 0 去判斷合法性,不合法就輸出「failure」;如果有數字糊掉,就看糊掉所剩下的部分可以對應到哪些數字,並試試看加入了那些數字可不可以使檢查碼為 0 。如果窮舉之後,檢查碼依然不為 0 ,則輸出「failure」。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。