http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11442&courseid=0
B: Nested Palindromes
Palindromes are numbers that read the same forwards and backwards. Your friend
Percy recently became interested in a special kind of palindrome that he calls a Nested
Palindrome. A Nested Palindrome meets three conditions:
The number is a palindrome.
Split the number in the middle. The first half of the digits of the number is also a
Nested Palindrome. If the number has an odd number of digits, don’t consider
the middle digit as part of the first half.
No two adjacent digits are the same.
Percy says that he has written a Nested Palindrome with no leading zeros on a slip of
paper. Next, Percy says that he has erased some of the digits in the number and
replaced those digits with question marks. He asks you to think about all possible
numbers, in increasing order, that can fill those digits and could possibly form the
number Percy wrote. Of course, Percy may not be telling the truth about having written
a Nested Palindrome in the first place.
Percy tells you that the number he wrote is the kth number of this potentially large list.
Your task is to find that kth number.
Input
There will be several test cases in the input. Each test case will consist of two lines. The
first line will contain an integer k (1≤k≤10
18
), which is the position in the ordered list you
must find. The second line contains a string of length 1 to 10,000, consisting only of
digits (‘0’ to ‘9’) and question marks (‘?’). Input is terminated by a line with a single 0.
Output
For each test case, output the Nested Palindrome that Percy is looking for. If that
number does not exist, or if the string cannot form a Nested Palindrome, output -1.
Output no spaces, and do not separate answers with blank lines.
2013 ACM ICPC Southeast USA Regional Programming Contest
Page 4 of 16 2 November, 2013
Sample Input
1
1?1
1
?3?
1
?1?
55
???
55
1?1
3
0?0
0
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=11000; int lenth[20],len,pos; int num[20],arr[20],NB[20],wei; bool flag,vis[20]; char str[maxn]; long long int pow9[20],cut,kth; void POW9() { pow9[0]=1; for(int i=1;i<=14;i++) pow9[i]=pow9[i-1]*9; } void dfs(int n,int limit) { if(flag) return ; if(n==wei) { cut--; if(cut==0LL) { flag=true; for(int i=0;i<wei;i++) { NB[i]=arr[i]; } } return ; } for(int i=0;i<=9;i++) { if(i==limit) continue; if(pow9[wei-n-1]<cut) { cut-=pow9[wei-n-1]; continue; } arr[n]=i; dfs(n+1,limit); } } void init() { POW9(); for(int i=0;i<15;i++) lenth[i]=(1<<i)-1; } void PT(int n) { if(n==-1) return ; PT(n-1); printf("%d",num[n]); PT(n-1); } int main() { init(); while(scanf("%I64d",&kth)!=EOF&&kth) { scanf("%s",str); len=strlen(str); pos=-1; memset(num,-1,sizeof(num)); memset(vis,false,sizeof(vis)); for(int i=1;i<15;i++) { if(lenth[i]==len) pos=i; } if(pos==-1) { puts("-1"); continue; } int nev=0; for(int i=0;i<pos;i++) { if(str[(1<<i)-1]!=‘?‘) { num[i]=str[(1<<i)-1]-‘0‘; vis[num[i]]=true; } else nev++; } if(num[0]==0) { puts("-1"); continue; } long long int maxleve=pow9[nev]; if(maxleve<kth) { puts("-1"); continue; } flag=false; if(num[0]==-1) ///a的值是未知,a不能是0,a不能是其他已知的数 其他数不能是a有9种选择 { maxleve/=9; int ath=1,a=-1; while(kth>maxleve) ath++,kth-=maxleve; for(int i=1;i<=9;i++) { if(vis[i]==0) { ath--; if(ath==0) { a=i; break; } } } if(a==-1) { puts("-1"); continue; } cut=kth;num[0]=a;wei=nev-1; dfs(0,num[0]); } else ///a的值已知,其他数不能是a有9种选择 { cut=kth;wei=nev; dfs(0,num[0]); } if(flag==false) { puts("-1"); continue; } int st=0; for(int i=0;i<pos;i++) { if(num[i]==-1) { num[i]=NB[st++]; } } PT(pos-1); putchar(10); } return 0; }
SERC2013 B Nested Palindromes,布布扣,bubuko.com
原文:http://blog.csdn.net/u012797220/article/details/21471097