농부 존의 소들은 농장을 탈출해서 장난을 칩니다. 탈출하는 것을 방지하기 위해 존은 조합 자물쇠를 샀습니다. 여러분도 알다시피 그의 소들은 매우 영특해서 존은 많은 조합들을 시도해도 쉽게 열리지 않도록 하길 원합니다. 자물쇠는 1부터 N까지 숫자들이 적힌 세 개의 다이얼을 가지고 있고, 1과 N이 인접한 원형 다이얼입니다.
자물쇠는 여는 두 가지 조합이 있는데, 하나는 농부 존이 설정한 조합과, 자물쇠 제작자가 설정한 "마스터 조합"입니다. 하지만 자물쇠는 작은 오차가 있어서, 각 다이얼이 농부 존의 조합들과 모두 거리가 2 이내이거나, 마스터 조합과의 거리가 모두 2 이내에 있는 조합들도 열리게 됩니다.
예를 들어, 농부 존의 조합이 (1,2,3)이고 "마스터 조합"이 (4,5,6)이면, 이 자물쇠는 (1,N,5)의 조합 (농부 존의 조합에 충분히 근접해있으므로) 또는 (2,4,8) ("마스터 조합“에 충분히 근접해있으므로)에 열릴 것입니다. (1,5,6)은 어느 하나의 단일 조합에도 근접하지 않으므로 열리지 않는단 것을 주의하세요.
농부 존의 조합과 마스터의 조합이 주어질 때, 자물쇠가 열리는 조합의 수를 계산하세요. 위의 문제에 의하면, (1,2,3)과 (3,2,1)은 서로 다른 조합입니다.
** (1,2,3)과 (1,N,5)는 각 다이얼의 숫자가 (0,2,2) 만큼 떨어져있기 때문에 열리고, (1,5,6)은 (1,2,3)과는 (0,3,3)만큼 떨어져있고 (4,5,6)과는 (3,0,0)만큼 떨어져있기 때문에 열리지 않습니다.
Knowing that his cows are quite clever, Farmer John wants to make sure they cannot easily open the lock by simply trying many different combinations. The lock has three dials, each numbered 1..N (1 <= N <= 100), where 1 and N are adjacent since the dials are circular. There are two combinations that open the lock, one set by Farmer John, and also a "master" combination set by the lock maker. The lock has a small tolerance for error, however, so it will open even if the numbers on the dials are each within at most 2 positions of a valid combination. For example, if Farmer John's combination is (1,2,3) and the master combination is (4,5,6), the lock will open if its dials are set to (1,N,5) (since this is close enough to Farmer John's combination) or to (2,4,8) (since this is close enough to the master combination). Note that (1,5,6) would not open the lock, since it is not close enough to any one single combination.
Given Farmer John's combination and the master combination, please determine the number of distinct settings for the dials that will open the lock. Order matters, so the setting (1,2,3) is distinct from (3,2,1).
50 1 2 3 5 6 7
출처:usaco/2013/bronze 번역:Fate