D. Ability To Convert

Codeforces

IDCF758D

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsdpgreedymathstrings

English · Original

Chinese · Translation

Formal · Original

Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of the letter _A_ he will write the number 10. Thus, by converting the number 475 from decimal to hexadecimal system, he gets 11311 (475 = 1·162 + 13·161 + 11·160). Alexander lived calmly until he tried to convert the number back to the decimal number system. Alexander remembers that he worked with little numbers so he asks to find the minimum decimal number so that by converting it to the system with the base _n_ he will get the number _k_. ## Input The first line contains the integer _n_ (2 ≤ _n_ ≤ 109). The second line contains the integer _k_ (0 ≤ _k_ < 1060), it is guaranteed that the number _k_ contains no more than 60 symbols. All digits in the second line are strictly less than _n_. Alexander guarantees that the answer exists and does not exceed 1018. The number _k_ doesn't contain leading zeros. ## Output Print the number _x_ (0 ≤ _x_ ≤ 1018) — the answer to the problem. [samples] ## Note In the first example 12 could be obtained by converting two numbers to the system with base 13: 12 = 12·130 or 15 = 1·131 + 2·130.

Alexander 正在学习如何将十进制数转换为任意进制，但他不懂英文字母，因此他将任何数都仅以十进制形式书写，也就是说，他不会使用字母 #cf_span[A]，而是写成数字 #cf_span[10]。因此，当他将十进制数 #cf_span[475] 转换为十六进制时，他会得到 #cf_span[11311]（因为 #cf_span[475 = 1·162 + 13·161 + 11·160]）。Alexander 一直平静地生活，直到他尝试将这个数重新转换回十进制系统。 Alexander 记得他处理的都是较小的数，因此他要求找出最小的十进制数，使得将其转换为以 #cf_span[n] 为基数的进制时，得到的数恰好是 #cf_span[k]。第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 109]）。第二行包含整数 #cf_span[k]（#cf_span[0 ≤ k < 1060]），保证 #cf_span[k] 的位数不超过 #cf_span[60] 位。第二行中的所有数字都严格小于 #cf_span[n]。 Alexander 保证答案存在且不超过 #cf_span[1018]。数 #cf_span[k] 不包含前导零。请输出数 #cf_span[x]（#cf_span[0 ≤ x ≤ 1018]）——本题的答案。在第一个例子中，#cf_span[12] 可以通过将两个数转换为以 #cf_span[13] 为基数的进制得到：#cf_span[12 = 12·130] 或 #cf_span[15 = 1·131 + 2·130]。 ## Input 第一行包含整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 109]）。第二行包含整数 #cf_span[k]（#cf_span[0 ≤ k < 1060]），保证 #cf_span[k] 的位数不超过 #cf_span[60] 位。第二行中的所有数字都严格小于 #cf_span[n]。Alexander 保证答案存在且不超过 #cf_span[1018]。数 #cf_span[k] 不包含前导零。 ## Output 请输出数 #cf_span[x]（#cf_span[0 ≤ x ≤ 1018]）——本题的答案。 [samples] ## Note 在第一个例子中，#cf_span[12] 可以通过将两个数转换为以 #cf_span[13] 为基数的进制得到：#cf_span[12 = 12·130] 或 #cf_span[15 = 1·131 + 2·130]。

**Definitions** Let $ n \in \mathbb{Z} $ be the base ($2 \leq n \leq 10^9$). Let $ k $ be a string of decimal digits representing a number in base $ n $, with $ 0 \leq k < 10^{60} $, and each digit $ d $ in $ k $ satisfies $ 0 \leq d < n $. Let $ D = (d_1, d_2, \dots, d_m) $ be the sequence of digits of $ k $, interpreted as a base-$ n $ number, where $ m $ is the length of $ k $. **Constraints** 1. $ 2 \leq n \leq 10^9 $ 2. $ 0 \leq k < 10^{60} $, and $ k $ has at most 60 digits 3. Each digit $ d_i $ of $ k $ satisfies $ 0 \leq d_i < n $ 4. $ k $ has no leading zeros 5. The answer $ x $ satisfies $ 0 \leq x \leq 10^{18} $ **Objective** Find the minimum decimal number $ x $ such that when $ x $ is expressed in base $ n $, its digit representation (written in decimal form without letters) equals the string $ k $. That is, find the minimal $ x \in \mathbb{Z}_{\geq 0} $ satisfying: $$ x = \sum_{i=1}^{m} d_i \cdot n^{m-i} $$ where $ d_i $ is the $ i $-th digit of the string $ k $.

Samples

Input #1

13
12

Output #1

Input #2

16
11311

Output #2

Input #3

20
999

Output #3

Input #4

17
2016

Output #4

API Response (JSON)

{
  "problem": {
    "name": "D. Ability To Convert",
    "description": {
      "content": "Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF758D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alexander is learning how to convert numbers from the decimal system to any other, however, he doesn't know English letters, so he writes any number only as a decimal number, it means that instead of ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Alexander 正在学习如何将十进制数转换为任意进制，但他不懂英文字母，因此他将任何数都仅以十进制形式书写，也就是说，他不会使用字母 #cf_span[A]，而是写成数字 #cf_span[10]。因此，当他将十进制数 #cf_span[475] 转换为十六进制时，他会得到 #cf_span[11311]（因为 #cf_span[475 = 1·162 + 13·161 + 11·160]）。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the base ($2 \\leq n \\leq 10^9$).  \nLet $ k $ be a string of decimal digits representing a number in base $ n $, with $ 0 \\leq k < 10^{60} $, and each digi...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments