Codeforces 899D Shovel Sale

链接

传送门

题意

有\(n\)个铁铲，价格分别为\(1～n\)，现在要买两个铲子，要求价格和的末尾数字9的个数最多。输出有多少种买法。

思路

首先可以用买了个最贵的两个铲子的价格求出末尾最多有多少个9。一个9都凑不出来的时候答案为\(\frac{n \times (n - 1)}{2}\)。能凑出来时，枚举连续9之前的数字求和。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;

using namespace std;

const LL a[] = {0, 9, 99, 999, 9999, 99999, 999999, 9999999, 99999999, 999999999, 9999999999LL};
const LL b[] = {0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 10000000000LL};

int main() {
  LL n, sum;
  scanf("%lld", &n);
  sum = n + n - 1;
  int p = -1;
  while (sum >= a[p + 1]) {
    ++p;
  }
  if (p == 0) {
    printf("%lld\n", (n - 1) * n / 2);
    return 0;
  }
  LL ans = 0, cur = a[p];
  for (int i = 0; i < 10; ++i) {
    sum = n + n - 1;
    if (sum < cur) {
      break;
    }
    if (n >= cur) {
      ans += (cur - 1) / 2;
    } else {
      LL m = n + n - cur + 1;
      if (m > 1) {
        ans += m / 2;
      }
    }
    cur += b[p];
  }
  printf("%lld\n", ans);
  return 0;
}