[JRKSJ R8] 三七二十一

Luogu

IDLGP10571

Time1000ms

Memory512MB

DifficultyP3

2024洛谷原创O2优化洛谷月赛Ad-hoc

给你一个由 $1\sim 9$ 的数字组成的数字串 $s$。定义一个数字串 $s$ 表示的数为将其看作十进制数得到的数。形式化地说，长为 $n$ 的数字串 $s$ 表示的数是 $\sum_{i=1}^n 10^{n-i}s_i$。你可以对这个数字串执行若干次操作，每次操作中你可以选定一个位置 $1\le p\le n$ 并将 $s_p$ 修改为任意 $1\sim 9$ 中的数字。你需要使该数字串**不存在**任何一个非空子串满足这个子串表示的数字是 $2^k(k\in \N)$ 即 $2$ 的任意**非负整数**次幂，请你求出最少的操作次数。 ## Input 一行一个数字串 $s$。 ## Output 一行一个整数表示答案。 [samples] ## Note ### 样例解释对于样例 $1$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $2,4,8$，将 $s$ 修改为 $5963$ 是最优解之一。对于样例 $2$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $1,4,16,64$，将 $s$ 修改为 $666$ 是最优解之一。 ### 数据规模与约定 **本题采用捆绑测试。** 令 $n=|s|$。 | $\text{Subtask}$ | $n\le $ | 分值 | | :----------: | :----------: | :----------: | | $1$ | $4$ | $10$ | | $2$ | $8$ | $10$ | | $3$ | $17$ | $20$ | | $4$ | $10^3$ | $20$ | | $5$ | $10^6$ | $40$ | 对于 $100\%$ 的数据，$1\le n\le 10^6$，$s$ 由 $1\sim 9$ 的数字组成。

Samples

Input #1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[JRKSJ R8] 三七二十一",
    "description": {
      "content": "给你一个由 $1\\sim 9$ 的数字组成的数字串 $s$。定义一个数字串 $s$ 表示的数为将其看作十进制数得到的数。形式化地说，长为 $n$ 的数字串 $s$ 表示的数是 $\\sum_{i=1}^n  10^{n-i}s_i$。 你可以对这个数字串执行若干次操作，每次操作中你可以选定一个位置 $1\\le p\\le n$ 并将 $s_p$ 修改为任意 $1\\sim 9$ 中的数字。你需要使该数",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10571"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给你一个由 $1\\sim 9$ 的数字组成的数字串 $s$。定义一个数字串 $s$ 表示的数为将其看作十进制数得到的数。形式化地说，长为 $n$ 的数字串 $s$ 表示的数是 $\\sum_{i=1}^n  10^{n-i}s_i$。\n\n你可以对这个数字串执行若干次操作，每次操作中你可以选定一个位置 $1\\le p\\le n$ 并将 $s_p$ 修改为任意 $1\\sim 9$ 中的数字。你需要使该数...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments