### 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?

### Code

import java.io.BufferedReader;
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