🐷大肚肚
CF-44H普及+/提高

电话号码

2.0s💾 256MB

📋 题目描述

给你一个电话号码的各位数字 a1,a2,...,ana_1,a_2,...,a_n,根据给定的规则生成一个号码 b1,b2,...,bnb_1,b_2,...,b_nbbaa 不能完全相同) 。生成的规则如下:第一个数字 b1b_1 是从 090-9 中任选的一个, 当 i>1i>1 时, biai+bi12b_{i}\leftarrow\left\lfloor\frac{a_i+b_{i-1}}{2}\right\rfloor 或者 biai+bi12b_{i}\leftarrow\left\lceil\frac{a_i+b_{i-1}}{2}\right\rceil ,请你计算可以生成多少个新的号码。

📥 输入格式

仅有一行,是一个由 0099 的数字组成的非空序列,长度不超过 5050,表示给定的电话号码 a1,a2,...,ana_1,a_2,...,a_n

📤 输出格式

仅有一个整数,表示按照给定的规则可以生成的电话号码的个数。

📝 样例 1

输入
12345
输出
48

📝 样例 2

输入
09
输出
15

💡 题目讲解

1

理解题意

看一个最简单的例子:原号码 "09"(只有两位:a1=0,a2=9a_1=0, a_2=9)。

规则 ①b1b_1 随便选,0~9 都行。比如选 b1=2b_1=2

规则 ②b2b_2 怎么算?把 b1b_1a2a_2 加起来除以 2: b2=b1+a22=2+92=5.5b_2 = \frac{b_1 + a_2}{2} = \frac{2 + 9}{2} = 5.5

5.5 不是整数!可以向下取整 5.5=5\lfloor 5.5 \rfloor = 5,也可以向上取整 5.5=6\lceil 5.5 \rceil = 6

b1=2b_1=2 时,b2b_2 可以是 56——分叉了! 🌿

再试试 b1=3b_1=33+9=123+9=1212÷2=612 \div 2 = 6 是整数。两种取整结果都是 6 → 不分叉

💡 规律:b1+a2b_1+a_2奇数 → 分叉(差 1);偶数 → 不分叉。

b₁=2(11÷2=5.5 → 分叉)2⌊⌋5⌈⌉6b₁=3(12÷2=6 → 不分叉)3÷2=66b₁b₂b₁b₂规律:和是奇数→分叉(差 1);偶数→不分叉
1 / 6