# CF：Jokewithpermutation

Jokewithpermutation

Input ?le: joke.in
Output ?le: joke.out
Joey had saved a permutation of integers from 1 to n in a text ?le. All the numbers were written as
Then Joe made a practical joke on her: he removed all the spaces in the ?le.
Help Joey to restore the original permutation after the Joe’s joke!
Input
The input ?le contains a single line with a single string — the Joey’s permutation without spaces.
The Joey’s permutation had at least 1 and at most 50 numbers.
Output
Write a line to the output ?le with the restored permutation. Don’t forget the spaces!
If there are several possible original permutations, write any one of them.
Sample input and output
joke.in

4111109876532

joke.out

4 1 11 10 9 8 7 6 5 3 2

```#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[55];
int flag[31];
int x[31];
int len,n;
void dfs(int i,int t);
int main()
{
freopen("joke.in","r",stdin);
freopen("joke.out","w",stdout);
int i;
memset(s,0,sizeof(s));
memset(x,0,sizeof(x));
memset(flag,0,sizeof(flag));
while(scanf("%s",s)!=EOF)
{
len=strlen(s);
if(len<10) //优化，如果都是十以内
{
n=len;
for(i=0; i<n-1; i++)
printf("%c ",s[i]);
printf("%c\n",s[i]);
}
else
{
n=(len-11)/2+10;
//cout<<len<<" "<<n<<endl;
dfs(0,0);
for(i=0; i<n-1; i++)
printf("%d ",x[i]);
printf("%d\n",x[i]);
}
memset(s,0,sizeof(s));
memset(x,0,sizeof(x));
memset(flag,0,sizeof(flag));
}
return 0;
}
void dfs(int i,int t)
{
if(i==len) return;
if((i+1)<len&&s[i+1]==‘0‘) //注意10,20这两个数据，比较特殊
{
flag[(s[i]-48)*10]=1;
x[t]=(s[i]-48)*10;
dfs(i+2,t+1);
flag[(s[i]-48)*10]=1;
}
else if(flag[s[i]-48]==0)
{
flag[s[i]-48]=1;
//cout<<s[i]-48<<" 1"<<endl;
x[t]=s[i]-48;
dfs(i+1,t+1);
flag[s[i]-48]=0;
//cout<<s[i]-48<<" 0"<<endl;
}
else if((s[i]-48)<3&&(i+1)<len&&flag[(s[i]-48)*10+(s[i+1]-48)]==0)
{
flag[(s[i]-48)*10+(s[i+1]-48)]=1;
//cout<<(s[i]-48)*10+(s[i+1]-48)<<" 1"<<endl;
x[t]=(s[i]-48)*10+(s[i+1]-48);
dfs(i+2,t+1);
flag[(s[i]-48)*10+(s[i+1]-48)]=0;
//cout<<(s[i]-48)*10+(s[i+1]-48)<<" 0"<<endl;
}
return;
}```
View Code

CF：Jokewithpermutation

(0)
(0)