「SiR-1」Popsicle

Luogu

IDLGP9354

Time1000ms

Memory128MB

DifficultyP1

模拟洛谷原创O2优化洛谷月赛

猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0\sim 9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数字为 $0$ 的雪糕棒（也即 $n$ 出现了前导 $0$），猫猫会把这些雪糕棒拿走。小老鼠会来捣乱，它会在某个时刻（可能是所有操作开始之前，也可能是猫猫任意一次操作之后）改变某个雪糕棒上的一个数字。小老鼠**总共只能改变一个数字**。小老鼠希望操作次数尽量多，猫猫希望操作次数尽量少，所以她想知道二者都使用最优策略时，她的操作次数。 ## Input **本题单个测试点内有多组数据。** 第一行，一个正整数 $T$ 表示数据组数。对于每组数据： - 仅一行，一个正整数 $n$。 ## Output 共 $T$ 行，每行一个整数，表示答案。 [samples] ## Background 然而如何优雅地摆烂？ ## Note ### 样例解释 1 对于第一组数据，小老鼠可以一开始就将 $1100$ 变为 $1109$，这样猫猫共需要 $1 + 1 + 9$ 次操作把 $n$ 变为 $0$。 ### 数据规模与约定 **本题采用捆绑测试。** + Subtask 0（13 pts）：$n \leq 99$。 + Subtask 1（13 pts）：$n = 10^k$，$k$ 为自然数。 + Subtask 2（13 pts）：$n = 10^k - 1$，$k$ 为正整数。 + Subtask 3（13 pts）：$n \leq 999\ 999$。 + Subtask 4（48 pts）：无特殊限制。对于所有数据，$1 \leq T \leq 3333$，$1 \leq n \leq 9\ 999\ 999\ 999\ 999(=10^{13} - 1)$，毕竟猫猫最多一捆只有 $13$ 根雪糕嘛。

Samples

Input #1

2
1100
11332132121

Output #1

11
28

API Response (JSON)

{
  "problem": {
    "name": "「SiR-1」Popsicle",
    "description": {
      "content": "猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0\\sim 9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。 猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。 猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P1"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9354"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "猫猫有若干个雪糕棒排成一排，每个雪糕棒上有一个 $0\\sim 9$ 的数字，并且满足最左边的雪糕棒上写的数字不为 $0$。猫猫认为这一排雪糕棒从左到右依次构成了十进制正整数 $n$。\n\n猫猫认为 $0$ 是美好的，所以她会尽可能把 $n$ 变成 $0$，也就是把所有雪糕棒都拿走。\n\n猫猫每次会进行一次操作。每次操作选择一个数字非 $0$ 的雪糕棒，并将其减 $1$。这之后，如果最左边有连续的一些数...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments