题目描述
农夫约翰的奶牛们总是偷偷的逃出他的农场,去外面为非作歹。
农夫约翰为了防止它们私自逃离农场,购买了一个密码锁,以此阻止奶牛们打开农场大门。
约翰知道他的奶牛们都非常聪明,因此他想要确保它们不能通过简单的尝试一些密码组合,就轻易的将锁打开。
锁具上有三个密码拨盘,每个拨盘上的数字为 1…N,其中 1 和 N 相邻(因为拨盘是圆形的)。
一共有两种可以打开密码锁的数字组合,一组是约翰设置的密码组合,一组是制造商设置的密码组合。
这种锁具有一定的容错性,只要三个表盘上的数字与任意一组正确密码组合的对应位置数字相距两个位置以内,锁均会打开。
例如,假设约翰设置的密码组合是 (1,2,3),制造商设置的密码组合是 (4,5,6)。
此时我们输入组合 (1,3,5) 就可以将锁打开,因为这与约翰设置的密码接近,输入组合 (2,4,8) 也可以将锁打开,因为这与制造商设置的密码接近。
但是,如果我们输入组合 (1,5,6) 就不能将锁打开,因为它和两个密码都不接近。
现在给定你两个设置好的密码,请你判断一共有多少种密码组合可以将锁打开。
注意,密码组合是有序的,因此 (1,2,3) 和 (3,2,1) 是两种不同的组合。
输入格式
第一行包含整数 N。
第二行包含三个整数,表示约翰设置的密码组合。
第三行包含三个整数,表示制造商设置的密码组合。
输出格式
输出一个整数,表示可以打开锁的密码组合数量。
数据范围
1≤N≤100
输入样例:
50
1 2 3
5 6 7
输出样例:
249
算法1
因为n≤100,直接枚举所有可能的组合的复杂度是10的6次方,在可接受范围内。
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int a[3], b[3], c[3];
bool check()
{
bool st1 = true;bool st2 = true;
for (int i = 0; i < 3; ++i)
{
int d1 = min(abs(a[i] - c[i]), n - abs(a[i] - c[i]));
if (d1 > 2) st1 = false;
int d2 = min(abs(b[i] - c[i]), n - abs(b[i] - c[i]));
if (d2 > 2) st2 = false;
}
return st1 || st2;
}
int main()
{
cin >> n;
for (int i = 0; i < 3; ++i) cin >> a[i];
for (int i = 0; i < 3; ++i) cin >> b[i];
int cnt = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
for (int k = 1; k <= n; ++k)
{
c[0] = i, c[1] = j, c[2] = k;
if (check()) cnt ++;
}
cout << cnt << endl;
return 0;
}
算法2
闫总的方法,用数学的方法,算出密码A的组合、密码B的组合、A与B的交集,然后用容斥原理求出密码组合数量(A + B - A ∩ B),时间复杂度是O(1),复杂度和n无关,牛X啊!
C++代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3;
int n;
int a[N], b[N];
int both()
{
if (n < 5) return n * n * n;
int res = 1;
for (int i = 0; i < 3; ++i)
{
int d = min(abs(a[i] - b[i]), n - abs(a[i] - b[i]));
// res *= min(n, max(0, 5 - d));
res *= max(0, 5 - d);
}
return res;
}
int single()
{
int res = 1;
for (int i = 0; i < 3; ++i) res *= min(n, 5);
return res;
}
int main()
{
cin >> n;
for (int i = 0; i < 3; ++i) cin >> a[i];
for (int i = 0; i < 3; ++i) cin >> b[i];
cout << single() + single() - both() << endl;
return 0;
}
算法2有点小问题,6 1 1 1 4 4 4时,这里由于是首尾相连的,重叠的区间应该是n-2