Codeforces 899D Shovel Sale

題目大意

給定正整數 $n$（$2\le n\le 10^9$）。
考慮無序整數對 $(x, y)$（$1\le x,y\le n, x\ne y$）。
求滿足 「$x+y$ 結尾連續的 9 最多」的數對 $(x,y)$ 的個數。

例子：
$n=50$，$(49,50)$ 是一個滿足條件的數對。

比賽時我的思路

首先注意到，「兩個正整數的和」的結尾的連續的 9 一定不包含進位的貢獻，也不產生進位。

首先考慮（數對的和的）結尾最多有幾個連續的 9 。不難得出：
設 $n$ 的位數為 $k$ ，令 $x=5\times 10^{k-1}$ 。
若 $n\ge x$，則和的結尾最多有 $k$ 個連續的 9 。
若 $n=10^{k} - 1$，滿足條件的數對有 $n - x$ 個，否則有 $n-x+1$ 個。

若 $n < x$ ，數對之和的第 $k$ 位一定小于 $9$，故結尾至多有 $k-1$ 個連續的 9 。

若 $k-1=0$，則為平凡情形。
考慮 $k\ge 2$ 的情形。
設 $n$ 的 第 $k$ 位上的數字為 $h(n)$，顯然有 $h(n) > 0 $ 。

考慮數對 $(x,y)$（$x>y$），設 $x$ 的第 $k$ 位上的數字為 $h(x)$ 。
將所有滿足條件的數對 $(x,y)$ 分成下列若干類：

1. $h(n)>h(x)=h(y)=0$
2. $h(n)>h(x) = h(y) > 0$
3. $h(n)>h(x) > h(y)>0$
4. $h(n)>h(x) > h(y)=0$
5. $h(n)=h(x) > h(y) > 0$
6. $h(n) = h(x) > h(y) = 0$
7. $h(n) = h(x)= h(y) $

在比賽中，我沒考慮到上述第 7 種情況。

總結

本題的思維方式：分類。

實現技巧：
求一個正整數 $n$ 的位數可用 to_string(n).size() 。