A. Efim and Strange Grade

Codeforces

IDCF718A

Time1000ms

Memory256MB

Difficulty—

dpimplementationmath

English · Original

Chinese · Translation

Formal · Original

Efim just received his grade for the last test. He studies in a special school and his grade can be equal to any positive decimal fraction. First he got disappointed, as he expected a way more pleasant result. Then, he developed a tricky plan. Each second, he can ask his teacher to round the grade at any place after the decimal point (also, he can ask to round to the nearest integer). There are _t_ seconds left till the end of the break, so Efim has to act fast. Help him find what is the maximum grade he can get in no more than _t_ seconds. Note, that he can choose to not use all _t_ seconds. Moreover, he can even choose to not round the grade at all. In this problem, classic rounding rules are used: while rounding number to the _n_\-th digit one has to take a look at the digit _n_ + 1. If it is less than 5 than the _n_\-th digit remain unchanged while all subsequent digits are replaced with 0. Otherwise, if the _n_ + 1 digit is greater or equal to 5, the digit at the position _n_ is increased by 1 (this might also change some other digits, if this one was equal to 9) and all subsequent digits are replaced with 0. At the end, all trailing zeroes are thrown away. For example, if the number 1.14 is rounded to the first decimal place, the result is 1.1, while if we round 1.5 to the nearest integer, the result is 2. Rounding number 1.299996121 in the fifth decimal place will result in number 1.3. ## Input The first line of the input contains two integers _n_ and _t_ (1 ≤ _n_ ≤ 200 000, 1 ≤ _t_ ≤ 109) — the length of Efim's grade and the number of seconds till the end of the break respectively. The second line contains the grade itself. It's guaranteed that the grade is a positive number, containing at least one digit after the decimal points, and it's representation doesn't finish with 0. ## Output Print the maximum grade that Efim can get in _t_ seconds. Do not print trailing zeroes. [samples] ## Note In the first two samples Efim initially has grade 10.245. During the first second Efim can obtain grade 10.25, and then 10.3 during the next second. Note, that the answer 10.30 will be considered incorrect. In the third sample the optimal strategy is to not perform any rounding at all.

[{"iden":"statement","content":"Efim 刚刚收到了他最后一次测试的成绩。他就读于一所特殊学校，他的成绩可以是任意正的小数。起初他感到失望，因为他期望得到一个更令人满意的结果。随后，他想出了一个巧妙的计划：每秒，他可以要求老师在小数点后的任意位置对成绩进行四舍五入（也可以要求四舍五入到最近的整数）。\n\n距离课间结束还剩 #cf_span[t] 秒，因此 Efim 必须迅速行动。请帮助他找出在不超过 #cf_span[t] 秒的情况下，他能得到的最大成绩。注意，他可以选择不使用全部 #cf_span[t] 秒，甚至可以选择完全不进行四舍五入。\n\n本题中使用经典的四舍五入规则：当将数字四舍五入到第 #cf_span[n] 位时，需要查看第 #cf_span[n + 1] 位数字。如果该位数字小于 #cf_span[5]，则第 #cf_span[n] 位保持不变，其后所有数字均被替换为 #cf_span[0]；否则，如果第 #cf_span[n + 1] 位数字大于或等于 #cf_span[5]，则第 #cf_span[n] 位数字加 #cf_span[1]（这可能会导致前面的某些数字也发生变化，如果该位原本是 #cf_span[9]），其后所有数字均被替换为 #cf_span[0]。最后，所有末尾的零将被移除。\n\n例如，将数字 #cf_span[1.14] 四舍五入到第一位小数，结果为 #cf_span[1.1]；将 #cf_span[1.5] 四舍五入到最近的整数，结果为 #cf_span[2]。将数字 #cf_span[1.299996121] 四舍五入到第五位小数，结果为 #cf_span[1.3]。\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[t]（#cf_span[1 ≤ n ≤ 200 000]，#cf_span[1 ≤ t ≤ 10^9]），分别表示 Efim 成绩的长度和课间剩余的秒数。\n\n第二行包含成绩本身。保证成绩是一个正数，至少包含一位小数，且其表示形式不以 #cf_span[0] 结尾。\n\n请输出 Efim 在 #cf_span[t] 秒内能得到的最大成绩。不要输出末尾的零。"}},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[t]（#cf_span[1 ≤ n ≤ 200 000]，#cf_span[1 ≤ t ≤ 10^9]），分别表示 Efim 成绩的长度和课间剩余的秒数。第二行包含成绩本身。保证成绩是一个正数，至少包含一位小数，且其表示形式不以 #cf_span[0] 结尾。"},{"iden":"output","content":"请输出 Efim 在 #cf_span[t] 秒内能得到的最大成绩。不要输出末尾的零。"},{"iden":"examples","content":"输入\n6 1\n10.245\n输出\n10.25\n\n输入\n6 2\n10.245\n输出\n10.3\n\n输入\n3 100\n9.2\n输出\n9.2"},{"iden":"note","content":"在前两个样例中，Efim 初始成绩为 #cf_span[10.245]。第一秒，他可以获得成绩 #cf_span[10.25]，第二秒再获得 #cf_span[10.3]。注意，答案 #cf_span[10.30] 将被视为错误。在第三个样例中，最优策略是完全不进行四舍五入。"}]

**Definitions** Let $ s $ be a string representing Efim’s grade, of the form $ d_1d_2\dots d_k.d_{k+1}d_{k+2}\dots d_n $, where $ d_i \in \{0,1,\dots,9\} $, the decimal point is at position $ k $, and $ d_n \neq 0 $. Let $ t \in \mathbb{Z}^+ $ be the number of available rounding operations. **Constraints** 1. $ 1 \leq n \leq 200{,}000 $, $ 1 \leq t \leq 10^9 $ 2. The grade contains at least one digit after the decimal point. 3. The representation of the grade does not end with `0`. 4. Each rounding operation targets a decimal position $ i \geq k+1 $, rounding the number to the $ (i-1) $-th digit after the decimal (i.e., the $ i $-th digit overall after the decimal point). 5. Rounding follows standard rules: if the digit at position $ i+1 \geq 5 $, increment the digit at position $ i $ (with carry propagation), then truncate all subsequent digits; otherwise, truncate all digits after position $ i $. 6. Trailing zeros after rounding are removed. 7. At most $ t $ rounding operations may be performed, not necessarily all. **Objective** Find the maximum possible value of the grade after performing at most $ t $ valid rounding operations, where each operation rounds at one decimal digit position (from right to left), and trailing zeros are omitted in the output.

Samples

Input #1

6 1
10.245

Output #1

10.25

Input #2

6 2
10.245

Output #2

10.3

Input #3

3 100
9.2

Output #3

9.2

API Response (JSON)

{
  "problem": {
    "name": "A. Efim and Strange Grade",
    "description": {
      "content": "Efim just received his grade for the last test. He studies in a special school and his grade can be equal to any positive decimal fraction. First he got disappointed, as he expected a way more pleasan",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF718A"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Efim just received his grade for the last test. He studies in a special school and his grade can be equal to any positive decimal fraction. First he got disappointed, as he expected a way more pleasan...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "[{\"iden\":\"statement\",\"content\":\"Efim 刚刚收到了他最后一次测试的成绩。他就读于一所特殊学校，他的成绩可以是任意正的小数。起初他感到失望，因为他期望得到一个更令人满意的结果。随后，他想出了一个巧妙的计划：每秒，他可以要求老师在小数点后的任意位置对成绩进行四舍五入（也可以要求四舍五入到最近的整数）。\\n\\n距离课间结束还剩 #cf_span[t] 秒，因此 Efim...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s $ be a string representing Efim’s grade, of the form $ d_1d_2\\dots d_k.d_{k+1}d_{k+2}\\dots d_n $, where $ d_i \\in \\{0,1,\\dots,9\\} $, the decimal point is at position $ k $, a...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments