{"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$ 中的数字。你需要使该数字串**不存在**任何一个非空子串满足这个子串表示的数字是 $2^k(k\\in \\N)$ 即 $2$ 的任意**非负整数**次幂，请你求出最少的操作次数。\n\n## Input\n\n一行一个数字串 $s$。\n\n## Output\n\n一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n对于样例 $1$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $2,4,8$，将 $s$ 修改为 $5963$ 是最优解之一。\n\n对于样例 $2$，满足表示的数是 $2$ 的非负整数次幂的 $s$ 的非空子串有 $1,4,16,64$，将 $s$ 修改为 $666$ 是最优解之一。\n\n### 数据规模与约定\n**本题采用捆绑测试。**\n\n令 $n=|s|$。\n\n| $\\text{Subtask}$ | $n\\le $ | 分值 |\n| :----------: | :----------: | :----------: |\n| $1$ | $4$ | $10$ |\n| $2$ | $8$ | $10$ |\n| $3$ | $17$ | $20$ |\n| $4$ | $10^3$ | $20$ |\n| $5$ | $10^6$ | $40$ |\n\n对于 $100\\%$ 的数据，$1\\le n\\le 10^6$，$s$ 由 $1\\sim 9$ 的数字组成。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10571","tags":["2024","洛谷原创","O2优化","洛谷月赛","Ad-hoc"],"sample_group":[["2468","3"],["164","2"],["65535","0"]],"created_at":"2026-03-03 11:09:25"}}