当前位置:首页 » Project Euler » 详细页

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.

Solution

直接暴力从1-9枚举4个不同的数字,将其从小到大的排列组成的字符串记为key值,将其可能得到的答案记载在key值下面(用一个映射结构,即Map类)。 要计算4个数字得到的答案,需要从加减乘除中枚举3个运算符,值得注意的是下列5个算式是不同的,需要单独判定。 $$a \quad ? \quad [ b \quad ? \quad ( c \quad ? \quad d ) ]$$ $$a \quad ? \quad [ ( c \quad ? \quad d ) \quad ? \quad b]$$ $$[ b \quad ? \quad ( c \quad ? \quad d ) ] \quad ? \quad a$$ $$[ ( c \quad ? \quad d ) \quad ? \quad b] \quad ? \quad a$$ $$(a \quad ? \quad b) \quad ? \quad (c \quad ? \quad d) $$ 其中$?$可能是任意的(不同或相同的)四则运算符。 最后,遍历所有的key值,将所有的正整数答案从小到大排列,依次扫描得到其“能连续表示”的最大值。这些最大值的最大值即为答案。

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)
			ans.get(key).add(res);
    }
    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>();
    		tmp.addAll(it.getValue());
    		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>();
    	for(int aa:a) b.add(aa);
    	Collections.sort(b);
    	String res="";
    	for(int bb:b) res+=bb;
    	return res;
    }
}
1258
99ms