NP=P

시간 제한1초메모리 제한1024 MB

요약

K가 주어졌을 때, C(M, N mod (M+1)) mod K 값을 묻는 질의만으로 1부터 K까지의 M을 알아내는 데 필요한 최소 질의 횟수를 구하고, 그 횟수 안에 M을 실제로 찾는 인터랙티브 문제이다.

문제

이 문제는 인터랙티브 문제입니다.

동우와 세준이는 이항 계수 놀이를 만들었다.

이 놀이는 먼저 세준이가 양의 정수 $K$ 와 $K$ 이하의 양의 정수 $M$ 을 정한다. 그 후 세준이가 동우에게 $K$ 를 알려주면, 동우는 다음 질문을 최소로 하여 $M$ 을 맞춰야 한다.

동우가 세준이에게 정수 $N$ 을 질문하면, 세준이는 $\dbinom{M}{N\bmod{\left( M+1 \right)}}\bmod K$ *를 알려준다.

동우를 도와 주어진 $K$ 에 대해 최악의 경우에도 $M$ 을 맞출 수 있는 질문 횟수의 최솟값을 찾고, 실제로 $M$ 을 맞춰보자.

* $\binom{a}{b}$ 는 조합(combination)으로, $a$ 개의 공들 중 $b$ 개를 구분 없이 뽑는 경우의 수를 의미한다.

컴퓨터는 세준이, 유저는 동우로 생각하고 인터랙티브가 진행된다.

먼저 컴퓨터가 유저에게 $K(1\le K\le 10^6)$ 를 입력으로 준다.

유저는 주어진 $K$ 에서 $M$ 을 맞출 수 있는 질문 횟수의 최솟값 $Q$ 를 출력한다. 만약 $Q$ 가 잘못되었다면 컴퓨터는 즉시 틀렸습니다를 띄우고 프로그램을 종료한다.

이후 유저와 컴퓨터는 아래 과정을 $Q$ 번 반복한다.

$Q$ 번의 질의가 끝난 후, 유저는 예측한 $M$ 을 출력한다.

조건을 만족하지 않거나 잘못된 출력을 하는 경우, 컴퓨터는 틀렸습니다를 띄우고 프로그램을 종료한다.

유저는 출력 후 다른 출력 없이 프로그램을 종료해야 한다.

인터랙션 도중 컴퓨터에게 정상적인 출력이 전달되지 않았거나 덜 전달된 경우, flush를 하지 않은 경우, 혹은 정답 출력 후 프로그램이 종료되지 않는 경우 등의 상황에는 시간 초과 등의 결과를 받을 수 있다.