农夫约翰的奶牛们总是偷偷的逃出他的农场，去外面为非作歹。
农夫约翰为了防止它们私自逃离农场，购买了一个密码锁，以此阻止奶牛们打开农场大门。
约翰知道他的奶牛们都非常聪明，因此他想要确保它们不能通过简单的尝试一些密码组合，就轻易的将锁打开。
锁具上有三个密码拨盘，每个拨盘上的数字为 $1$ … $N$，其中 $1$ 和 $N$ 相邻（因为拨盘是圆形的）。
一共有两种可以打开密码锁的数字组合，一组是约翰设置的密码组合，一组是制造商设置的密码组合。
这种锁具有一定的容错性，只要三个表盘上的数字与任意一组正确密码组合的对应位置数字相距两个位置以内，锁均会打开。
例如，假设约翰设置的密码组合是 $\left( 1, 2 , 3 \right)$，制造商设置的密码组合是 $\left( 4, 5, 6 \right)$。
此时我们输入组合 $\left( 1, 3, 5 \right)$ 就可以将锁打开，因为这与约翰设置的密码接近，输入组合 $\left( 2, 4, 8 \right)$ 也可以将锁打开，因为这与制造商设置的密码接近。
但是，如果我们输入组合 $\left( 1, 5, 6 \right)$ 就不能将锁打开，因为它和两个密码都不接近。
现在给定你两个设置好的密码，请你判断一共有多少种密码组合可以将锁打开。
注意，密码组合是有序的，因此 $\left( 1, 2, 3 \right)$ 和 $\left( 3, 2, 1 \right)$ 是两种不同的组合。
输入格式
第一行包含整数 $N$。
第二行包含三个整数，表示约翰设置的密码组合。
第三行包含三个整数，表示制造商设置的密码组合。
输出格式
输出一个整数，表示可以打开锁的密码组合数量。
数据范围
$1 \leq N \leq 100$
输入样例
50
1 2 3
5 6 7
输出样例
249
使用数组 $a$ 表示 Farmer John 设置的密码组合，数组 $b$ 表示制造商设置的密码组合，数组 $d$ 存储在密码锁上两点的位置信息（$d$ 最开始表示两个点的下标之差）。
考虑如下两种情况：
I. $N \leq 5$
在密码锁上任意取两点，当 $N \leq 5$ 时，这两点的距离一定小于或等于 $2$。因此，对于任意一种正确密码组合，密码锁上的任意密码组合一定合法。
因此，正确密码组合个数为 $N^{3}$。
res += pow(n, 3);
II. $N \geq 6$
正确的密码组合个数可以使用容斥原理计算，即符合 Farmer John 的密码组合个数与符合制造商的密码组合个数减去符合两者的密码组合个数。
因为 $N \geq 6$，所以对于密码锁上的任意一个点，与其间隔 $2$ 个位置以内的 $4$ 个点一定是位置互异的 $4$ 个点。符合 Farmer John 的密码组合个数与符合制造商的密码组合个数因此为 $2 \left( N^{3} \right)$。
res += 2 * pow(5, 3);
由于两个点的距离过近，这两个点的周围 $4$ 个点可能重合。这些重合的点是导致某些密码组合既符合 Farmer John 设置的密码，也符合制造商设置的密码的原因。
首先需要计算两个点在密码锁上的距离。利用破环成链的思想，可以使用如下公式计算两个点的距离（比较 $a$ 和 $b$ 的距离与 $b$ 和 $a + n$ 的距离）：
1, ..., a ..., b, ... n ||| 1 + n, ..., a + n, ..., b + n, ... 2n
- - ----- -----
$$d \left[ i \right] = \min \left( \lvert a \left[ i \right] - b \left[ i \right] \rvert, \lvert \min \left( a \left[ i \right], b \left[ i \right] \right) - \max \left( a \left[ i \right], b \left[ i \right] \right) + n \rvert \right)$$
for (int i = 1; i <= 3; i++)
{
cin >> a[i];
}
for (int i = 1; i <= 3; i++)
{
cin >> b[i];
d[i] = min(abs(a[i] - b[i]), abs(min(a[i], b[i]) - max(a[i], b[i]) + n));
}
在如上述的结构中，假设 $a \left[ i \right] \leq b \left[ i \right]$。考虑：
-
$a$ 右侧相邻点和 $b$ 左侧没有相邻点。为保证 $a$ 和 $b$ 在这一侧的没有相邻点重合，它们中间的点数必须大于或等于 $4$，即 $d \left[ i \right] \geq 4$，
-
$a$ 右侧相邻点和 $b$ 左侧有相邻点。
-
为保证 $a$ 和 $b$ 在这一侧的相邻点有重合，它们中间的点数必须小于 $4$，即 $d \left[ i \right] \leq 4$，中间的重合点数为 $a \left[ i \right] + 2 - \left( b \left[ i \right] - 2 \right) + 1 = 5 - \left( b \left[ i \right] - a \left[ i \right] \right)$ = $5 - d \left[ i \right]$。
-
$a$ 左侧相邻点和 $b$ 右侧相邻点。虽然 $N \geq 6$，但是这两侧的点可能重合。考虑极限情况，假设点 $a \left[ i \right]$ 的坐标为 $3$（此时，点 $a \left[ i \right]$ 容错的 $5$ 个点的坐标分别为 $1$、$2$、$3$、$4$、$5$），为保证两侧的点不重合，点 $b \left[ i \right]$ 容错的最右侧点的坐标应为 $b \left[ i \right] + 2 = a \left[ i \right] + d \left[ i \right] + 2 = 5 + d \left[ i \right]$。因此，
-
当 $n \geq 5 + d \left[ i \right]$。此时，$a$ 左侧相邻点和 $b$ 右侧相邻点没有重合。总重合点的数量为 $5 - d \left[ i \right]$。
-
当 $n < 5 + d \left[ i \right]$。此时 $a$ 左侧相邻点和 $b$ 右侧相邻点有重合，且重合数量为 $b \left[ i \right] + 2 - n$（即在破环成链中第二个链的部分。这部分其实就是第一个链的开头）。总重合数量为 $5 - d \left[ i \right] + b \left[ i \right] + 2- n = 7 - d \left[ i \right] + a \left[ i \right] - d \left[ i \right] - n = 7 + a \left[ i \right] - n = 7 + 3 - n = 10 - n$。
-
-
for (int i = 1; i <= 3; i++)
{
if (d[i] <= 4)
{
if (n <= d[i] + 4)
{
d[i] = 10 - n;
}
else
{
d[i] = 5 - d[i];
}
}
else
{
d[i] = 0;
}
}
res -= (d[1] * d[2] * d[3]);
C++：
#include <iostream>
#include <cmath>
using namespace std;
const int N = 4;
int n;
int a[N], b[N], d[N];
int res;
int main()
{
cin >> n;
for (int i = 1; i <= 3; i++)
{
cin >> a[i];
}
for (int i = 1; i <= 3; i++)
{
cin >> b[i];
d[i] = min(abs(a[i] - b[i]), abs(min(a[i], b[i]) - max(a[i], b[i]) + n));
}
if (n >= 6)
{
res += 2 * pow(5, 3);
for (int i = 1; i <= 3; i++)
{
if (d[i] <= 4)
{
if (n <= d[i] + 4)
{
d[i] = 10 - n;
}
else
{
d[i] = 5 - d[i];
}
}
else
{
d[i] = 0;
}
}
res -= (d[1] * d[2] * d[3]);
}
else
{
res += pow(n, 3);
}
cout << res << endl;
return 0;
}
