P9752 [CSP-S 2023] 密码锁

[CSP-S 2023] 密码锁

题目描述

小 Y 有一把五个拨圈的密码锁。如图所示，每个拨圈上是从 $0$ 到 $9$ 的数字。每个拨圈都是从 $0$ 到 $9$ 的循环，即 $9$ 拨动一个位置后可以变成 $0$ 或 $8$，

因为校园里比较安全，小 Y 采用的锁车方式是：从正确密码开始，随机转动密码锁仅一次；每次都是以某个幅度仅转动一个拨圈或者同时转动两个相邻的拨圈。

当小 Y 选择同时转动两个相邻拨圈时，两个拨圈转动的幅度相同，即小 Y 可以将密码锁从 $\tt{0\;0\;1\;1\;5}$ 转成 $\tt{1\;1\;1\;1\;5}$，但不会转成 $\tt{1\;2\;1\;1\;5}$。

时间久了，小 Y 也担心这么锁车的安全性，所以小 Y 记下了自己锁车后密码锁的 $n$ 个状态，注意这 $n$ 个状态都不是正确密码。

为了检验这么锁车的安全性，小 Y 有多少种可能的正确密码，使得每个正确密码都能够按照他所采用的锁车方式产生锁车后密码锁的全部 $n$ 个状态。

输入格式

输入的第一行包含一个正整数 $n$，表示锁车后密码锁的状态数。

接下来 $n$ 行每行包含五个整数，表示一个密码锁的状态。

输出格式

输出一行包含一个整数，表示密码锁的这 $n$ 个状态按照给定的锁车方式能对应多少种正确密码。

样例 #1

样例输入 #1

1
0 0 1 1 5

样例输出 #1

81

提示

【样例 1 解释】

一共有 $81$ 种可能的方案。

其中转动一个拨圈的方案有 $45$ 种，转动两个拨圈的方案有 $36$ 种。

【样例 2】

见选手目录下的 lock/lock2.in 与 lock/lock2.ans。

【数据范围】

对于所有测试数据有：$1 \leq n \leq 8$。

测试点	$n\leq$	特殊性质
$1\sim 3$	$1$	无
$4\sim 5$	$2$	无
$6\sim 8$	$8$	A
$9\sim 10$	$8$	无

特殊性质 A：保证所有正确密码都可以通过仅转动一个拨圈得到测试数据给出的 $n$ 个状态。

附件下载

lock.zip 578B

// #include <bits/stdc++.h>
// using namespace std;
// int T;
// vector<int> a(5);
// set<vector<int>> st;
// int main()
// {
//     // freopen(".in", "r", stdin);
//     // freopen(".out", "w", stdout);
//     cin >> T;
//     while (T--)
//     {
//         for (int i = 0; i <= 4; i++)
//             cin >> a[i];
//         for (int i = 0; i <= 4; i++)      // 转动一个
//             for (int j = 1; j <= 10; j++) // 枚举幅度
//             {
//                 int tmp = a[i];
//                 a[i] = (a[i] + j) % 10;      // 转动
//                 st.insert(a);                // 记录
//                 a[i] = tmp;                  // 还原
//                 a[i] = (a[i] + 10 - j) % 10; // 反过来转
//                 st.insert(a);                // 记录
//                 a[i] = tmp;                  // 还原
//             }
//         for (int i = 0; i < 4; i++)       // 转两个
//             for (int j = 1; j <= 10; j++) // 枚举幅度
//             {
//                 int tmp1 = a[i], tmp2 = a[i + 1];
//                 a[i] = (a[i] + j) % 10;          // 转动
//                 a[i + 1] = (a[i + 1] + j) % 10;  // 转动
//                 st.insert(a);                    // 记录
//                 a[i] = tmp1;                     // 还原
//                 a[i + 1] = tmp2;                 // 还原
//                 a[i] = (a[i] + 10 - j) % 10;     // 反过来转
//                 a[i + 1] = (a[i] + 10 - j) % 10; // 反过来转
//                 st.insert(a);                    // 记录
//                 a[i] = tmp1;                     // 还原
//                 a[i + 1] = tmp2;                 // 还原
//             }
//         cout << st.size();
//         st.clear();
//     }
//     putchar('\n'), system("pause");
//     return 0;
// }
#include <bits/stdc++.h>
using namespace std;
int T;
bool check(string x, string y)
{
    bool flag1, flag2;
    int cnt = 0;
    int diff1 = -1, diff2 = -1;
    for (int i = 0; i < x.size(); i++)
        if (x[i] != y[i])
        {
            cnt++;
            if (diff1 == -1)
                diff1 = i;
            else if (diff2 == -1)
                diff2 = i;
        }
    flag1 = (cnt == 1);
    flag2 = (cnt == 2 && abs(diff1 - diff2) == 1 && (x[diff1] - y[diff1] + 10) % 10 == (x[diff2] - y[diff2] + 10) % 10);
    return flag1 || flag2;
}
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> T;
    while (T--)
    {
        int ans = 0;
        string st = "";
        for (int i = 1; i <= 5; i++)
        {
            int x;
            cin >> x;
            st += char(x + '0');
        }
        for (int i = 10000; i <= 99999; i++)
        {
            string s = to_string(i);
            ans += check(st, s);
        }
        cout << ans << endl;
    }
    putchar('\n'), system("pause");
    return 0;
}