G. Parking Spaces

Codeforces

IDCF10279G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Monocarp has opened his own car park. There are $n$ parking spaces in total, located from left to right. Monocarp decided to number all his parking spaces, but since he really doesn't like the digit $k$, the numbering would be peculiar. Monocarp will number the parking spaces one by one (starting from the leftmost) with integers starting from one. If the next number that Monocarp wants to use for the current parking space contains the digit $k$ in its notation, then Monocarp will skip this number and move on to the next number until he finds a number that does not contain the digit $k$ in its notation. This would be the number that Monocarp will use for the current parking space; then he will continue assigning numbers to the next parking spaces. For example, if Monocarp doesn't like the digit $1$ and there are $12$ spaces in his car park, they will be numbered as follows: $[ 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 23, 24 ]$. Your task is to find the number that Monocarp will assign to the last (i. e. $n$-th) parking space. The first line contains two integers $n$ and $k$ $(1 <= n <= 10^9, 0 <= k <= 9)$ — the number of parking spaces and the digit that Monocarp doesn't like. Print the number that Vasily will assign to the $n$-th parking space. The first example is described in the statement. In the second example, there are $12$ parking spaces, and the digit that Monocarp doesn't like is $2$. The parking space numbers will thus look like this: $[ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14 ]$. Therefore, the $12$-th parking space will have the number $14$. In the third example, there are $18$ parking spaces, and the digit that Monocarp doesn't like is $0$. The parking space numbers will thus look like this: $[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]$. Therefore, the $18$-th parking space will have the number $19$. ## Input The first line contains two integers $n$ and $k$ $(1 <= n <= 10^9, 0 <= k <= 9)$ — the number of parking spaces and the digit that Monocarp doesn't like. ## Output Print the number that Vasily will assign to the $n$-th parking space. [samples] ## Note The first example is described in the statement. In the second example, there are $12$ parking spaces, and the digit that Monocarp doesn't like is $2$. The parking space numbers will thus look like this: $[ 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14 ]$. Therefore, the $12$-th parking space will have the number $14$.In the third example, there are $18$ parking spaces, and the digit that Monocarp doesn't like is $0$. The parking space numbers will thus look like this: $[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19 ]$. Therefore, the $18$-th parking space will have the number $19$.

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of parking spaces, and $ k \in \{0, 1, \dots, 9\} $ be the forbidden digit. Let $ f(m) $ denote the number of positive integers $ \leq m $ that do **not** contain the digit $ k $ in their decimal representation. **Constraints** $ 1 \leq n \leq 10^9 $, $ 0 \leq k \leq 9 $ **Objective** Find the smallest integer $ x \in \mathbb{Z}^+ $ such that $ f(x) = n $.

API Response (JSON)

{
  "problem": {
    "name": "G. Parking Spaces",
    "description": {
      "content": "Monocarp has opened his own car park. There are $n$ parking spaces in total, located from left to right. Monocarp decided to number all his parking spaces, but since he really doesn't like the digit $",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10279G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Monocarp has opened his own car park. There are $n$ parking spaces in total, located from left to right. Monocarp decided to number all his parking spaces, but since he really doesn't like the digit $...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of parking spaces, and $ k \\in \\{0, 1, \\dots, 9\\} $ be the forbidden digit.  \nLet $ f(m) $ denote the number of positive integers $ \\leq m $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments