UVA-12107(検索)
本題の主な難点は列挙された式が成立するかどうかを判断することである.
本人は1つの固定式列挙等号の左の変更可能な位置の値を採用してそれから積を生成して後の列と一致する時間が最悪10^4(前の4桁はすべて変更可能な位置)が成立するかどうかを判断する必要があります.
次に反復深さ探索列挙上限を主アルゴリズムとして,{
毎回ビット単位で決定します.
最後のコピー列の変更に特に注意してください.
}
本人は1つの固定式列挙等号の左の変更可能な位置の値を採用してそれから積を生成して後の列と一致する時間が最悪10^4(前の4桁はすべて変更可能な位置)が成立するかどうかを判断する必要があります.
次に反復深さ探索列挙上限を主アルゴリズムとして,{
毎回ビット単位で決定します.
最後のコピー列の変更に特に注意してください.
}
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<=(n);(i)++)
int Cmp(int* a,int f,int e,int s){
int ts = s,tts=s,cnt=0;
while(ts){
ts/=10; cnt++;
} if(cnt!=e-f+1) return 0;
for(int i=e;i>=f;i--){
int x = s%10;
if(x!=a[i]&&a[i]!=-1) return 0;
s/=10;
}
return 1;
}
int f[3],e[3],All = 0;
int judge(int* a,int* b,int fl){
if(fl==f[2]){
int c[2],cnt=0;
for(int i=0;i<=1;i++){
c[i] = 0;
for(int j=f[i];j<=e[i];j++){
c[i]=c[i]*10+b[j];
}
}
if(Cmp(a,f[2],e[2],c[0]*c[1])) All++;
if(All >= 2) return 0;
return 1;
}
if(a[fl]!=-1){
b[fl] = a[fl];
if(!judge(a,b,fl+1)) return 0;
}
else{
int st = 0;
if(fl==f[0]||fl==f[1]) st++;
for(int i=st;i<=9;i++){
b[fl] = i;
if(!judge(a,b,fl+1)) return 0;
}
}
return 1;
}
int Judge(int* a){
All = 0;
int b[8];
if(judge(a,b,0)){
if(All == 0) return 0;
if(All == 1) return 1;
}
return 0;
}
const int N = 8;
int A[N],n;
void copy(int* a,int* b){
for(int i=0;i<n;i++) a[i]=b[i];
}
void print_ans(int* a){
for(int i=0;i<3;i++){
if(i) printf(" ");
for(int j=f[i];j<=e[i];j++){
if(a[j]!=-1) printf("%d",a[j]);
else printf("*");
}
}
printf("
");
}
int dfs(int* a,int p,int d,int maxd){
if(d==maxd){
for(int i=p;i<n;i++) a[i] = A[i];
if(Judge(a)){
print_ans(a);
return 1;
}
return 0;
}
for(int i = -1;i<=9;i++){
if(A[p] == i && n-p-1<maxd-d) continue;
if((p==f[0]||p==f[1]||p==f[2])&&!i) continue;
int add = 1;
if(A[p] == i) add--;
a[p] = i;
if(dfs(a,p+1,d+add,maxd)) return 1;
}
return 0;
}
int main()
{
char s[3][N];
int kase=1;
while(scanf("%s",s[0])!=EOF&&s[0][0]!='0'){
scanf("%s %s",s[1],s[2]);
n = 0;
int add = 0;
for(int i=0;i<3;i++){
f[i]= add ;
add += strlen(s[i]);
e[i] = add - 1;
for(int j=0;s[i][j]!=0;j++){
A[n++]=s[i][j]-(s[i][j]=='*' ? ('*'+1):'0');
}
}
printf("Case %d: ",kase++);
if(Judge(A)){
print_ans(A);
continue;
}
int b[N];
for(int maxd = 1;;maxd++){
copy(b,A);
if(dfs(b,0,0,maxd)) break;
}
}
return 0;
}
//* * 56