時間限制 1000 ms ・ 記憶體限制 256 MB
題目描述
小智和小遙各有一副牌，每張牌上寫著一個整數。兩人各自等機率抽出一張牌，數字較大者獲勝。如果數字相同，就把牌放回各自牌組、均勻洗牌，再抽一次，直到分出勝負。
小智看過對方的牌後，想在自己的牌組加入一張新牌。新牌的數字必須已經出現在小智原來的牌組中。他希望加入新牌後，獲勝機率不會降低，且獲勝機率要高於落敗機率；原題以所有兩人抽牌配對中，自己的牌較大的次數多於較小的次數來說明後一個條件。請求出符合要求的最小新牌數字。
例如小智持有 1、1、5，小遙持有 1、2、4，原有九種配對中，小智勝出的有三種，落敗的有四種。加入一張 5 後，勝出的配對變成六種，落敗的仍為四種。即使牌上的數字相同，不同實體卡片仍分別計算抽到的情況。
輸入格式
第一行為整數 X、Y，分別表示小智、小遙原來的卡片張數。第二行提供 X 個整數，為小智的牌；第三行提供 Y 個整數，為小遙的牌。
- 0 ≤ X、Y ≤ 10^5
- 每張牌的數字介於 0 與 10^9，含兩端。
原題分組：30 分滿足 X、Y ≤ 1000；70 分依完整限制。
輸出格式
若存在加入後使獲勝機率不降低、且獲勝機率高於落敗機率的新牌數字，輸出其中最小的整數；否則輸出 -1。
官方資料校對與待釐清事項
本稿僅供待審，尚未建立完整隱藏測資。
- PDF 輸出段落使用「會提升」，但官方參考程式與解題投影片第 16 頁明確使用新勝率大於等於舊勝率，並要求新勝局數嚴格大於新敗局數。因此採用與題目描述一致的「不降低」。
- 官方仍容許 X 或 Y 等於 0，卻沒有定義空牌組的抽牌方式；全部配對都平手時，原始勝率也未定義。參考程式對零分母運算無明確數學定義，不能把程式偶然結果當作規格，這些邊界仍需釐清。
- 不採用鏡像另增的條件；官方計算的是排除平手後的勝率。
範例 1
輸入：
3 3
1 1 5
1 2 4
輸出：
5
範例 2
輸入：
3 3
1 2 4
1 1 3
輸出：
4
範例 3
輸入：
3 3
1 2 3
1 2 4
輸出：
-1
來源
TOI 2022/04 練習賽潛力組〈比大小（Cards）〉。本稿依官方 PDF 自行整理文字，保留原題未釐清處及全部官方範例。
原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202204/Cards.pdf
官方解題投影片：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202204/Cards.odp 官方參考程式：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202204/Cards.zip
範例測資
範例輸入 1
3 3 1 1 5 1 2 4
範例輸出 1
5
範例輸入 2
3 3 1 2 4 1 1 3
範例輸出 2
4
範例輸入 3
3 3 1 2 3 1 2 4
範例輸出 3
-1
討論與題解
載入討論區…