OpenJudge

06:数字变换

总时间限制:
1000ms
内存限制:
65536kB
描述

给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换

1. 交换相邻的两个数字

2. 将一个数字加1。如果加1后大于9,则变为0

3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。

最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。

输入
有最多 100,000 组数据
每组数据就是包含5个数字的字符串
输出
对每组数据,输出将"12345"变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1
样例输入
12435
99999
12374
样例输出
1
-1
3
提示
由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。

建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。

然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。
来源
Guo Wei

01答案需要使用long long表示
05表达式期望值,Ai小于2^20

全局题号
15279
提交次数
619
尝试人数
191
通过人数
77