Wumpus 사냥

Hunt the Wumpus는 $10 \times 10$ 격자판에서 컴퓨터와 겨루는 게임이다. 게임을 시작하면 wumpus 네 마리가 격자판에 무작위로 놓인다. 두 마리가 같은 칸에 놓이지는 않는다. 플레이어는 wumpus를 모두 찾아 잡아야 한다. 칸은 두 자리 십진수 좌표를 입력해 추측한다. 추측한 칸에 wumpus가 있으면 게임이 그 사실을 알려 주고, 그 wumpus는 잡혀 격자판에서 사라진다. wumpus를 맞혔는지와 관계없이, 추측한 칸과 가장 가까운 남은 wumpus 사이의 맨해튼 거리가 알려진다. 플레이어는 이 거리를 이용해 wumpus의 위치를 좁혀 간다. 마지막 wumpus를 잡으면 게임이 끝난다.

이 문제에서는 게임의 컴퓨터 쪽 프로그램을 작성한다. 추측한 칸과 무작위로 생성된 wumpus 위치는 두 자리 수로 표현된다. 십의 자리 숫자가 $x$, 일의 자리 숫자가 $y$이며, 이는 점 $(x, y)$를 뜻한다.

게임을 결정적으로 만들기 위해 주어진 시드 $s$로 자체 의사 난수 생성기를 사용한다. 난수 하나는 먼저 $s \leftarrow s + \lfloor s/13 \rfloor + 15$를 계산한 뒤, $s$의 하위 두 자리를 반환해서 만든다. 처음 생성된 서로 다른 네 수가 wumpus의 위치가 된다. 시드가 132이면 첫 번째 수는 $132 + 10 + 15$의 하위 두 자리인 57이며, 이는 점 $(5, 7)$에 해당한다.

첫 줄에는 난수 생성기의 시드 $s$ ($10^4 \le s \le 10^6$)가 정수 하나로 주어진다. 나머지 각 줄에는 두 자리 수(앞자리 0 가능)가 하나씩 주어지며, 이는 플레이어가 추측한 격자판의 한 칸이다.

입력은 항상 올바른 형식이며 하나의 완전한 게임을 나타낸다. 마지막 추측은 항상 마지막 wumpus를 찾는다. 추측은 최대 250개이다.

각 추측에 대해 컴퓨터의 응답을 출력한다. 추측이 wumpus를 맞히면 You hit a wumpus!를 한 줄에 출력한다. 맞혔는지와 관계없이 잡히지 않은 wumpus가 남아 있으면, 가장 가까운 남은 wumpus까지의 맨해튼 거리를 출력한다. 두 점 $(x_1, y_1)$, $(x_2, y_2)$ 사이의 맨해튼 거리는 $|x_1 - x_2| + |y_1 - y_2|$이며, 항상 정수이다.

게임이 끝나면 모든 wumpus를 찾는 데 필요한 총 이동 횟수 $m$을 Your score is $m$ moves. 형식으로 한 줄에 출력한다.