i178. 比大小 (Cards)
Tags : 二分搜 前綴和 機率 貪心
Accepted rate : 51人/74人 ( 69% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-05 20:19

Content

注意:這題原題目敘述不清楚,請記得看下面的補充說明。

小智和小遙很喜歡玩比大小的遊戲,每當他們被分配到一些自己不想做的工作時,就會問對方願不願意來玩一場比大小,輸家要負責做贏家的工作。

比大小的規則十分簡單:小智和小遙會各自準備一副空白的卡片,並在每一張卡片上寫一個數字,接著他們從牌組中隨機抽出一張牌,上面數字較大的人獲勝。如果平手的話他們會把卡片放回牌組裡面,均勻洗牌以後用同樣的規則繼續比下去,直到分出勝負。

他們都會先看過對方的牌組,確認自己覺得對方不會比較有利。他們也都有好好洗牌,所以抽到每一張牌的機率相等,因此原本比賽的進行應該是公平的。然而,小智為了讓自己少做一點工作所以偷偷作弊,他總是會在看完小遙的牌組以後,偷偷離開再寫一個數字到一張新的空白卡片上,並把這張卡片加進自己的牌組裡面。

小智希望在自己寫上數字以後獲勝的機率不會降低,而且獲勝的機率可以比輸掉的機率高,也就是在所有對決情況中「自己的牌比對方的牌大的次數」要多於「自己的牌比對方的牌小的次數」。舉例來說,若小智的牌組有三張牌$\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 }$

Input

第一列有兩個整數 $\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}$),第二列代表小智原始的牌組每一張牌上的數字,第三列代表小遙的牌組每一張牌上的數字。

Output

如果在加了一張卡片以後小智獲勝的機率會提升,而且可以比輸掉的機率高,請輸出卡片上可以寫的最小整數。如果無法達成目標則輸出$\color{black}{-1}$。

Sample Input #1
3 3
1 1 5
1 2 4
Sample Output #1
5
Sample Input #2
3 3
1 2 4
1 1 3
Sample Output #2
2
Sample Input #3
3 3
1 2 3
1 2 4
Sample Output #3
-1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1K
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <1M
公開 測資點#10 (5%): 1.0s , <1M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <10M
公開 測資點#14 (5%): 1.0s , <10M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :

第一組(測資點$\color{black}{00}$~$\color{black}{05}$):$\color{black}{X , Y ≤ 1000}$。

第二組(測資點$\color{black}{06}$~$\color{black}{19}$):無特別限制。

Tags:
二分搜 前綴和 機率 貪心
出處:
TOI練習賽202204潛力組第2題 [管理者: linlincaleb@ ... (臨末之頌) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
31723 forkidlai (forkidlai) i178
python AC tip
455 2022-08-16 15:46