100명의 플레이어가 10000문제로 이루어진 퀴즈 토너먼트에서 경쟁하고 있으며, 플레이어 번호는 1부터 100까지이다. 플레이어 i는 실력 값 S_i를 가지고, 문제 j는 난이도 값 Q_j를 가진다. 각 실력 값과 각 난이도 값은 구간 [-3.00, 3.00]에서 균등 무작위로 선택되며, 서로 독립적이다. 예를 들어 어떤 플레이어의 실력 값이 2.47853일 수도 있고, 어떤 문제의 난이도 값이 -1.4172일 수도 있다.

플레이어 i가 문제 j를 풀 때, 정답을 맞힐 확률은 f(S_i - Q_j)이다. 여기서 f는 시그모이드 함수이다: f(x) = \frac{1}{1 + e^{-x}} 여기서 e는 오일러 수 (대략 2.718...)라는 수학 상수이다. 0 \lt f(x) \lt 1이 모든 x에 대해 성립하므로, f(S_i - Q_j)는 항상 올바른 확률 값이다. 각 정답 시도는 다른 모든 선택과 독립적으로 무작위로 이루어진다.

단 한 가지 예외가 있다: 플레이어 중 정확히 1명은 부정행위자(cheater)이다! 부정행위자는 모든 플레이어 중에서 균등 무작위로 선택되며, 다른 모든 선택과 독립적이다. 부정행위자는 다음과 같이 행동한다. 각 문제에 답하기 전에 공정한 동전을 던진다. 앞면이 나오면 부정행위를 하지 않고 규칙이 정상적으로 적용된다. 뒷면이 나오면 몰래 인터넷에서 답을 찾아 정답으로 답한다. 형식적으로, 부정행위자는 각 문제마다 확률 0.5로 부정행위를 할지 말지를 무작위로 결정하며, 이 결정은 다른 모든 선택과 독립적이다.

토너먼트의 결과로 주어지는 정보는, 각 플레이어에 대해 각 문제를 맞혔는지 틀렸는지(정오답)만이다. 위의 일반적인 설명을 제외하면, 당신은 플레이어들의 실력 값이나 문제들의 난이도 값에 대해 어떤 정보도 알지 못한다.

당신은 테스트 케이스의 적어도 \mathbf{P}%에서 부정행위자를 맞혀야 한다. 즉, \mathbf{T}개의 케이스 중 적어도 \mathbf{P} \cdot \mathbf{T} / 100개는 성공해야 한다.

#10394 upload 1 done 1 how_to_reg 1

Cheating Detection timer 60s memory 1024MB

#10394

Cheating Detection 60s 1024MB