Trong một trong trò chơi đoán số, hệ thống sẽ tạo ngẫu nhiên một số nguyên từ 1 đến n. Việc của bạn cần đoán ra số đó là số nào:

• Nếu bạn đoán trúng thì bạn chiến thắng, trò chơi kết thúc.
• Nếu bạn đoán lớn hơn thì hệ thống sẽ thông báo là: "high" và yêu cầu bạn đoán số khác.
• Nếu bạn đoán bé hơn thì hệ thống sẽ thông báo là: "low" và yêu cầu bạn đoán số khác.

Hải là một người kém may mắn. Cho số nguyên dương n (1 ≤ n ≤ 1015) hãy tìm và đưa ra số lần đoán ít nhất để Hải chắc chắn sẽ đoán trúng số của hệ thống.

Biết rằng Hải sẽ chọn cách đoán thông minh nhất có thể.

Ví dụ:

• Test mẫu 1:
   

  Input	Output
  3	2

  
  Với n = 3, thì gameGuessNumber(n) = 2.
  Giải thích: Đầu tiên Hải số đoán số 2
  • Nếu hệ thống báo chính xác thì Hải đã chiến thắng với chỉ 1 lần đoán.
  • Nếu Hệ thống thông báo "hight" thì Hải chắc chắn số của hệ thống là 1 nên Hải sẽ đoán 1 và giành chiến thắng với 2 lượt đoán.
  • Nếu Hệ thống thông báo "low" thì Hải chắc chắn số của hệ thống là 3 nên Hải sẽ đoán 3 và giành chiến thắng với 2 lượt đoán.
     
• Test mẫu 2:
   

  Input	Output
  5	3

  
  Với n = 5, thì gameGuessNumber(n) = 3.

Hướng dẫn bài tập.

Cách đoạn thông minh nhất là chúng ta sẽ đoán phần tử ở giữa trong đoạn từ 1 đến n, do Hải kém may mắn nên phần tử cần đoán sẽ nhỏ hoặc lớn hơn phần tử cần đoán, Số phần tử mà Hải phải đoán trong lần tiếp theo là n-(n+1)/2, đến khi chỉ còn 1 phần tử thì Hải chắc chắn sẽ đoán trúng.

int gameGuessNumber(long long n)
{
    if (n==1) return 1;
	return 1 + gameGuessNumber(n-(n+1)/2);
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

using namespace std;

int gameGuessNumber(long long n)
{
    if (n==1) return 1;
	return 1 + gameGuessNumber(n-(n+1)/2);
}
int main(){
	long long n;
	cin >> n;
	cout << gameGuessNumber(n);
	return 0;
}