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

Cube digit pairs 题号:90 难度: 40 中英对照

Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.

For example, the square number 64 could be formed:


In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.

For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.

However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.

In determining a distinct arrangement we are interested in the digits on each cube, not the order.

{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5}
{1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}

But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.

How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?


Solution

用长度为10的一个二进制数来表示一个立方体上出现的数字,例如0000111111表示集合{1,2,3,4,5,6}。 先枚举所有的1-1023之间的数字,判断它的二进制位上为1的数量是否为6,若为6则记录下来。 再对所有记录下来的数字,两层循环枚举两个数字,作为两个立方体的状态,判断当前状态是否可以表示所有的100以内的完全平方数,这里要对6和9的判定进行特判(考虑6和9可互用)。 利用一个vis数组来记录当前状态是否已经查询过,这里要注意两个立方体没有顺序之分,需要判定两次。

Code

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.PriorityQueue;

public final class p90 {
    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 public boolean a[]=new boolean[10],b[]=new boolean[10];
    static public final boolean check_6(int x){
    	return (((a[6]||a[9])&&b[x])
    			||((b[6]||b[9])&&a[x]));
    }
    static public final boolean check(int x,int y){
    	if(x==6||x==9) return check_6(y);
    	if(y==6||y==9) return check_6(x);
    	return ((a[x]&&b[y])
    			||(a[y]&&b[x]));
    }
    static public final boolean solve(int m,int n){
    	for(int i=0;i<10;i++)
    		a[i]=b[i]=false;
    	int index=0;
    	while(m!=0||n!=0){
    		a[index]=(m&1)!=0;
    		b[index++]=(n&1)!=0;
    		m>>=1;
    		n>>=1;
    	}
    	if(!check(0,1)) return false;
    	if(!check(0,4)) return false;
    	if(!check(0,9)) return false;
    	if(!check(1,6)) return false;
    	if(!check(2,5)) return false;
    	if(!check(3,6)) return false;
    	if(!check(4,9)) return false;
    	if(!check(6,4)) return false;
    	if(!check(8,1)) return false;
    	return true;
    }
    static public final int get(int n){
    	//计算二进制下1的个数
    	int res=0;
    	while(n!=0){
    		if((n&1)!=0) res++;
    		n>>=1;
    	}
    	return res;
    }
    
    
    static public String run(){
    	int statu[]=new int[1024],cnt=0;
    	boolean[] vis=new boolean[1024*1024+5];
    	for(int i=0;i<vis.length;i++) vis[i]=false;
    	for(int i=1;i<1024;i++){
    		if(get(i)==6)
    			statu[cnt++]=i;
    	}
    	int ans=0;
    	for(int i=0;i<cnt;i++) for(int j=0;j<cnt;j++){
    		if(solve(statu[i],statu[j])){
    			int x=statu[i]*1024+statu[j];
    			int y=statu[j]*1024+statu[i];
    			if(vis[x]||vis[y]) continue;
    			vis[x]=vis[y]=true;
    			ans++;
    		}
    	}
    	return Integer.toString(ans);
	}
}













1217
11ms