#P1076. 「合」数

「合」数

题目描述

给你一个数 nn,每次你可以对 nn 执行下列操作:如果 nn 从左到右数第 ii 位的数和第 i+1i+1 位的数之和小于 10100<i<n0<i<n),则可以对这两位数进行「合」操作,将这两位数合成一位数,例如,数 36473647 可以对第 11 位和第 22 位进行「合」操作,这样原数就变成了 947947。你还可以任意使用魔法,可以在任意一次操作前,将 nn 这个数变成 nn',不过变化的要求是这两个数的各位数字之和必须相同,位数也必须相同,例如你可以将 2727 变成 3636,但不能变成 20720799。你的任务是,判断能否用有限次的「合」操作和任意次魔法机会,让初始数 xx 变为目标数 yy,如果可以,输出最少需要使用的「合」操作的次数;如果不可以,输出 NO\text{NO}

输入格式

一行两个整数 xxyy,即初始数和目标数。

输出格式

一行。如果可以让初始数 xx 变为目标数 yy,输出最少需要使用的「合」操作的次数;否则输出 NO\text{NO}

4182 87
2
544 49
1
976 166
NO

样例解释

对于样例 11,操作如下:418249276278874182 \to 492 \to 762 \to 78 \to 87,共 22 步(魔法不算)。

对于样例 22,操作如下:54443649544 \to 436 \to 49,共 11 步。

对于样例 33976976 无论如何操作都无法变成 166166

数据范围

x|x| 表示 xx 的位数。

测试点 11 22 33 44 55 66 77 88 99 1010
x=|x|= 55 1010 1818 3030 100100 500500 10001000 60006000 1500015000 5000050000