숫자 할당

시간 제한0.1초메모리 제한2048 MB

요약
격자의 여덟 합이 주어질 때, 남은 칸에 1부터 13을 넣어 모든 합을 만족시키는 경우의 수를 센다.
난이도

보통10점 중 6점

유형
백트래킹, 완전 탐색, 재귀
정답자
아직 제출이 없습니다

문제

위 그림과 같이 5×55 \times 5 크기의 총 2525칸으로 이루어진 격자판이 주어져 있다. 편의상 맨 왼쪽 위칸의 좌표를 (1,1)(1,1)이라 하고 맨 오른쪽 아래 칸의 좌표를 (5,5)(5,5)라 하자. 초기에 (1,1)(1,1), (4,5)(4,5), (5,4)(5,4), (5,5)(5,5)에는 00이 채워져 있고, 11행의 모든 칸과 11열의 모든 칸은 미리 어떤 숫자(정수)들이 채워져 있다. 즉, AA부터 HH까지는 미리 채워진 숫자들이다. 이제 나머지 빈 칸들에 11부터 1313까지의 서로 다른 수들을 채워야한다. 즉, aa부터 mm까지는 11부터 1313까지의 서로 다른 숫자이다. 이때, 각 숫자들 사이에는 다음과 같은 규칙이 성립해야 한다.

  • A=a+e+i+lA = a + e + i + l
  • B=b+f+j+mB = b + f + j + m
  • C=c+g+kC = c + g + k
  • D=d+hD = d + h
  • E=a+b+c+dE = a + b + c + d
  • F=e+f+g+hF = e + f + g + h
  • G=i+j+kG = i + j + k
  • H=l+mH = l + m

즉, (1,1)(1,1)을 제외하고, 첫 번째 행의 각 칸에 있는 수들은 같은 열에 있는 수들의 합이며, 첫 번째 열의 각 칸에 있는 수들은 같은 행에 있는 수들의 합이다.

예를 들어, AA부터 HH까지의 숫자가 오른쪽 그림과 같이 주어졌다고 하자. 만약 aa부터 mm까지의 숫자를 그림과 같이 할당하면 위의 규칙이 만족된다. 하지만 만약 AA부터 HH까지의 숫자가 3,22,27,9,16,34,27,143, 22, 27, 9, 16, 34, 27, 14로 주어졌다면 위의 규칙을 만족하도록 aa부터 mm까지에 할당할 수 있는 방법이 없다.

AA부터 HH까지 88개의 숫자가 주어졌을 때, 위의 규칙이 만족되도록 11부터 1313까지의 서로 다른 숫자를 aa부터 mm까지에 할당하는 모든 경우의 수를 출력하는 프로그램을 작성하시오.

입력

입력은 표준입력을 사용한다. 정수 A,B,C,D,E,F,G,HA, B, C, D, E, F, G, H의 값이 한 줄에 차례로 주어진다. 각 정수는 33이상 4646이하이다.

출력

출력은 표준출력을 사용한다. 11부터 1313까지의 서로 다른 1313개의 정수를 aa부터 mm까지에 할당할 수 있는 모든 경우의 수를 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    33 22 27 9 16 34 27 14
    
    예상 출력
    126
    
  2. 예제 2

    입력
    3 22 27 9 16 34 27 14
    
    예상 출력
    0