[信息与未来 2017] 密码锁
题目描述
乌龟给自己的贵重物品上了密码锁。密码锁上有 5 个数字拨盘。每个数字拨盘每次向上拨使数字增加 1 （9 向上拨得到 0），向下拨使数字减少 1 （0 向下拨得到 9）。
拨盘上的数字组成一个 5 位数。只要拨盘上的数字变为素数，密码锁就会被解开。素数 (又称质数) 是只能被 1 和它自身整除的大于 1 的自然数。因为乌龟动作实在太慢，他希望你帮他计算如何开锁，使得拨动的总次数最少。
输入格式
一个5位数，表示拨盘的初始数字。
输出格式
一个5位素数，表示开启密码锁使用的素数（拨动次数最少）。如有多组解，输出满足条件的最大数。
样例 #1
样例输入 #1
01210
样例输出 #1
01319
解答思路
首先分析题意, 我们有一个5位的密码, 想要通过拨动它来使密码为一个质数, 我们要得到的是拨动次数最小的质数, 当波动次数相同时, 我们要输出最大的那个数.
由于密码是5位数, 我们可以枚举00000 ~ 99999, 其常数也不过十万, 再求出该范围内每个数与初始数字相差的拨动次数, 如果该数的拨动次数小于等于(为什么要等于, 因为等于的时候可以更新最大值), 就更新我们的答案, 最后将答案输出就好.
还有一个待解决的问题是, 我们该如何求最小的拨动次数, 比如说将6拨动到0, 如果按照6 - 5 - 4 - 3 - 2 - 1 - 0 的顺序, 它的拨动次数为6次(即6 - 0); 但按照6 - 7 - 8 - 9 - 0 的顺序, 它的波动次数为4次, 这明显是更小的拨动次数, 那么我们该如何处理这种情况呢?
可以画图来说明, 我们知道密码0 ~ 9是不断循环的, 因此我们可以将两个0 ~ 9拼接起来, 并重新定义他们的下标0 ~ 19.如图所示:
我们再来看刚才6到0的情况, 我们发现6(下标6)可以向左到0(下标0), 同时也可以向右到0(下标10),到左边的距离为6 - 0 = 6, 到右边的距离为10 - 6 = 4; 不难发现右边的下标均对应左边的下标 + 10, 比如说左边的2的下标为2, 右边的2的下标为12.并且距离就等于下标之差, 所以, 我们可以发现, 最短的拨动次数就会出现在当前的数为start, 目标数为target, 则右边的目标数为10 + target, 最短距离只会出现在start - target 和 10 + target - start这两个数的较小值(start >= target), 如果start < target, 就反过来;
那么, 我们就可以开始写代码了.
代码部分
#include <iostream>
#include <cmath>
#include <climits>
using namespace std;
int p;
bool checkIsPrime(int x){
if(x <= 1) return false;
for(int i = 2; i <= sqrt(x); i ++ ){
if(!(x % i)){
return false;
}
}
return true;
}
int getCnt(int ni, int np){
//枚举i和p的每一位
int ans = 0;
while(ni || np){
int numi = ni % 10, nump = np % 10;
if(numi < nump){
ans += min(10 + numi - nump, nump - numi);
}else{
ans += min(10 + nump - numi, numi - nump);
}
ni /= 10, np /= 10;
}
return ans;
}
int main() {
//因为密码锁只有5位, 所以可以暴力枚举1 ~ 99999, 输出拨动次数最少的最大数
cin >> p;
int cnt = INT_MAX;
int ans = INT_MIN;
for(int i = 0; i <= 99999; i ++ ){
//记录变化的位数
if(checkIsPrime(i)){
//getCnt用来计算i变成p的最小拨动次数
int cur = getCnt(i, p);
if(cur <= cnt){
cnt = cur;
ans = max(ans, i);
}
}
}
//最后格式化输出含前导0的答案
printf("%05d", ans);
return 0;
}