A, B, C, D 四個人參加一個考試，這個考試是10題是非題(Y/N)，每答對一題得一分，下列圖表是一個範例，我們知道A, B, C 三人的分數，但缺了 D 的分數，我們從 A, B, C, D 的答案和三個人的分數，想算出 D 的分數。下面的範例我們可以知道 D 應該是得 5 分，不過有些情況我們沒辦法確定 D 的分數。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Point | |
| A | Y | N | N | Y | Y | N | Y | N | Y | N | 8 |
| B | Y | Y | N | N | Y | N | Y | N | N | Y | 4 |
| C | N | Y | Y | Y | Y | N | Y | Y | N | N | 7 |
| D | N | N | Y | Y | N | Y | Y | Y | N | Y | ? |
你的任務就是寫一個程式來從 n 個同學的答案和前(n-1)的分數，判斷能不能確認第 n 個同學的分數
每一組測試資料的第一行有兩個數字 n 的學生及 p 道是非題， 1 <= n <= 20 且1 <= p <= 60. 接下來的 n 行資料，前 n-1 行資料會是一個分數與 p 個是非題的回答，第 n 行只有 p 個是非題答案。
當程式讀到只有一個數字 0 時結束
有三種可能的輸出
1. 如果輸入的資訊相互矛盾，不能判斷，請輸出 'c'
2. 如果輸入的資訊正確，但是沒辦法算出分數，請輸出 'n'
3. 如果輸入的資訊正確，也能算出最後一人的分數，請輸出 'y' 及分數
4 10 8 Y N N Y Y N Y N Y N 4 Y Y N N Y N Y N N Y 7 N Y Y Y Y N Y Y N N N N Y Y N Y Y Y N Y 3 2 1 Y N 2 Y N N N 3 2 1 Y N 1 N Y Y Y 0
y 5 c n
這題是將整體問題縮減(Reduce)到更小的規模來做解答
需要判斷的型態比較複雜,並且也可能存在無法縮減的狀況
極端來說,如果整個問題都無法縮減
則所求的答案必須與已經有回答的"完全相同" 或"完全相反",才會有解
而什麼樣的條件可以判定可以縮減呢
如果有兩筆成績與答題資料,題數為n,相異的題數為d,則相同題數為n-d,得分分別為a,b
則如果a-b=d,可確認相異答案的部分A全對+B全錯;a-b>d則矛盾
若b-a=d,則相異處B全對A全錯,b-a>d則矛盾
a+b=2n-d,則相同處AB都對,a+b>2n-d則矛盾
a+b=d,則相異處AB都錯,a+b<d則矛盾
若兩個人答案完全相同而分數不同,矛盾
兩人答案相反而分數和不為n,矛盾
以上檢查均通過,則表示無法縮減
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||