i115: 尋找紙牌
Tags :
Accepted rate : 5人/7人 ( 71% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-04-30 20:49

Content

今天雨昕把編號$\color{black}{0、1、2、……、N-1}$的紙牌按順序順時針排成一圈,$\color{black}{N=5}$的case如下圖。

也就是對於每張牌$\color{black}{k}$,他的順時針方向那張是$\color{black}{k+1}$,逆時針那張是$\color{black}{k-1}$,除了$\color{black}{0}$和$\color{black}{N-1}$例外。

首先定義任兩張牌$\color{black}{a}$、$\color{black}{b}$的距離$\color{black}{dist(a,b)}$代表$\color{black}{a}$從順時針或逆時針方向兩邊沿著圓到達$\color{black}{b}$,中間經過的距離的最小值,這裡定義兩個相鄰的紙牌之間距離$\color{black}{1}$,因此在$\color{black}{N=5}$時,也就是有五張紙牌時可以畫出上面那張圖,其中$\color{black}{dist(1,3)=min(2,3)=2}$、$\color{black}{dist(0,4)=min(1,4)=1}$,另外定義如果$\color{black}{a=b}$時,則$\color{black}{dist(a,b)=0}$,簡單來說距離的定義就是如果$\color{black}{a≥b}$,則$\color{black}{dist(a,b)=min(a-b,N-a+b)}$。

而現在雨昕在心裡選了其中一張牌,它的數字為$\color{black}{ans}$,阿祁要試著猜出雨昕的謎底,但是需要一些提示,所以阿祁每次可以選兩個數字$\color{black}{x}$、$\color{black}{y}$,雨昕會告訴阿祁$\color{black}{dist(x,ans)}$與$\color{black}{dist(y,ans)}$的大小關係,如果$\color{black}{dist(x,ans)}$比較小,雨昕會回答$\color{black}{x}$;反之如果$\color{black}{dist(y,ans)}$比較小,雨昕會回答$\color{black}{y}$,如果兩個$\color{black}{dist}$一樣他會說兩個一樣大。

阿祁現在要從$\color{black}{0、1、2、……、N-1}$裡找到雨昕的答案,但是他不會亂猜,要有把握才會作答,所以現在問你一件事,如果阿祁在完全不知道任何資訊下使用最聰明的方法玩,至少要先詢問幾次距離大小關係,才一定可以確定答案呢?

Input

本題有多筆測資,因此第一行會有一個正整數$\color{black}{T}$告訴你有幾筆測資。

接著有$\color{black}{T}$行代表$\color{black}{T}$筆測資,每個測資都只有一行一個數$\color{black}{N}$,代表牌有$\color{black}{N}$張。

測資範圍:

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

$\color{black}{2 ≤ N ≤ 10^{18}}$

Output

針對每個測資,輸出一個數代表答案(也就是查詢所需最小次數)。

Sample Input #1
8
2
3
4
5
6
7
8
9
Sample Output #1
1
1
2
2
2
2
2
3
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (30%): 1.0s , <1M
公開 測資點#1 (70%): 3.0s , <10M
Hint :

$\color{black}{N=2}$,阿祁可以第一次查詢0,1和答案的距離,回答比較小的那個就是解。

$\color{black}{N=3}$,阿祁第一次查詢0,1,如果回答接近0答案就是0,回答接近1答案就是1,若回答相同則為2

$\color{black}{N=4}$,阿祁第一次查詢0,1,如果回答接近0答案就是0、3其中一個,回答接近1答案就是1、2其中一個,這兩種case皆可以分別透過再一次的詢問0,3、1,2求解。

對於$\color{black}{30\%}$ 測資: $\color{black}{1 ≤ T ≤ 1000}$,$\color{black}{2 ≤ N ≤ 1000}$

對於$\color{black}{70\%}$ 測資: 同原題目限制

Tags:
出處:
Chi's Coding Problem [管理者:
Ststone1687 (使用C++的都邪教)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」