h540: 神奇早餐店(Magic Shop)
Tags : math ٩(ˊᗜˋ*)و
Accepted rate : 24人/29人 ( 83% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-04 12:52

Content

麥夫非常喜歡魔法,大家都叫他mf(魔法)mf(麥夫)。

麥夫今天去吃早餐,老闆問他要不要喝點東西。

麥夫:「那我要一杯手工豆奶。」

老闆:「我們最近沒有磨奶」

麥夫:「那有熱可可嗎?」

老闆:「可可也沒了」

麥夫:「那一杯米漿好了。」

老闆:「米漿剛剛也沒囉。」

麥夫:「喔不我的咪...米漿...」

由於這間早餐店實在是太奇怪了,麥夫想要喝的飲料都剛好沒有了,所幸最後還有賣可樂,他還可以配可樂享用他的早餐。

「配cola...嗎...?」

「如果我再早一點來的話...或許可可跟米漿就不會沒了...」麥夫心想。

但是人稱的mfmf不是假的,他決定使用他的魔法,回到還有一個時間點,讓他可以買到最後一杯米漿。

於是他跟老闆要了今天早上準備了多少可可跟米漿。

可是不止這間店奇怪,來這間店裡光顧的人也都很奇怪,如果還有賣可可或是米漿,那他們會優先選擇購買可可或是米漿一杯,且他們不喜歡與前一個客人買同樣的飲料,除非可可或米漿有一個已經賣完了,他們才會勉為其難接受與前一個客人購買一樣的飲料。

mfmf對米漿情有獨鍾,但由於考慮到使用魔法對身體的負擔,他希望可以回到最晚的時間點,能保證他至少能買到最後一杯米漿,請問mfmf最晚應該成為第幾個來店裡的客人?

Input

輸入的第一行有一個整數$\color{black}{T}$,代表接著有$\color{black}{T}$筆測試資料。

接著有$\color{black}{T}$行,每行包含兩個正整數$\color{black}{C,R}$,代表老闆該天準備了$\color{black}{C}$杯可可跟$\color{black}{R}$杯米漿。

• $\color{black}{1≤T≤10^5}$

• $\color{black}{1≤C,R≤10^{10}}$

Output

對於每筆測試資料,請輸出一行包含一個整數$\color{black}{K}$,代表mfmf成為第$\color{black}{K}$個來店裡的客人可以保證他至少能買到最後一杯米漿,如果不管怎樣mfmf都買不到米漿了,請輸出٩(ˊᗜˋ*)و。

Sample Input #1
3
0 1
777 0
2 2
Sample Output #1
1
٩(ˊᗜˋ*)و
3
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (28%): 1.0s , <1M
公開 測資點#1 (28%): 1.0s , <1M
公開 測資點#2 (11%): 1.0s , <10M
公開 測資點#3 (11%): 1.0s , <10M
公開 測資點#4 (22%): 1.0s , <10M
Hint :

對於範例中的第三筆測試資料,最糟的情況是前面的客人買了米漿→可可→米漿,於是mfmf必須是至少第3個客人才能確保他能買到米漿。

子任務配分測資範圍限制
$\color{black}{subtask1}$$\color{black}{28\%}$$\color{black}{C=0}$
$\color{black}{subtask2}$$\color{black}{28\%}$$\color{black}{R=0}$
$\color{black}{subtask3}$$\color{black}{44\%}$$\color{black}{無特殊限制}$

 

Tags:
math ٩(ˊᗜˋ*)و
出處:
pcsh weekly contest [管理者:
Ststone1687 (使用C++的都邪教)
]


ID User Problem Subject Hit Post Date
30118
406490150@gm... (我是朱朱)
h540
test
77 2022-04-29 23:48
30107
pcsh_contest (板中競賽)
h540
113 2022-04-29 12:13