小藍(lán)有 N 個小球,編號 1 至 N。其中 N ? 1 是正品,重量相同;有 1 個是次品,重量比正品輕。
為了找出次品,小藍(lán)已經(jīng)用天平進(jìn)行了 M 次稱重,并且記錄下來每次兩邊放的小球編號,和稱重結(jié)果。
請你根據(jù)記錄,判斷還剩下幾個小球有次品的嫌疑。
第一行包含 2 個整數(shù) N 和 M。
以下包含 M 次稱重記錄,每個記錄占 4 行。
第一行是一個整數(shù) K,表示天平兩邊各放了 K 個小球。
第二行包含 K 個整數(shù),代表放在天平左邊的小球編號。
第三行包含 K 個整數(shù),代表放在天平右邊的小球編號。
第四行是一個字符,為 ‘>’, ‘<’, ‘=’ 之一?!?gt;’ 代表左邊比右邊重,‘<’ 代表左邊比右邊輕,‘=’ 代表兩邊重量相等。
在一次稱重中保證每個小球最多出現(xiàn) 1 次。
輸出一個整數(shù),代表答案。
10 2 3 1 2 3 4 5 6 < 2 3 7 8 9 =
2
{1, 2, 3} < {4, 5, 6} 能判斷出次品在 {1, 2, 3} 之中。
{3, 7} = {8, 9} 能判斷出 3 不可能是次品。
所以只剩下 {1, 2} 可能是次品。
對于 40% 的數(shù)據(jù),1 ≤ N ≤ 106 ;
對于 100% 的數(shù)據(jù),1 ≤ N ≤ 109 , 1 ≤ M ≤ 105 , 參與 M 次稱重的小球總數(shù) ≤ 106 .
為了更好地備戰(zhàn)即將到來的藍(lán)橋杯國賽競賽?,我們特別準(zhǔn)備了藍(lán)橋杯歷年真題供大家學(xué)習(xí)和練習(xí).