Hotter Colder Interactive 컴파일 명령

수찬이는 승현이와 Hotter Colder라는 게임을 하고 있습니다. 승현이는 $1$ 이상 $N$ 이하의 정수를 하나 가지고 있고, 수찬이는 이를 추측합니다.

수찬이의 추측은 $1$ 이상 $N$ 이하의 정수를 하나 승현이에게 말하는 것입니다. 이 때 승현이는 hotter, colder 또는 same이라고 답합니다.

수찬이의 첫 번째 추측에 대해서 승현이는 항상 same이라고 답합니다. 나머지 추측들에 대해서는 다음과 같이 답합니다.

• 만약 수찬이의 이번 추측이 저번 추측보다 승현이의 수에 더 가까우면, 승현이는 hotter라고 답합니다.
• 만약 수찬이의 이번 추측이 저번 추측보다 승현이의 수에 더 멀면, 승현이는 colder라고 답합니다.
• 만약 수찬이의 이번 추측이 저번 추측보다 승현이의 수에 더 가깝거나 더 멀지 않으면, 승현이는 same이라고 답합니다.

문제

당신은 수찬이와 대신해 승현이와 게임을 하는 함수 HC(N)을 구현해야 합니다. 함수 HC(N)은 함수 Guess(G)를 호출하여 승현이의 수를 알아내야 합니다. 여기서 $G$는 $1$ 이상 $N$ 이하의 정수입니다. 함수 Guess(G)는 승현이의 답이 hotter면 $1$, colder면 $-1$, same이면 $0$을 반환합니다. 함수 HC(N)은 반드시 승현이의 수를 반환해야 합니다.

예시

$N = 5$이고, 승현이의 정수가 $2$라고 가정합니다.

여기서는 $5$번의 추측으로 답을 찾았습니다. 당신은 더 적은 추측으로 답을 찾을 수 있습니다.

부분문제

부분문제 1 [25점]

함수 HC(N)은 함수 Guess(G)를 최대 $500$번 호출 할 수 있습니다. 채점기는 $1$ 이상 $500$ 이하의 정수 $N$에 대하여 함수 HC(N)을 최대 $125,250$번 호출 할 것입니다.

부분문제 2 [25점]

함수 HC(N)은 함수 Guess(G)를 최대 $18$번 호출 할 수 있습니다. 채점기는 $1$ 이상 $500$ 이하의 정수 $N$에 대하여 함수 HC(N)을 최대 $125,250$번 호출 할 것입니다.

부분문제 3 [25점]

함수 HC(N)은 함수 Guess(G)를 최대 $16$번 호출 할 수 있습니다. 채점기는 $1$ 이상 $500$ 이하의 정수 $N$에 대하여 함수 HC(N)을 최대 $125,250$번 호출 할 것입니다.

부분문제 4 [최대 25점]

$W$를 $2^{W} \le 3N$을 만족하는 최대의 정수라고 합시다. 이 부분문제의 점수는 다음과 같이 주어집니다.

• 만약 함수 HC(N)이 함수 Guess(G)를 $2 W$번 이상으로 호출했을 경우 0점입니다.
• $\alpha$를 $0 < \alpha < 1$이고 함수 HC(N)이 Guess(G)를 $( 2 W - \alpha W )$번 이하로 호출함을 만족하는 최대의 실수라고 했을 때, $25 \alpha$점입니다.
• 함수 HC(N)이 함수 Guess(G)를 $W$번 이하로 호출했을 경우 25점입니다.

채점기는 $1$ 이상 $500,000,000$ 이하의 정수 $N$에 대하여 함수 HC(N)을 최대 $1,000,000$번 호출 할 것입니다.

함수 HC(N)이 호출 될 때 사용하는 모든 변수들을 초기화했는지 확인하세요.

구현 세부 사항

• 구현해야 하는 파일 : hottercolder.c 또는 hottercolder.cpp
• include해야 하는 파일 : grader.h
• 예제 채점기 : grader.c 또는 grader.cpp
• 예제 입력 : grader.in.1 또는 grader.in.2
• 채점기는 $N$과 승현이의 정수를 계속 입력으로 받습니다.
• 만약 당신의 프로그램이 부분문제 1에 해당하는 입력들에 대하여 올바르게 동작했다면, 채점기는 "OK 1"을 출력합니다.
• 만약 당신의 프로그램이 부분문제 2에 해당하는 입력들에 대하여 올바르게 동작했다면, 채점기는 "OK 2"를 출력합니다.
• 만약 당신의 프로그램이 부분문제 3에 해당하는 입력들에 대하여 올바르게 동작했다면, 채점기는 "OK 3"을 출력합니다.
• 만약 당신의 프로그램이 부분문제 4에 해당하는 입력들에 대하여 올바르게 동작했다면, 채점기는 "OK 4 alpha $\alpha$"를 출력합니다.