数字生成游戏

数字生成游戏

题目描述

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

1. 将 的任意两位对换生成新的数字，例如 可以生成 ；
2. 将 的任意一位删除生成新的数字，例如 可以生成 ；
3. 在 的相邻两位之间 之间插入一个数字 ， 需要满足 。例如 可以生成 ，但是不能生成 等。

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

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

输入格式

第一行包含 个正整数，为初始数字 。

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

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

输出格式

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

样例 #1

样例输入 #1

143
3
134
133
32

样例输出 #1

1
-1
4

提示

样例解释

无法得到

数据范围

对于 的数据，；
对于 的数据，；
对于 的数据，；
对于 的数据，；
对于 的数据，。

#include<queue>
#include<cstdio>
#include<cstring>
main() {}
int dist[10000000];
struct in{int x,s;}u;
std::queue<in>que;
void tie(int \*a,int <h,int x) {
    lth=0;//解码 
    while(x) a[lth++]=x%10,x/=10;
}
int dis(int \*a,int lth) {
    int x=0;//还原 
    while(lth) x\*=10,x+=a[--lth];
    return x;
}
void add(int \*a,int lth,int step) {
    int tmp;//o(n)的add操作 
    a[lth]=a[lth-1];
    for(int i=lth-1;i>=1;i--) {
        for(int j=a[i+1]+1;j<a[i-1];j++) {
            a[i]=j;
            tmp=dis(a,lth+1);
            if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step});
        }
        a[i]=a[i-1];
    }
}
void del(int \*a,int lth,int step) {
    int tmp,out=0;//o(n)的delete操作 
    for(int i=lth-1;i>=0;i--) {
        out^=a[i]^=out^=a[i];
        tmp=dis(a,lth-1);
        if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step});
    }
}
void swa(int \*a,int lth,int step) {
    int tmp;//o(n\*(n-1)/2)的swap操作 
    for(int i=0;i<lth;i++) {
        for(int j=i+1;j<lth;j++) {
            if(a[i]==a[j]) continue;
            a[i]^=a[j]^=a[i]^=a[j];
            tmp=dis(a,lth);
            if(dist[tmp]==-1) dist[tmp]=step,que.push((in){tmp,step});
            a[i]^=a[j]^=a[i]^=a[j];
        }
    }
}
int entry() {
    memset(dist,-1,sizeof dist);
    int a[10],lth,lmt,x;
    scanf("%d",&x);
    tie(a,lmt,x),dist[x]=0;
    que.push((in){x,0});
    while(!que.empty()) {
        u=que.front();
        que.pop();
        memset(a,0,sizeof a);
        tie(a,lth,u.x);
        if(lth>1) del(a,lth,u.s+1),tie(a,lth,u.x);
        if(lth>1) swa(a,lth,u.s+1),tie(a,lth,u.x);
        if(lth<lmt) add(a,lth,u.s+1);
    }
    scanf("%d",&lmt);
    while(lmt--) {
        scanf("%d",&x);
        printf("%d\n",dist[x]);
    }
    return 0;
}
int aptal=entry();