만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

숫자 할당

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

요약
1부터 13까지의 서로 다른 수를 a부터 m까지의 칸에 배정하여 A부터 H까지 주어진 합계를 모두 만족하는 방법의 수를 구합니다.
난이도

보통10점 중 5점

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

문제

위 그림과 같이 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이 채워져 있다. 1행의 모든 칸과 1열의 모든 칸에는 정수가 미리 채워져 있으며, 이 값들이 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까지의 수를 할당할 방법이 없다.

입력

입력은 표준입력을 사용한다. 정수 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