### Arithmetic expressions题号：93 难度： 35 中英对照

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

8 = (4 * (1 + 3)) / 2
14 = 4 * (3 + 1 / 2)
19 = 4 * (2 + 3) − 1
36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

### Code

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;

public final class p93 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static HashMap<String,HashSet<Integer>> ans;
static public void check(double tmp,String key){
int res=(int)(tmp+1e-7);//判断res是不是整数
if(Math.abs(res-tmp)<1e-7 && res>0)
}
static public String run(){
ans=new HashMap<String,HashSet<Integer>>();
int[] a=new int[4];
for(a[0]=1;a[0]<=9;a[0]++)
for(a[1]=1;a[1]<=9;a[1]++) if(a[1]!=a[0])
for(a[2]=1;a[2]<=9;a[2]++) if(a[2]!=a[1] && a[2]!=a[0])
for(a[3]=1;a[3]<=9;a[3]++) if(a[3]!=a[2] && a[3]!=a[1] && a[3]!=a[0]){
String key=toString(a);
if(!ans.containsKey(key)) ans.put(key,new HashSet<Integer>());
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
for(int k=0;k<4;k++){
check( cal(a[0],i,cal(a[1],j,cal(a[2],k,a[3]))) ,key);
check( cal(a[0],i,cal(cal(a[2],k,a[3]),j,a[1])) ,key);
check( cal(cal(a[1],j,cal(a[2],k,a[3])),i,a[0]) ,key);
check( cal(cal(cal(a[2],k,a[3]),j,a[1]),i,a[0]) ,key);
check( cal(cal(a[0],i,a[1]),j,cal(a[2],k,a[3])) ,key);
}
}
String ANS="";
int max=0;
for(HashMap.Entry<String,HashSet<Integer>> it:ans.entrySet()){
ArrayList<Integer> tmp=new ArrayList<Integer>();
Collections.sort(tmp);
int cnt=0;
for(int x:tmp){
if(x==cnt+1) cnt++;
else break;
}

if(cnt>max){
max=cnt;
ANS=it.getKey();
}
}
return ANS;
}
static public final double cal(double a,int op,double b){
if(op==0) return a+b;
if(op==1) return a-b;
if(op==2) return a*b;
return a/b;
}
static public final String toString(int a[]){
ArrayList<Integer> b=new ArrayList<Integer>();
}
1258