D. Shovel Sale

Codeforces

IDCF899D

Time1000ms

Memory256MB

Difficulty—

constructive algorithmsmath

English · Original

Chinese · Translation

Formal · Original

There are _n_ shovels in Polycarp's shop. The _i_\-th shovel costs _i_ burles, that is, the first shovel costs 1 burle, the second shovel costs 2 burles, the third shovel costs 3 burles, and so on. Polycarps wants to sell shovels in pairs. Visitors are more likely to buy a pair of shovels if their total cost ends with several 9s. Because of this, Polycarp wants to choose a pair of shovels to sell in such a way that the sum of their costs ends with maximum possible number of nines. For example, if he chooses shovels with costs 12345 and 37454, their total cost is 49799, it ends with two nines. You are to compute the number of pairs of shovels such that their total cost ends with maximum possible number of nines. Two pairs are considered different if there is a shovel presented in one pair, but not in the other. ## Input The first line contains a single integer _n_ (2 ≤ _n_ ≤ 109) — the number of shovels in Polycarp's shop. ## Output Print the number of pairs of shovels such that their total cost ends with maximum possible number of nines. Note that it is possible that the largest number of 9s at the end is 0, then you should count all such ways. It is guaranteed that for every _n_ ≤ 109 the answer doesn't exceed 2·109. [samples] ## Note In the first example the maximum possible number of nines at the end is one. Polycarp cah choose the following pairs of shovels for that purpose: * 2 and 7; * 3 and 6; * 4 and 5. In the second example the maximum number of nines at the end of total cost of two shovels is one. The following pairs of shovels suit Polycarp: * 1 and 8; * 2 and 7; * 3 and 6; * 4 and 5; * 5 and 14; * 6 and 13; * 7 and 12; * 8 and 11; * 9 and 10. In the third example it is necessary to choose shovels 49 and 50, because the sum of their cost is 99, that means that the total number of nines is equal to two, which is maximum possible for _n_ = 50.

Polycarp 的商店中有 #cf_span[n] 把铲子。第 #cf_span[i] 把铲子的价格为 #cf_span[i] 布尔，即第一把铲子价格为 #cf_span[1] 布尔，第二把为 #cf_span[2] 布尔，第三把为 #cf_span[3] 布尔，依此类推。Polycarp 希望以成对的方式出售铲子。顾客更倾向于购买总价格以多个 #cf_span[9] 结尾的铲子对。因此，Polycarp 希望选择一对铲子，使得它们的价格之和结尾尽可能多地包含数字 9。例如，若他选择价格为 #cf_span[12345] 和 #cf_span[37454] 的铲子，其总价格为 #cf_span[49799]，结尾有两个 9。你需要计算有多少对铲子，其总价格结尾包含尽可能多的 9。如果一对铲子中有一把在另一对中不存在，则认为这两对不同。第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 109]）——Polycarp 商店中铲子的数量。请输出总价格结尾包含最多可能数量 9 的铲子对的数量。注意：最大可能的结尾 9 的数量可能是 0，此时你需要统计所有满足条件的配对方式。保证对于所有 #cf_span[n ≤ 109]，答案不超过 #cf_span[2·109]。在第一个示例中，结尾最多可能有 1 个 9。Polycarp 可以选择以下铲子对：在第二个示例中，两把铲子总价格结尾最多有 1 个 9。以下铲子对符合 Polycarp 的要求：在第三个示例中，必须选择价格为 #cf_span[49] 和 #cf_span[50] 的铲子，因为它们的价格和为 #cf_span[99]，即结尾有两个 9，这是 #cf_span[n = 50] 时可能的最大值。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[2 ≤ n ≤ 109]）——Polycarp 商店中铲子的数量。 ## Output 请输出总价格结尾包含最多可能数量 9 的铲子对的数量。注意，最大可能的结尾 9 的数量可能是 0，此时你需要统计所有满足条件的配对方式。保证对于所有 #cf_span[n ≤ 109]，答案不超过 #cf_span[2·109]。 [samples] ## Note 在第一个示例中，结尾最多可能有 1 个 9。Polycarp 可以选择以下铲子对：#cf_span[2] 和 #cf_span[7]；#cf_span[3] 和 #cf_span[6]；#cf_span[4] 和 #cf_span[5]。在第二个示例中，两把铲子总价格结尾最多有 1 个 9。以下铲子对符合 Polycarp 的要求：#cf_span[1] 和 #cf_span[8]；#cf_span[2] 和 #cf_span[7]；#cf_span[3] 和 #cf_span[6]；#cf_span[4] 和 #cf_span[5]；#cf_span[5] 和 #cf_span[14]；#cf_span[6] 和 #cf_span[13]；#cf_span[7] 和 #cf_span[12]；#cf_span[8] 和 #cf_span[11]；#cf_span[9] 和 #cf_span[10]。在第三个示例中，必须选择价格为 #cf_span[49] 和 #cf_span[50] 的铲子，因为它们的价格和为 #cf_span[99]，即结尾有两个 9，这是 #cf_span[n = 50] 时可能的最大值。

**Definitions** Let $ n \in \mathbb{Z} $, $ n \geq 2 $, be the number of shovels. Let the cost of the $ i $-th shovel be $ i $, for $ i \in \{1, 2, \dots, n\} $. **Constraints** $ 2 \leq n \leq 10^9 $ **Objective** Let $ S = \{ (i, j) \mid 1 \leq i < j \leq n \} $ be the set of all unordered pairs of distinct shovels. For each pair $ (i, j) $, define the sum $ s_{i,j} = i + j $. Let $ k_{\max} $ be the maximum number of trailing 9s in the decimal representation of any $ s_{i,j} $. Let $ P = \{ (i, j) \in S \mid s_{i,j} \text{ ends with exactly } k_{\max} \text{ trailing 9s} \} $. Compute $ |P| $.

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "D. Shovel Sale",
    "description": {
      "content": "There are _n_ shovels in Polycarp's shop. The _i_\\-th shovel costs _i_ burles, that is, the first shovel costs 1 burle, the second shovel costs 2 burles, the third shovel costs 3 burles, and so on. Po",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF899D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are _n_ shovels in Polycarp's shop. The _i_\\-th shovel costs _i_ burles, that is, the first shovel costs 1 burle, the second shovel costs 2 burles, the third shovel costs 3 burles, and so on. Po...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Polycarp 的商店中有 #cf_span[n] 把铲子。第 #cf_span[i] 把铲子的价格为 #cf_span[i] 布尔，即第一把铲子价格为 #cf_span[1] 布尔，第二把为 #cf_span[2] 布尔，第三把为 #cf_span[3] 布尔，依此类推。Polycarp 希望以成对的方式出售铲子。\n\n顾客更倾向于购买总价格以多个 #cf_span[9] 结尾的铲子对。因此，P...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ n \\geq 2 $, be the number of shovels.  \nLet the cost of the $ i $-th shovel be $ i $, for $ i \\in \\{1, 2, \\dots, n\\} $.  \n\n**Constraints**  \n$ 2 \\leq n \\l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments