F. Igor and Interesting Numbers

Codeforces

IDCF747F

Time2000ms

Memory256MB

Difficulty—

brute forcecombinatoricsdpmath

English · Original

Chinese · Translation

Formal · Original

Igor likes hexadecimal notation and considers **positive** integer in the hexadecimal notation _interesting_ if each digit and each letter in it appears no more than _t_ times. For example, if _t_ = 3, then integers _13a13322_, _aaa_, _abcdef0123456789_ are interesting, but numbers _aaaa_, _abababab_ and _1000000_ are not interesting. Your task is to find the _k_\-th smallest _interesting_ for Igor integer in the hexadecimal notation. The integer should not contain leading zeros. ## Input The first line contains the two integers _k_ and _t_ (1 ≤ _k_ ≤ 2·109, 1 ≤ _t_ ≤ 10) — the number of the required integer and the maximum number of times some integer or letter can appear in interesting integer. It can be shown that the answer always exists for such constraints. ## Output Print in the hexadecimal notation the only integer that is the _k_\-th smallest _interesting_ integer for Igor. [samples] ## Note The first 20 _interesting_ integers if _t_ = 1: _1_, _2_, _3_, _4_, _5_, _6_, _7_, _8_, _9_, _a_, _b_, _c_, _d_, _e_, _f_, _10_, _12_, _13_, _14_, _15_. So the answer for the first example equals _12_.

Igor 喜欢十六进制表示法，并认为一个正整数在十六进制表示中是 _interesting_ 的，当且仅当其中的每个数字和每个字母出现的次数不超过 #cf_span[t] 次。例如，如果 #cf_span[t = 3]，那么整数 _13a13322_、_aaa_、_abcdef0123456789_ 是 _interesting_ 的，但数字 _aaaa_、_abababab_ 和 _1000000_ 不是 _interesting_ 的。你的任务是找到 Igor 的十六进制表示中第 #cf_span[k] 小的 _interesting_ 整数。该整数不应包含前导零。第一行包含两个整数 #cf_span[k] 和 #cf_span[t] (#cf_span[1 ≤ k ≤ 2·109], #cf_span[1 ≤ t ≤ 10]) —— 分别表示所需的整数序号和某个数字或字母在 _interesting_ 整数中最多出现的次数。可以证明，在这些约束下答案一定存在。请以十六进制表示法输出唯一的整数，它是 Igor 的第 #cf_span[k] 小的 _interesting_ 整数。当 #cf_span[t = 1] 时，前 20 个 _interesting_ 整数为：_1_、_2_、_3_、_4_、_5_、_6_、_7_、_8_、_9_、_a_、_b_、_c_、_d_、_e_、_f_、_10_、_12_、_13_、_14_、_15_。因此第一个示例的答案为 _12_。 ## Input 第一行包含两个整数 #cf_span[k] 和 #cf_span[t] (#cf_span[1 ≤ k ≤ 2·109], #cf_span[1 ≤ t ≤ 10]) —— 分别表示所需的整数序号和某个数字或字母在 _interesting_ 整数中最多出现的次数。可以证明，在这些约束下答案一定存在。 ## Output 请以十六进制表示法输出唯一的整数，它是 Igor 的第 #cf_span[k] 小的 _interesting_ 整数。 [samples] ## Note 当 #cf_span[t = 1] 时，前 20 个 _interesting_ 整数为：_1_、_2_、_3_、_4_、_5_、_6_、_7_、_8_、_9_、_a_、_b_、_c_、_d_、_e_、_f_、_10_、_12_、_13_、_14_、_15_。因此第一个示例的答案为 _12_。

**Definitions** Let $\Sigma = \{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\}$ be the set of 16 hexadecimal digits. Let $t \in \mathbb{Z}^+$ be the maximum allowed frequency of any digit/letter in an "interesting" number. An integer in hexadecimal notation is *interesting* if: - It has no leading zeros. - Each symbol in $\Sigma$ appears at most $t$ times in its representation. Let $S_k$ denote the $k$-th smallest interesting integer in lexicographic order (under hexadecimal representation, no leading zeros). **Constraints** 1. $1 \leq k \leq 2 \cdot 10^9$ 2. $1 \leq t \leq 10$ **Objective** Find $S_k$, the $k$-th smallest interesting integer in hexadecimal notation.

Samples

Input #1

17 1

Output #1

Input #2

1000000 2

Output #2

fca2c

API Response (JSON)

{
  "problem": {
    "name": "F. Igor and Interesting Numbers",
    "description": {
      "content": "Igor likes hexadecimal notation and considers **positive** integer in the hexadecimal notation _interesting_ if each digit and each letter in it appears no more than _t_ times. For example, if _t_ = 3",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF747F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Igor likes hexadecimal notation and considers **positive** integer in the hexadecimal notation _interesting_ if each digit and each letter in it appears no more than _t_ times. For example, if _t_ = 3...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Igor 喜欢十六进制表示法，并认为一个正整数在十六进制表示中是 _interesting_ 的，当且仅当其中的每个数字和每个字母出现的次数不超过 #cf_span[t] 次。例如，如果 #cf_span[t = 3]，那么整数 _13a13322_、_aaa_、_abcdef0123456789_ 是 _interesting_ 的，但数字 _aaaa_、_abababab_ 和 _100000...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $\\Sigma = \\{0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f\\}$ be the set of 16 hexadecimal digits.  \nLet $t \\in \\mathbb{Z}^+$ be the maximum allowed frequency of any digit/letter in an \"interes...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments