Aizu Online Judge 1161 Verbal Arithmetic

■1161 Verbal Arithmetic

非常に汚い探索による解法．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. // AC  
10. public class Main{  
11.   
12.  Scanner sc=new Scanner(System.in);  
13.   
14.  int INF=1<<28;  
15.  double EPS=1e-9;  
16.   
17.  int n;  
18.  String[] ss;  
19.   
20.  void run(){  
21.   for(;;){  
22.    n=sc.nextInt();  
23.    if(n==0){  
24.     break;  
25.    }  
26.    ss=new String[n];  
27.    for(int i=0; i<n; i++){  
28.     ss[i]=sc.next();  
29.    }  
30.    solve();  
31.   }  
32.  }  
33.   
34.  int size;  
35.  int[] cs;  
36.  int[] map;  
37.  boolean[] used;  
38.  int ans;  
39.   
40.  void solve(){  
41.   int[] a=new int[256];  
42.   fill(a, -1);  
43.   size=0;  
44.   for(String s : ss){  
45.    for(int i=0; i<s.length(); i++){  
46.     if(a[s.charAt(i)]==-1){  
47.      size++;  
48.      a[s.charAt(i)]=INF;  
49.     }  
50.     a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);  
51.    }  
52.   }  
53.   cs=new int[size];  
54.   for(int k=0, i=0; i<256; i++){  
55.    if(a[i]>=0){  
56.     cs[k++]=i+1000*a[i];  
57.    }  
58.   }  
59.   sort(cs);  
60.   
61.   used=new boolean[10];  
62.   map=new int[256];  
63.   fill(map, -1);  
64.   ans=0;  
65.   dfs(0);  
66.   println(""+ans);  
67.  }  
68.   
69.  void dfs(int k){  
70.   if(k==size){  
71.    if(ok(8)){  
72.     ans++;  
73.    }  
74.    return;  
75.   }  
76.   for(int i=0; i<10; i++){  
77.    if(!used[i]){  
78.     used[i]=true;  
79.     map[cs[k]%1000]=i;  
80.     if(ok(cs[k]/1000)){  
81.      dfs(k+1);  
82.     }  
83.     map[cs[k]%1000]=-1;  
84.     used[i]=false;  
85.    }  
86.   }  
87.  }  
88.   
89.  boolean ok(int d){  
90.   int sum=0;  
91.   for(int j=0; j<n; j++){  
92.    if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){  
93.     return false;  
94.    }  
95.    int num=0;  
96.    for(int i=max(0, d-ss[j].length()); i<d; i++){  
97.     num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];  
98.    }  
99.    if(j==n-1){  
100.     sum-=num;  
101.    }else{  
102.     sum+=num;  
103.    }  
104.   }  
105.   int mod=1;  
106.   for(int i=0; i<d; i++){  
107.    mod*=10;  
108.   }  
109.   return sum%mod==0;  
110.  }  
111.   
112.  void debug(Object... os){  
113.   System.err.println(Arrays.deepToString(os));  
114.  }  
115.   
116.  void print(String s){  
117.   System.out.print(s);  
118.  }  
119.   
120.  void println(String s){  
121.   System.out.println(s);  
122.  }  
123.   
124.  public static void main(String[] args){  
125.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
126.   new Main().run();  
127.  }  
128. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int n;
 String[] ss;

 void run(){
  for(;;){
   n=sc.nextInt();
   if(n==0){
    break;
   }
   ss=new String[n];
   for(int i=0; i<n; i++){
    ss[i]=sc.next();
   }
   solve();
  }
 }

 int size;
 int[] cs;
 int[] map;
 boolean[] used;
 int ans;

 void solve(){
  int[] a=new int[256];
  fill(a, -1);
  size=0;
  for(String s : ss){
   for(int i=0; i<s.length(); i++){
    if(a[s.charAt(i)]==-1){
     size++;
     a[s.charAt(i)]=INF;
    }
    a[s.charAt(i)]=min(a[s.charAt(i)], s.length()-1-i);
   }
  }
  cs=new int[size];
  for(int k=0, i=0; i<256; i++){
   if(a[i]>=0){
    cs[k++]=i+1000*a[i];
   }
  }
  sort(cs);

  used=new boolean[10];
  map=new int[256];
  fill(map, -1);
  ans=0;
  dfs(0);
  println(""+ans);
 }

 void dfs(int k){
  if(k==size){
   if(ok(8)){
    ans++;
   }
   return;
  }
  for(int i=0; i<10; i++){
   if(!used[i]){
    used[i]=true;
    map[cs[k]%1000]=i;
    if(ok(cs[k]/1000)){
     dfs(k+1);
    }
    map[cs[k]%1000]=-1;
    used[i]=false;
   }
  }
 }

 boolean ok(int d){
  int sum=0;
  for(int j=0; j<n; j++){
   if(map[ss[j].charAt(0)]==0&&ss[j].length()>1){
    return false;
   }
   int num=0;
   for(int i=max(0, d-ss[j].length()); i<d; i++){
    num=num*10+map[ss[j].charAt(ss[j].length()-d+i)];
   }
   if(j==n-1){
    sum-=num;
   }else{
    sum+=num;
   }
  }
  int mod=1;
  for(int i=0; i<d; i++){
   mod*=10;
  }
  return sum%mod==0;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}