B. A Prosperous Lot

Codeforces

IDCF934B

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsimplementation

English · Original

Chinese · Translation

Formal · Original

_Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that when Sui tries to approach them, it will be driven away by the fairies inside._ Big Banban is hesitating over the amount of money to give out. He considers loops to be lucky since it symbolizes unity and harmony. He would like to find a positive integer _n_ not greater than 1018, such that there are exactly _k_ loops in the decimal representation of _n_, or determine that such _n_ does not exist. A loop is a planar area enclosed by lines in the digits' decimal representation written in Arabic numerals. For example, there is one loop in digit 4, two loops in 8 and no loops in 5. Refer to the figure below for all exact forms. <center>![image](https://espresso.codeforces.com/aabe96422d20d188998fa211f3727cece8601ee9.png)</center> ## Input The first and only line contains an integer _k_ (1 ≤ _k_ ≤ 106) — the desired number of loops. ## Output Output an integer — if no such _n_ exists, output _\-1_; otherwise output any such _n_. In the latter case, your output should be a **positive** decimal integer not exceeding 1018. [samples]

除了年兽之外，还有一种名为祟的妖魔，它会惊吓儿童并使其生病。父母会给孩子们红包，把钱放在枕头下，这样当祟靠近时，会被钱中的仙子驱赶走。大班班正在犹豫该给多少压岁钱。他认为环形是幸运的，因为它象征着团结与和谐。他希望找到一个不超过 $10^{18}$ 的正整数 $n$，使得 $n$ 的十进制表示中恰好包含 $k$ 个环，或者确定这样的 $n$ 不存在。一个环是指在阿拉伯数字的十进制表示中，由线条围成的平面区域。例如，数字 $4$ 中有一个环，$8$ 中有两个环，而 $5$ 中没有环。具体形式请参考下图。第一行且仅一行包含一个整数 $k$（$1 ≤ k ≤ 10^6$）——期望的环的数量。输出一个整数：如果不存在这样的 $n$，输出 _-1_；否则输出任意一个满足条件的 $n$。在后一种情况下，你的输出必须是一个不超过 $10^{18}$ 的正十进制整数。 ## Input 第一行且仅一行包含一个整数 $k$（$1 ≤ k ≤ 10^6$）——期望的环的数量。 ## Output 输出一个整数：如果不存在这样的 $n$，输出 _-1_；否则输出任意一个满足条件的 $n$。在后一种情况下，你的输出必须是一个不超过 $10^{18}$ 的正十进制整数。 [samples]

**Definitions** Let $ k \in \mathbb{Z} $, $ 1 \leq k \leq 10^6 $, be the target number of loops. Let $ L(d) $ denote the number of loops in digit $ d \in \{0,1,\dots,9\} $: $$ L(0) = 1,\ L(1) = 0,\ L(2) = 0,\ L(3) = 0,\ L(4) = 1,\ L(5) = 0,\ L(6) = 1,\ L(7) = 0,\ L(8) = 2,\ L(9) = 1 $$ Let $ n \in \mathbb{Z}^+ $, $ n \leq 10^{18} $, be a positive integer whose decimal representation has digits $ d_1 d_2 \dots d_m $. **Constraints** 1. $ 1 \leq k \leq 10^6 $ 2. $ 1 \leq n \leq 10^{18} $ **Objective** Find any $ n $ such that $$ \sum_{i=1}^m L(d_i) = k $$ If no such $ n $ exists, output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. A Prosperous Lot",
    "description": {
      "content": "_Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF934B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_Apart from Nian, there is a daemon named Sui, which terrifies children and causes them to become sick. Parents give their children money wrapped in red packets and put them under the pillow, so that ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "除了年兽之外，还有一种名为祟的妖魔，它会惊吓儿童并使其生病。父母会给孩子们红包，把钱放在枕头下，这样当祟靠近时，会被钱中的仙子驱赶走。\n\n大班班正在犹豫该给多少压岁钱。他认为环形是幸运的，因为它象征着团结与和谐。\n\n他希望找到一个不超过 $10^{18}$ 的正整数 $n$，使得 $n$ 的十进制表示中恰好包含 $k$ 个环，或者确定这样的 $n$ 不存在。\n\n一个环是指在阿拉伯数字的十进制表示中...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ k \\in \\mathbb{Z} $, $ 1 \\leq k \\leq 10^6 $, be the target number of loops.  \nLet $ L(d) $ denote the number of loops in digit $ d \\in \\{0,1,\\dots,9\\} $:  \n$$\nL(0) = 1,\\ L(1) = ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments