B. Maximize Sum of Digits

Codeforces

IDCF770B

Time1000ms

Memory256MB

Difficulty—

implementationmath

English · Original

Chinese · Translation

Formal · Original

Anton has the integer _x_. He is interested what positive integer, which doesn't exceed _x_, has the maximum sum of digits. Your task is to help Anton and to find the integer that interests him. If there are several such integers, determine the biggest of them. ## Input The first line contains the positive integer _x_ (1 ≤ _x_ ≤ 1018) — the integer which Anton has. ## Output Print the positive integer which doesn't exceed _x_ and has the maximum sum of digits. If there are several such integers, print the biggest of them. Printed integer must not contain leading zeros. [samples]

Anton 有一个整数 #cf_span[x]。他想知道一个不超过 #cf_span[x] 的正整数，其各位数字之和最大。你的任务是帮助 Anton 找到这个整数。如果有多个这样的整数，请找出其中最大的一个。第一行包含一个正整数 #cf_span[x]（#cf_span[1 ≤ x ≤ 1018]）——Anton 拥有的整数。请输出一个不超过 #cf_span[x] 且各位数字之和最大的正整数。如果有多个这样的整数，请输出其中最大的一个。输出的整数不能包含前导零。 ## Input 第一行包含一个正整数 #cf_span[x]（#cf_span[1 ≤ x ≤ 1018]）——Anton 拥有的整数。 ## Output 请输出一个不超过 #cf_span[x] 且各位数字之和最大的正整数。如果有多个这样的整数，请输出其中最大的一个。输出的整数不能包含前导零。 [samples]

**Definitions** Let $ x \in \mathbb{Z} $ with $ 1 \leq x \leq 10^{18} $. Let $ S(n) = \sum_{i=0}^{k} d_i $ denote the sum of digits of a positive integer $ n $, where $ n = \sum_{i=0}^{k} d_i \cdot 10^i $ and $ d_i \in \{0,1,\dots,9\} $, $ d_k \neq 0 $. **Constraints** Find $ n \in \mathbb{Z} $ such that: 1. $ 1 \leq n \leq x $ 2. $ S(n) $ is maximized over all such $ n $ 3. If multiple $ n $ achieve the maximum $ S(n) $, choose the largest such $ n $ **Objective** Determine $ \max \left\{ n \in \mathbb{Z} \mid 1 \leq n \leq x \text{ and } S(n) = \max_{1 \leq m \leq x} S(m) \right\} $

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "B. Maximize Sum of Digits",
    "description": {
      "content": "Anton has the integer _x_. He is interested what positive integer, which doesn't exceed _x_, has the maximum sum of digits. Your task is to help Anton and to find the integer that interests him. If t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF770B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Anton has the integer _x_. He is interested what positive integer, which doesn't exceed _x_, has the maximum sum of digits.\n\nYour task is to help Anton and to find the integer that interests him. If t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Anton 有一个整数 #cf_span[x]。他想知道一个不超过 #cf_span[x] 的正整数，其各位数字之和最大。\n\n你的任务是帮助 Anton 找到这个整数。如果有多个这样的整数，请找出其中最大的一个。\n\n第一行包含一个正整数 #cf_span[x]（#cf_span[1 ≤ x ≤ 1018]）——Anton 拥有的整数。\n\n请输出一个不超过 #cf_span[x] 且各位数字之和最大...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ x \\in \\mathbb{Z} $ with $ 1 \\leq x \\leq 10^{18} $.  \nLet $ S(n) = \\sum_{i=0}^{k} d_i $ denote the sum of digits of a positive integer $ n $, where $ n = \\sum_{i=0}^{k} d_i \\cdo...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments