Boring Game

시간 제한4초메모리 제한2048 MB

요약
숨은 수 S를 찾는 문제로, K가 정해지지 않은 상태에서 K번째 질문까지는 정직하게, 그 뒤로는 뒤집어서 답하는 Bob에게 'x 이상인가?'만 물을 수 있다.
난이도

보통10점 중 7점

유형
이분 탐색, 게임 이론, 구현, 수학
정답자
아직 제출이 없습니다

문제

Alice and her little brother, Bob are playing a number guessing game.

Bob has selected a (hidden) integer SS.

Alice can ask questions about the hidden number, which are of the following form: "Is the hidden number at least xx?" Bob answers her questions with "Yes" or "No". Unfortunately, after K≥1K ≥ 1 questions, Bob gets bored of the game, and from then on, he will give false answers to all questions.

That is, Bob:

  • Answers "Yes" to the first KK questions if and only if x≤Sx ≤ S, and
  • After the KK-th question, he answers "Yes" if and only if S<xS < x.

Note that Bob always answers correctly to the first question and Alice does not know the value of KK.

Your task is to devise and implement a questioning strategy for Alice to identify the hidden number. Your score is based on the number of questions asked - the fewer questions, the better the score.

제한

  • 1≤T≤10001 ≤ T ≤ 1000
  • 1≤S≤10181 ≤ S ≤ 10^{18}
  • 1≤K≤1501 ≤ K ≤ 150

예제

이 문제는 공개된 예제가 없습니다.