小 $Y$ 有一把五个拨圈的密码锁。
如图所示,每个拨圈上是从 $0$ 到 $9$ 的数字。
每个拨圈都是从 $0$ 到 $9$ 的循环,即 $9$ 拨动一个位置后可以变成 $0$ 或 $8$,
因为校园里比较安全,小 $Y$ 采用的锁车方式是:
从正确密码开始,随机转动密码锁仅一次;每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。
当小 $Y$ 选择同时转动两个相邻拨圈时,两个拨圈转动的幅度相同,即小 $Y$ 可以将密码锁从 0 0 1 1 5
转成 1 1 1 1 5
,但不会转成 1 2 1 1 5
。
时间久了,小 $Y$ 也担心这么锁车的安全性,所以小 $Y$ 记下了自己锁车后密码锁的 $n$ 个状态,注意这 $n$ 个状态都不是正确密码。
为了检验这么锁车的安全性,小 $Y$ 有多少种可能的正确密码,使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 $n$ 个状态。
输入格式
输入的第一行包含一个正整数 $n$,表示锁车后密码锁的状态数。
接下来 $n$ 行每行包含五个整数,表示一个密码锁的状态。
输出格式
输出一行包含一个整数,表示密码锁的这 $n$ 个状态按照给定的锁车方式能对应多少种正确密码。
数据范围
对于所有测试数据有:$1 ≤ n ≤ 8$。
特殊性质 $A$:保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 $n$ 个状态。
输入样例:
1
0 0 1 1 5
输出样例:
81
样例解释
一共有 $81$ 种可能的方案。
其中转动一个拨圈的方案有 $45$ 种,转动两个拨圈的方案有 $36$ 种。
算法1
(暴力枚举) $O(n^2)$
暴力枚举所有可能的状态,并存在 $f_{a,b,c,d,e}$ 中。
遍历所有 $a,b,c,d,e$($0 \sim 9$),如果 $f_{a,b,c,d,e}$ 为 $n$ 时,$ans$ 加一。
输出 $ans$。
需要注意最终答案必须从所有方案都可以推得。
$f_{a,b,c,d,e}$ 为 $n$ 就是体现了这个性质。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 15;
int n;
int a[N];
int f[N][N][N][N][N];
int main(){
scanf("%d",&n);
int t = n;
while(t --){
int a,b,c,d,e;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
for(int i = 1;i <= 9;i ++){
f[(a + i) % 10][b][c][d][e] ++; // 转动一个
f[a][(b + i) % 10][c][d][e] ++;
f[a][b][(c + i) % 10][d][e] ++;
f[a][b][c][(d + i) % 10][e] ++;
f[a][b][c][d][(e + i) % 10] ++;
f[(a + i) % 10][(b + i) % 10][c][d][e] ++; // 转动两个
f[a][(b + i) % 10][(c + i) % 10][d][e] ++;
f[a][b][(c + i) % 10][(d + i) % 10][e] ++;
f[a][b][c][(d + i) % 10][(e + i) % 10] ++;
}
}
int ans = 0;
for(int a = 0;a <= 9;a ++){ // 计算
for(int b = 0;b <= 9;b ++){
for(int c = 0;c <= 9;c ++){
for(int d = 0;d <= 9;d ++){
for(int e = 0;e <= 9;e ++){
if(f[a][b][c][d][e] == n) ans ++;
}
}
}
}
}
printf("%d\n",ans);
return 0;
}