F. Minimal Subset Difference

Codeforces
IDCF924F
Time3000ms
Memory256MB
Difficulty—
dp
English · Original
Chinese · Translation
Formal · Original
We call a positive integer _x_ a _k_\-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference between the sum of digits in one subset and the sum of digits in the other subset is **less than or equal to** _k_. Each digit should belong to exactly one subset after the split. There are _n_ queries for you. Each query is described with three integers _l_, _r_ and _k_, which mean that you are asked how many integers _x_ between _l_ and _r_ (inclusive) are _k_\-beautiful. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 5·104), indicating the number of queries. Each of the next _n_ lines describes a query, containing three integers _l_, _r_ and _k_ (1 ≤ _l_ ≤ _r_ ≤ 1018, 0 ≤ _k_ ≤ 9). ## Output For each query print a single number — the answer to the query. [samples] ## Note If 1 ≤ _x_ ≤ 9, integer _x_ is _k_\-beautiful if and only if _x_ ≤ _k_. If 10 ≤ _x_ ≤ 99, integer _x_ = 10_a_ + _b_ is _k_\-beautiful if and only if |_a_ - _b_| ≤ _k_, where _a_ and _b_ are integers between 0 and 9, inclusive. 100 is _k_\-beautiful if and only if _k_ ≥ 1.
我们称一个正整数 #cf_span[x] 为 #cf_span[k]-美观整数，当且仅当可以将其十进制表示中的各位数字组成的多重集划分为两个子集，使得其中一个子集的数字和与另一个子集的数字和之差的绝对值 *小于或等于* #cf_span[k]。划分后，每个数字必须恰好属于其中一个子集。 你有 #cf_span[n] 个查询。每个查询由三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k] 描述，表示你需要回答在区间 [#cf_span[l], #cf_span[r]]（包含端点）中有多少个整数 #cf_span[x] 是 #cf_span[k]-美观的。 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·10^4]），表示查询的数量。 接下来的 #cf_span[n] 行每行描述一个查询，包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^{18}]，#cf_span[0 ≤ k ≤ 9]）。 对于每个查询，请输出一个数——该查询的答案。 如果 #cf_span[1 ≤ x ≤ 9]，则整数 #cf_span[x] 是 #cf_span[k]-美观的当且仅当 #cf_span[x ≤ k]。 如果 #cf_span[10 ≤ x ≤ 99]，则整数 #cf_span[x = 10a + b] 是 #cf_span[k]-美观的当且仅当 #cf_span[|a - b| ≤ k]，其中 #cf_span[a] 和 #cf_span[b] 是介于 #cf_span[0] 和 #cf_span[9] 之间的整数。 #cf_span[100] 是 #cf_span[k]-美观的当且仅当 #cf_span[k ≥ 1]。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·10^4]），表示查询的数量。接下来的 #cf_span[n] 行每行描述一个查询，包含三个整数 #cf_span[l]、#cf_span[r] 和 #cf_span[k]（#cf_span[1 ≤ l ≤ r ≤ 10^{18}]，#cf_span[0 ≤ k ≤ 9]）。 ## Output 对于每个查询，请输出一个数——该查询的答案。 [samples] ## Note 如果 #cf_span[1 ≤ x ≤ 9]，则整数 #cf_span[x] 是 #cf_span[k]-美观的当且仅当 #cf_span[x ≤ k]。如果 #cf_span[10 ≤ x ≤ 99]，则整数 #cf_span[x = 10a + b] 是 #cf_span[k]-美观的当且仅当 #cf_span[|a - b| ≤ k]，其中 #cf_span[a] 和 #cf_span[b] 是介于 #cf_span[0] 和 #cf_span[9] 之间的整数。#cf_span[100] 是 #cf_span[k]-美观的当且仅当 #cf_span[k ≥ 1]。
Let $ S(x) $ denote the multiset of decimal digits of a positive integer $ x $. A positive integer $ x $ is **$ k $-beautiful** if and only if there exists a partition of $ S(x) $ into two disjoint subsets $ A $ and $ B $, such that: $$ \left| \sum_{d \in A} d - \sum_{d \in B} d \right| \leq k $$ Let $ T = \sum_{d \in S(x)} d $ be the total sum of digits of $ x $. Then $ x $ is $ k $-beautiful if and only if there exists a subset of digits summing to $ s $, such that: $$ |2s - T| \leq k $$ which is equivalent to: $$ s \in \left[ \frac{T - k}{2}, \frac{T + k}{2} \right] $$ and $ s $ must be an integer achievable as a subset sum of $ S(x) $. --- **Given:** - $ n $ queries ($ 1 \leq n \leq 5 \cdot 10^4 $) - Each query: $ l, r, k $ with $ 1 \leq l \leq r \leq 10^{18} $, $ 0 \leq k \leq 9 $ **For each query, compute:** $$ \left| \left\{ x \in \mathbb{Z} \mid l \leq x \leq r \text{ and } x \text{ is } k\text{-beautiful} \right\} \right| $$ --- **Special cases (from problem):** - If $ 1 \leq x \leq 9 $: $ x $ is $ k $-beautiful $ \iff x \leq k $ - If $ 10 \leq x \leq 99 $, $ x = 10a + b $: $ x $ is $ k $-beautiful $ \iff |a - b| \leq k $ - $ x = 100 $ is $ k $-beautiful $ \iff k \geq 1 $ > Note: These are illustrative edge cases; the general condition above applies to all $ x $. --- **Objective:** For each query $ (l, r, k) $, compute the count of $ k $-beautiful integers in $ [l, r] $, using the subset-sum condition on digit multisets.
Samples
Input #1
10
1 100 0
1 100 1
1 100 2
1 100 3
1 100 4
1 100 5
1 100 6
1 100 7
1 100 8
1 100 9
Output #1
9
28
44
58
70
80
88
94
98
100
Input #2
10
1 1000 0
1 1000 1
1 1000 2
1 1000 3
1 1000 4
1 1000 5
1 1000 6
1 1000 7
1 1000 8
1 1000 9
Output #2
135
380
573
721
830
906
955
983
996
1000
API Response (JSON) 
{
  "problem": {
    "name": "F. Minimal Subset Difference",
    "description": {
      "content": "We call a positive integer _x_ a _k_\\-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference betwee",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF924F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We call a positive integer _x_ a _k_\\-beautiful integer if and only if it is possible to split the multiset of its digits in the decimal representation into two subsets such that the difference betwee...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "我们称一个正整数 #cf_span[x] 为 #cf_span[k]-美观整数，当且仅当可以将其十进制表示中的各位数字组成的多重集划分为两个子集，使得其中一个子集的数字和与另一个子集的数字和之差的绝对值 *小于或等于* #cf_span[k]。划分后，每个数字必须恰好属于其中一个子集。\n\n你有 #cf_span[n] 个查询。每个查询由三个整数 #cf_span[l]、#cf_span[r] 和 ...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ S(x) $ denote the multiset of decimal digits of a positive integer $ x $.\n\nA positive integer $ x $ is **$ k $-beautiful** if and only if there exists a partition of $ S(x) $ into two disjoint s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments
© Rotriw 2026. 若您有相关疑问请联系 issue@rmj.ac