P1132 数字生成游戏

    • 168通过
    • 546提交
  • 题目提供者
  • 评测方式 云端评测
  • 标签 搜索
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    1. 将$s$的任意两位对换生成新的数字,例如$143$可以生成$314,413,134$;

    2. 将$s$的任意一位删除生成新的数字,例如$143$可以生成$14,13,43$

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

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

    另外,小明给规则$3$又加了一个限制,即生成数的位数不能超过初始数$s$的位数。若$s$是$143$,那么$1243$与$1343$都是无法生成的;若$s$为$1443$,那么可以将$s$删除变为$143$,再生成$1243$或$1343$。

    输入输出格式

    输入格式:

    第一行包含$1$个正整数,为初始数字$s$。

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

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    143
    3
    134
    133
    32
    
    输出样例#1: 复制
    1
    -1
    4
    

    说明

    $143$ ->$ 134$

    $133$无法得到

    $143$ -> $13$ -> $123$ ->$ 23 $->$ 32$

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。