#P1132. 数字生成游戏

数字生成游戏

题目描述

小明完成了这样一个数字生成游戏,对于一个不包含00的数字ss来说,有以下33种生成新的数的规则:

  1. ss的任意两位对换生成新的数字,例如143143可以生成314,413,134314,413,134

  2. ss的任意一位删除生成新的数字,例如143143可以生成14,13,4314,13,43

  3. ss的相邻两位之间si,si+1s_i,s_{i + 1}之间插入一个数字x,x需要满足si<x<si+1s_i<x<s_{i + 1}。例如143143可以生成1243,13431243,1343,但是不能生成1143,15431143,1543等。

现在小明想知道,在这个生成法则下,从ss开始,每次生成一个数,可以用然后用新生成的数生成另外一个数,不断生成直到生成tt至少需要多少次生成操作。

另外,小明给规则33又加了一个限制,即生成数的位数不能超过初始数ss的位数。若ss143143,那么1243124313431343都是无法生成的;若ss14431443,那么可以将ss删除变为143143,再生成1243124313431343

输入格式

第一行包含11个正整数,为初始数字ss

第二行包含一个正整数mm,为询问个数。

接下来mm行,每行一个整数tttt不包含00),表示询问从ss开始不断生成数字到tt最少要进行多少次操作。任两个询问独立,即上一个询问生成过的数到下一个询问都不存在,只剩下初始数字ss

输出格式

mm行,每行一个正整数,对每个询问输出最少操作数,如果无论如果无论也变换不成,则输出1-1

143
3
134
133
32
1
-1
4

提示

143143 ->134 134

133133无法得到

143143 -> 1313 -> 123123 ->23 23 ->32 32

对于20%20\%的数据,s<100s < 100
对于40%40\%的数据,s<1000s < 1000
对于40%40\%的数据,m<10m < 10
对于60%60\%的数据,s<10000s < 10000
对于100%100\%的数据,s<100000,m50000s < 100000,m ≤ 50000