b579: 恢復分數
Tags : 數論
Accepted rate : 3人/8人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2015-10-21 13:26

Content

A, B, C, D 四個人參加一個考試,這個考試是10題是非題(Y/N),每答對一題得一分,下列圖表是一個範例,我們知道A, B, C 三人的分數,但缺了 D 的分數,我們從 A, B, C, D 的答案和三個人的分數,想算出 D 的分數。下面的範例我們可以知道 D 應該是得 5 分,不過有些情況我們沒辦法確定 D 的分數。

 12345678910Point
AYNNYYNYNYN8
BYYNNYNYNNY4
CNYYYYNYYNN7
DNNYYNYYYNY?

你的任務就是寫一個程式來從 n 個同學的答案和前(n-1)的分數,判斷能不能確認第 n 個同學的分數

 

Input

每一組測試資料的第一行有兩個數字 n 的學生及 p 道是非題, 1 <= n <= 20 且1 <= p <= 60. 接下來的 n 行資料,前 n-1 行資料會是一個分數與 p 個是非題的回答,第 n 行只有 p 個是非題答案。

當程式讀到只有一個數字 0 時結束

Output

有三種可能的輸出
1. 如果輸入的資訊相互矛盾,不能判斷,請輸出 'c'
2. 如果輸入的資訊正確,但是沒辦法算出分數,請輸出 'n'
3. 如果輸入的資訊正確,也能算出最後一人的分數,請輸出 'y' 及分數

Sample Input #1
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
Sample Output #1
y 5
c
n
測資資訊:
記憶體限制: 128 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :

這題是將整體問題縮減(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,矛盾
以上檢查均通過,則表示無法縮減

Tags:
數論
出處:
SEARCC-ISSC國際學生程式設計競賽 [管理者:
spocktsai (囧rz)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」