골롬 케이지

골롬 눈금자(Golomb Ruler)는 모든 차이값(예: |a-b|)이 서로 다른 정수들의 집합이다. 아틀란티스 게임은 골롬 눈금자를 확장하여 합, 곱, 나눗셈의 결과까지 모두 양의 정수가 되도록 한다. 집합 $\{2, 8, 10, 11\}$은 덧셈, 곱셈, 나눗셈 조건도 만족하는 아틀란티스 골롬 눈금자이다. 예를 들어 이 집합의 2와 10은 +, -, *, /연산으로 각각 12, 8, 20, 5를 만든다. 이 집합의 다른 어떤 쌍도 같은 결과를 만들지 않는다.

$N \times N$ 퍼즐 격자가 케이지로 나뉘어 있고 각 케이지마다 결과값이 주어진다. 각 행과 각 열에 집합의 숫자가 정확히 한 번씩 들어가도록 숫자를 배치하라. 각 케이지는 덧셈, 뺄셈, 곱셈, 나눗셈 중 하나의 연산으로 그 케이지의 결과값이 되어야 한다. 연산 대상이 되는 수는 주어지지 않는다.

집합 $\{2, 8, 10, 11\}$ 기준의 퍼즐 예시

다음 풀이로 정리된다:

첫 줄에 격자 크기, 둘째 줄에 숫자 집합, 셋째 줄에 케이지 개수가 주어진다. 이후 케이지마다 한 줄씩 결과값, 첫 번째 칸의 위치, 두 번째 칸의 위치 순서로 주어진다. 위치는 행, 열 순서이며 가장 왼쪽 위 칸은 (0, 0)이다.

Grid Size
Number Set
Number of cages
Result, grid location 1, grid location 2 (케이지마다 반복)

격자 크기는 4(4x4) 또는 6(6x6)이다. 숫자 집합은 오름차순이며 1보다 크고 100보다 작은 양의 정수로만 이루어진다. 케이지의 칸은 항상 2개다. 격자 크기가 0이면 입력의 끝이다.

격자 전체를 출력한다. 각 숫자는 두 자리 형식으로 쓰고, 숫자 사이에는 공백 한 칸을 둔다. 해 격자 사이에는 빈 줄을 하나 둔다.