CF924F Minimal Subset Difference

我们称一个正整数 $x$ 为 $k$-美丽整数，当且仅当可以将其十进制表示下的数字多重集合分成两个子集，使得其中一个子集的数字和与另一个子集的数字和之差小于等于 $k$。每个数字在分割后必须恰好属于一个子集。 现在有 $n$ 个询问。每个询问由三个整数 $l$、$r$ 和 $k$ 描述，表示你需要回答有多少个 $x$ 满足 $l \leq x \leq r$，且 $x$ 是 $k$-美丽整数。

第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^{4}$），表示询问的数量。 接下来的 $n$ 行，每行包含三个整数 $l$、$r$ 和 $k$（$1 \leq l \leq r \leq 10^{18}$，$0 \leq k \leq 9$），描述一个询问。

对于每个询问，输出一个整数，表示满足条件的 $k$-美丽整数的个数。

如果 $1 \leq x \leq 9$，整数 $x$ 是 $k$-美丽整数当且仅当 $x \leq k$。 如果 $10 \leq x \leq 99$，整数 $x=10a+b$ 是 $k$-美丽整数当且仅当 $|a-b| \leq k$，其中 $a$ 和 $b$ 是 $0$ 到 $9$ 之间的整数。 $100$ 是 $k$-美丽整数当且仅当 $k \geq 1$。 由 ChatGPT 4.1 翻译