22327번 - Divisor game 다국어언어 제한함수 구현

Alice and Bob invented a two-player game. At first, Alice chooses a positive integer k in the range from 1 to some fixed integer n. Then Bob asks questions of the form ‘Is k divisible by m?’, where m is a positive integer. Alice answers each such question with ‘yes’ or ‘no’. Bob wants to know what number Alice bears in mind by asking as few questions as possible. Your task is to write a program, which plays the game as Bob.

Let us denote by d( n) the minimal number of questions, which have to be asked to find k, regardless of what k Alice chooses (for given n). Your program’s answer for a test case will be considered correct, if k is correctly determined using no more than d( n) questions.

Your program must use a special library to play the game. The library consists of the files: alice.h and alice.c (for C/C++). The library provides the following functionality:

• int get_n() — Your program should call this function to initialize a game, before it calls any other function/procedure provided by the library. Function get_n returns n, the upper bound on the number that Alice has in mind. Number n satisfies the limitations 1 ≤ n ≤ 1 000 000 . Moreover, in 50 % of test cases n satisfies 1 ≤ n ≤ 10 000.
• int is_divisible_by(int m) — Your program may ask questions by calling this function. Function is_divisible_by returns 1 if the number k Alice has in mind is divisible by m. Otherwise it returns 0. The parameter m must satisfy 1 ≤ m ≤ n. Your program should ask as few questions as possible.
• void guess(int k) — To end the game your program should report the number k Alice has in mind, by calling the procedure guess(k). The parameter k should satisfy 1 ≤ k ≤ n. After calling this procedure your program will be terminated automatically.

If your program makes an illegal call, it will be terminated.

Your program should communicate only by means of the above functions and procedures. Your program must not read or write any files, it must not use standard input/output and it must not try to access any memory outside your program.

Below there is a sample interaction between a program and the library.

• alice.c
• alice.h