F. Minimal Subset Difference

Codeforces

IDCF956F

Time3000ms

Memory256MB

Difficulty—

bitmasksdp

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.

Samples

Input #1

Output #1

Input #2

Output #2

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": "CF956F"
  },
  "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"
    }
  ]
}

Full JSON Raw Segments