注意:這題原題目敘述不清楚,請記得看下面的補充說明。
小智和小遙很喜歡玩比大小的遊戲,每當他們被分配到一些自己不想做的工作時,就會問對方願不願意來玩一場比大小,輸家要負責做贏家的工作。
比大小的規則十分簡單:小智和小遙會各自準備一副空白的卡片,並在每一張卡片上寫一個數字,接著他們從牌組中隨機抽出一張牌,上面數字較大的人獲勝。如果平手的話他們會把卡片放回牌組裡面,均勻洗牌以後用同樣的規則繼續比下去,直到分出勝負。
他們都會先看過對方的牌組,確認自己覺得對方不會比較有利。他們也都有好好洗牌,所以抽到每一張牌的機率相等,因此原本比賽的進行應該是公平的。然而,小智為了讓自己少做一點工作所以偷偷作弊,他總是會在看完小遙的牌組以後,偷偷離開再寫一個數字到一張新的空白卡片上,並把這張卡片加進自己的牌組裡面。
小智希望在自己寫上數字以後獲勝的機率不會降低,而且獲勝的機率可以比輸掉的機率高,也就是在所有對決情況中「自己的牌比對方的牌大的次數」要多於「自己的牌比對方的牌小的次數」。舉例來說,若小智的牌組有三張牌$\color{black}{1}$ 、$\color{black}{1}$、$\color{black}{5}$,小遙的牌組有三張牌$\color{black}{1}$、$\color{black}{2}$、$\color{black}{4}$,而我們用$\color{black}{(a, b)}$ 來代表小智抽到的數字 $\color{black}{a}$ 以及小遙抽到的數$\color{black}{b}$,則在$\color{black}{3×3=9}$ 種情況中,小智獲勝的情況有 $\color{black}{(5, 1)}$、$\color{black}{(5, 2)}$、$\color{black}{(5, 4)}$三種,小智輸掉的情況有 $\color{black}{(1, 2)}$、$\color{black}{(1, 2)}$、$\color{black}{(1, 4)}$、$\color{black}{(1, 4)}$四種,所以現在小智的勝率較低。但如果小智增加了一張寫著 $\color{black}{5}$ 的卡片,則小智獲勝的情況就會變成六種,而輸掉的情況還是四種,獲勝的機率就高於輸掉的機率了。
為了不要讓小遙起疑心,小智寫上去的數字必須是原本就存在於自己牌組裡的數字,而且這個數字越小越好。請你算算看小智應該要寫上什麼數字?
補充說明:
在本題假設$\color{black}{W}$代表原來全部牌中小智贏的組合的總組合數;$\color{black}{L}$代表小智輸的組合的總組合數,本題就是要你找到一個$\color{black}{A}$裡面最小的數字,假設這張牌和小遙的所有牌比較的輸贏組合數分別為$\color{black}{w}$、$\color{black}{l}$,讓以下條件皆成立:
$\color{black}{(1)\ l ≤ w}$
$\color{black}{(2)\ L + l < W + w }$
第一列有兩個整數 $\color{black}{X}$ 和 $\color{black}{Y}$ ( $\color{black}{ 1 ≤ X, Y ≤ 10^5}$ ),代表一開始小智與小遙牌組的卡牌數量。第二列與第三列分別有 $\color{black}{X}$ 個與 $\color{black}{Y}$ 個整數(數值介於 $\color{black}{1}$和 $\color{black}{10^9}$),第二列代表小智原始的牌組每一張牌上的數字,第三列代表小遙的牌組每一張牌上的數字。
如果在加了一張卡片以後小智獲勝的機率會提升,而且可以比輸掉的機率高,請輸出卡片上可以寫的最小整數。如果無法達成目標則輸出$\color{black}{-1}$。
3 3 1 1 5 1 2 4
5
3 3 1 2 4 1 1 3
2
3 3 1 2 3 1 2 4
-1
第一組(測資點$\color{black}{00}$~$\color{black}{05}$):$\color{black}{X , Y ≤ 1000}$。
第二組(測資點$\color{black}{06}$~$\color{black}{19}$):無特別限制。