Havannah

Havannah는 Christian Freeling가 만든 추상 전략 보드게임이다. Havannah는 각 변에 S개의 육각형이 있는 육각형 보드에서 진행하는 게임이다. 각 육각형에는 수평인 변이 둘, 기울어진 변이 넷 있다. 육각형은 정수 값의 쌍으로 식별된다. 보드 아래쪽 모서리의 육각형은 (1, 1)이다. (x, y)에서 두 시 방향으로 인접한 육각형은 (x, y+1)이다. (x, y)에서 열 시 방향으로 인접한 육각형은 (x + 1, y)이다. 다음은 S = 5인 보드의 예시이다:

Havannah 게임에서 각 육각형에는 최대 하나의 돌만 놓을 수 있다. 보드에 한 번 놓인 돌은 절대 제거하거나 옮기지 않는다. 게임의 목표는 돌로 다음 세 종류 중 하나에 해당하는 연결된 돌의 집합을 만드는 것이다. 승리 구조는 다음과 같다:

• 비어 있는 육각형을 하나 이상 둘러싸는 고리. 즉, 내부 육각형 중 적어도 하나는 비어 있어야 한다. 더 구체적으로는, 돌이 놓인 육각형들에 의해 보드의 가장 바깥 경계와 분리된 빈 육각형이 존재한다. 이 규칙은 공식 Havannah 게임과 다르다는 점에 유의하라.

• 보드의 임의의 두 모서리를 연결하는 다리.

• 보드의 여섯 변 중 임의의 세 변을 연결하는 갈래. 모서리는 인접한 어느 변의 일부로도 세지 않는다.

이 그림은 승리 구조의 예시를 보여 준다:

프로그램은 한 플레이어의 일련의 수가 승리 구조를 만드는지 판정해야 한다. 승리 구조를 만든다면, 그 구조의 이름과 이를 완성한 수의 번호를 출력해야 한다. 한 수가 여러 고리를 완성하거나, 둘보다 많은 모서리를 연결하거나, 셋보다 많은 변을 연결하더라도 해당 구조는 각각 여전히 고리, 다리 또는 갈래로 간주한다. 그러나 한 수가 서로 다른 종류의 구조를 동시에 완성한다면, 프로그램은 그 모든 구조의 이름을 출력해야 한다. 첫 번째 승리 수에만 관심이 있으므로, 승리 수 뒤의 모든 수는 무시한다. 수열의 모든 수를 둔 뒤에도 보드에 승리 구조가 없다면 프로그램은 none를 출력해야 한다.

제한

메모리 제한: 1GB.

테스트 세트 1 (Visible Verdict)

시간 제한: 30초. 1 ≤ T ≤ 200 2 ≤ S ≤ 50 0 ≤ M ≤ 100

L테스트 세트 2 (Hidden Verdict

시간 제한: 60초. 1 ≤ T ≤ 20 2 ≤ S ≤ 3000 0 ≤ M ≤ 10000

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 S와 M이 주어진다. 이들은 각각 보드의 각 변에 있는 육각형의 수와 수열에 포함된 수의 개수이다. 이어지는 M개의 줄에는 수열의 수가 순서대로 주어지며, 각 줄에는 공백으로 구분된 육각형 식별자 쌍 (x, y)가 주어진다. 수열의 모든 수는 크기가 S인 보드 위에 놓인다. 각 테스트 케이스에서 보드는 처음에 비어 있으며, 같은 수가 반복되지 않는다.

각 테스트 케이스마다 "Case #n: " 뒤에 다음 중 하나가 오는 한 줄을 출력한다:

• none

• bridge in move k

• fork in move k

• ring in move k

• bridge-fork in move k

• bridge-ring in move k

• fork-ring in move k

• bridge-fork-ring in move k

테스트 케이스 번호는 1부터 시작한다. 수의 번호는 1부터 시작한다.

Havannah는 Christian Freeling와 MindSports가 만들었다. MindSports와 Christian Freeling는 Google Code Jam를 지지하지 않으며 아무런 관련도 없다.