라피키의 시험

내가 헷갈린 게 아니라 네가 헷갈린 거다.

라피키

이것은 인터랙티브 문제이다.

새끼 사자는 모두 일련의 시험을 통과해야 사자왕이 될 수 있다. 심바의 스승 라피키는 문제를 분명하게 말하지 않기로 유명하므로, 직접 유도 질문을 던져야 한다. 목표는 다항식 해시의 base와 modulus를 알아내는 것이다.

라피키는 심바에게 초기 데이터를 전혀 주지 않는다. 대신 심바가 고른 문자열의 해시값을 여러 번 알려 줄 용의가 있다.

라피키의 해시는 다음 식으로 계산한다. $(s_0 \cdot x^0 + s_1 \cdot x^1 + s_2 \cdot x^2 + \dots + s_n \cdot x^n) \bmod p$. 여기서 $s_i$는 문자열의 $i$번째 문자가 영어 알파벳에서 몇 번째인지를 나타내는 수이며, 문자는 0번부터 번호를 매긴다. $x$와 $p$는 자연수이고, 각각 해시의 base와 modulus라고 부른다. $\bmod$는 나눗셈의 나머지이다.

프로그램이 올바르게 동작하려면 데이터를 출력할 때마다 다음 작업을 해야 한다.

• Pascal: flush(output);
• C/C++: fflush(stdout);
• Java: System.out.flush();
• Python: sys.stdout.flush();

또한 출력한 줄마다 줄바꿈 문자를 붙여야 한다.