時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
有 N 枚硬幣，編號為 1 到 N。其中恰好一枚是假幣，其重量與真幣不同；其餘硬幣的重量都相同。假幣可能較重，也可能較輕，事先並不知道是哪一種。
已經使用天平進行 K 次秤重。每次在左右兩盤放入相同數量的硬幣，並記錄兩盤上的硬幣編號及比較結果：
<：左盤總重量小於右盤。>：左盤總重量大於右盤。=：左右兩盤總重量相同。
根據全部紀錄，判斷能否唯一確定假幣的編號。若可能是假幣的硬幣不只一枚，就無法確定。只需辨認編號，不必判斷它較重或較輕。
輸入格式
第一行是資料組數 M，接著有一個空白行，再給出 M 組資料；相鄰資料組之間也有一個空白行。
每組第一行有兩個整數 N K，其中 1 ≤ N ≤ 100、1 ≤ K ≤ 100。
接下來的 2K 行，每兩行描述一次秤重：
- 第一行先給出整數
P（1 ≤ P ≤ ⌊N/2⌋），接著是左盤的P個硬幣編號，再接著是右盤的P個硬幣編號。整數以空白分隔。 - 第二行只有一個比較符號
<、>或=，意義如上。
輸出格式
每組資料輸出一行。若能唯一確定假幣，就輸出其編號；若根據秤重紀錄無法確定，則輸出 0。
相鄰兩組輸出之間必須有一個空白行。
題目來源
範例測資
範例輸入 1
2 5 3 2 1 2 3 4 < 1 1 4 = 1 2 5 = 6 4 3 1 2 3 4 5 6 < 1 1 2 = 2 1 3 4 5 < 2 4 5 2 6 >
範例輸出 1
3 0
請先登入後再提交程式碼
討論與題解
載入討論區…