题目描述

Supervin有一个独特的计算器。

此计算器由一个显示器，一个加号按钮和一个减号按钮构成。

目前，计算器显示器上显示整数 N。

按加号按钮可将计算器显示屏上显示的当前数字增加1。

同理，按减号按钮可将计算器显示屏上显示的当前数字减1。

计算器不显示任何前导零。

例如，如果计算器显示屏上显示100，则按减号按钮一次将使计算器显示99。

Supervin不喜欢奇数，因为他认为他们是“奇怪的”。

因此，他想通过按动计算器上的按钮来改变显示器上的数字，使得显示数字变为一个全部数位上数字均为偶数的十进制数。

因为计算器比较老旧，按钮并不是很好用，因此Supervin希望尽可能少的按动按钮。

请帮助Supervin确定要使得显示数字各个数位均为偶数，至少需要按动多少次按钮。

输入格式
输入第一行包含整数T，表示共有T组测试数据。

接下来T行，每行包含一个整数N，表示显示器上最初显示的数字。

输出格式
每组测试数据输出一个结果，每个结果占一行。

结果表示为“Case #x: y”，其中x为组别编号（从1开始），y为该组数据结果（即最少按动次数）。
数据范围
$ 1 \leq T \leq N $
$ 1 \leq N \leq 10_{}^{16} $

样例

输入样例：

4
42
11
1
2018 

输出样例：

Case #1: 0
Case #2: 3
Case #3: 1
Case #4: 2

算法1

(暴力枚举) $O(n)$

根据题意，要找到离数最近的一个每个位置均为偶数的数
我们可以采用从高位到低位枚举的方式：设枚举到的位数为$k$。

• 1.如果k位的数为偶数，则直接跳过。
• 2.若不是，则需要从该位进行变换：
  • 第一种变换方式为将该位-1，则后面几位也均要进行变换，最近的一个数便为后几位均为8
  • 第二种变换方式，挡该位数不是9时，则可将该位数+1,则离其最近的一个数便为后几位均为0。
• 3.最后比较两种变换方式离初始数的差，较小的即为最小操作次数。

时间复杂度

由于只循环两次，一次取得最小值，一次取得最大值，但每次循环均为O(n),总的时间复杂度即为O(n)

参考文献

KickStart官网

C++ 代码

#include<iostream>
using namespace std;
typedef long long LL;
const int N  = 20;
int T;
int nums[N];

int main()
{
    cin >> T;
    int cnt = 1;
    while(T--){
        LL n;
        cin >> n;
        LL tmp_n = n;
        int k = 0;
        while(n){
            nums[k] = n % 10;
            k++;
            n /= 10;
        }
        int len = k;
        LL res = 0;        
        LL l = 0, r = 0;
        for(int i = len - 1; i >= 0; i--){
            int t = nums[i];
            if(t % 2 == 0){
                l = l * 10 + t;
                r = r * 10 + t;
            }else{
                l = l * 10 + t - 1;
                for(int j = i - 1; j >= 0; j--) l = l * 10 + 8;
                res = tmp_n - l;
                if(t != 9){
                    r = r * 10 + t + 1;
                    for(int j = i - 1; j >= 0; j--) r = r * 10;
                    res = min(res, r - tmp_n);
                }
                break;
            }
        }
        printf("Case #%d: %lld \n", cnt++, res);
    }
    return 0;
}