Codeforces 899D Shovel Sale

链接

传送门

题意

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

思路

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

代码

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
#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;
}