切換
舊版
前往
大廳
主題

ZeroJudge - a633: 13. Not Quite OCR 解題心得

Not In My Back Yard | 2019-09-11 20:26:12 | 巴幣 0 | 人氣 125

題目連結:


題目大意:
數字 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」。

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

創作回應

相關創作

更多創作