G. Sequence with Digits

Codeforces

IDCF10259G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Let's define the following recurrence: $$a_{n+1} = a_{n} + minDigit(a_{n}) \cdot maxDigit(a_{n}).$$ Here $m i n D i g i t (x)$ and $m a x D i g i t (x)$ are the minimal and maximal digits in the decimal representation of $x$ without leading zeroes. For examples refer to notes. Your task is calculate $a_K$ for given $a_1$ and $K$. The first line contains one integer $t$ ($1 <= t <= 1000$) — the number of independent test cases. Each test case consists of a single line containing two integers $a_1$ and $K$ ($1 <= a_1 <= 10^(18)$, $1 <= K <= 10^(16)$) separated by a space. For each test case print one integer $a_K$ on a separate line. $a_1 = 487$ $a_2 = a_1 + m i n D i g i t (a_1) dot.op m a x D i g i t (a_1) = 487 + min (4, 8, 7) dot.op max (4, 8, 7) = 487 + 4 dot.op 8 = 519$ $a_3 = a_2 + m i n D i g i t (a_2) dot.op m a x D i g i t (a_2) = 519 + min (5, 1, 9) dot.op max (5, 1, 9) = 519 + 1 dot.op 9 = 528$ $a_4 = a_3 + m i n D i g i t (a_3) dot.op m a x D i g i t (a_3) = 528 + min (5, 2, 8) dot.op max (5, 2, 8) = 528 + 2 dot.op 8 = 544$ $a_5 = a_4 + m i n D i g i t (a_4) dot.op m a x D i g i t (a_4) = 544 + min (5, 4, 4) dot.op max (5, 4, 4) = 544 + 4 dot.op 5 = 564$ $a_6 = a_5 + m i n D i g i t (a_5) dot.op m a x D i g i t (a_5) = 564 + min (5, 6, 4) dot.op max (5, 6, 4) = 564 + 4 dot.op 6 = 588$ $a_7 = a_6 + m i n D i g i t (a_6) dot.op m a x D i g i t (a_6) = 588 + min (5, 8, 8) dot.op max (5, 8, 8) = 588 + 5 dot.op 8 = 628$ ## Input The first line contains one integer $t$ ($1 <= t <= 1000$) — the number of independent test cases.Each test case consists of a single line containing two integers $a_1$ and $K$ ($1 <= a_1 <= 10^(18)$, $1 <= K <= 10^(16)$) separated by a space. ## Output For each test case print one integer $a_K$ on a separate line. [samples] ## Note $a_1 = 487$ $a_2 = a_1 + m i n D i g i t (a_1) dot.op m a x D i g i t (a_1) = 487 + min (4, 8, 7) dot.op max (4, 8, 7) = 487 + 4 dot.op 8 = 519$ $a_3 = a_2 + m i n D i g i t (a_2) dot.op m a x D i g i t (a_2) = 519 + min (5, 1, 9) dot.op max (5, 1, 9) = 519 + 1 dot.op 9 = 528$ $a_4 = a_3 + m i n D i g i t (a_3) dot.op m a x D i g i t (a_3) = 528 + min (5, 2, 8) dot.op max (5, 2, 8) = 528 + 2 dot.op 8 = 544$ $a_5 = a_4 + m i n D i g i t (a_4) dot.op m a x D i g i t (a_4) = 544 + min (5, 4, 4) dot.op max (5, 4, 4) = 544 + 4 dot.op 5 = 564$ $a_6 = a_5 + m i n D i g i t (a_5) dot.op m a x D i g i t (a_5) = 564 + min (5, 6, 4) dot.op max (5, 6, 4) = 564 + 4 dot.op 6 = 588$ $a_7 = a_6 + m i n D i g i t (a_6) dot.op m a x D i g i t (a_6) = 588 + min (5, 8, 8) dot.op max (5, 8, 8) = 588 + 5 dot.op 8 = 628$

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, t\} $, let $ a_1^{(k)} \in \mathbb{Z}^+ $ and $ K^{(k)} \in \mathbb{Z}^+ $ be given. Define the recurrence: $$ a_{n+1}^{(k)} = a_n^{(k)} + \minDigit(a_n^{(k)}) \cdot \maxDigit(a_n^{(k)}) $$ where for $ x \in \mathbb{Z}^+ $, - $ \minDigit(x) $ is the smallest digit in the decimal representation of $ x $ (no leading zeros), - $ \maxDigit(x) $ is the largest digit in the decimal representation of $ x $. **Constraints** 1. $ 1 \le t \le 1000 $ 2. For each test case: - $ 1 \le a_1^{(k)} \le 10^{18} $ - $ 1 \le K^{(k)} \le 10^{16} $ **Objective** For each test case $ k $, compute $ a_{K^{(k)}}^{(k)} $.

API Response (JSON)

{
  "problem": {
    "name": "G. Sequence with Digits",
    "description": {
      "content": "Let's define the following recurrence: $$a_{n+1} = a_{n} + minDigit(a_{n}) \\cdot maxDigit(a_{n}).$$ Here $m i n D i g i t (x)$ and $m a x D i g i t (x)$ are the minimal and maximal digits in the deci",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10259G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Let's define the following recurrence: $$a_{n+1} = a_{n} + minDigit(a_{n}) \\cdot maxDigit(a_{n}).$$\n\nHere $m i n D i g i t (x)$ and $m a x D i g i t (x)$ are the minimal and maximal digits in the deci...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, t\\} $, let $ a_1^{(k)} \\in \\mathbb{Z}^+ $ and $ K^{(k)} \\in \\mathbb{Z}^+ $ be given.  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments