[GCJKickstart2018RoundA] A. Even Digits

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://code.google.com/codejam/contest/9234486/dashboard#s=p0

给一个数，这个数每次只能+1或-1，问把这个数变成每一位都是偶数的最少步数。

其实就是说，求和这个数的差的绝对值最小的每位都是偶数的数。

考虑比这个数小的数，要最大化这个数就是把这个数最高位的奇数-1后面的数都是8；

考虑比这个数大的数，要最小化这个数就是把这个数最高位的奇数+1后面的数都是0，但是要考虑当前最高位是9的时候，再+1是不可能的了，所以这一个情况就不需要++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;

using LL = unsigned long long;
const  int maxn = 18;
string s;

LL down(string x) {
  string y = x;
  LL a = stoull(x);
  y[0]--;
  for(int i = 1; i < y.length(); i++) y[i] = '8';
  LL b = stoull(y);
  return a - b;
}

LL up(string x) {
  string y = x;
  LL a = stoull(x);
  if(y[0] != '9') {
    y[0]++;
    for(int i = 1; i < y.length(); i++) y[i] = '0';
    LL b = stoull(y);
    return b - a;
  }
}

signed main() {
  freopen("in", "r", stdin);
  freopen("out", "w", stdout);
  int T, _ = 1;
  scanf("%d", &T);
  while(T--) {
    cin >> s;
    int n = s.length();
    LL ret = 0;
    for(int i = 0; i < n; i++) {
      if((s[i] - '0') % 2 == 0) continue;
      ret = min(down(s.substr(i, n-i)), up(s.substr(i, n-i)));
      break;
    }
    printf("Case #%d: %lld\n", _++, ret);
  }
  return 0;
}