首页 > 专题系列 > Java解POJ > POJ 1165 The Primes [解题报告] Java
2013
11-09

POJ 1165 The Primes [解题报告] Java

The Primes

问题描述 :


|---|---|---|---|---|
| 1 | 1 | 3 | 5 | 1 |
|---|---|---|---|---|
| 3 | 3 | 2 | 0 | 3 |
|---|---|---|---|---|
| 3 | 0 | 3 | 2 | 3 |
|---|---|---|---|---|
| 1 | 4 | 0 | 3 | 3 |
|---|---|---|---|---|
| 3 | 3 | 3 | 1 | 1 |
|---|---|---|---|---|
(Figure 1)



Figure 1 shows a square. Each row, each column and the two diagonals can be read as a five digit prime number. The rows are read from left to right. The columns are read from top to bottom. Both diagonals are read from left to right. Write a program that constructs such squares:
  • The prime numbers must have the same digit sum (11 in the example).
  • The digit in the top left-hand corner of the square is pre-determined (1 in the example).
  • A prime number may be used more than once in the same square.
  • If there are several solutions, all must be presented.
  • A five digit prime number cannot begin with zeros, ie 00003 is NOT a five digit prime number.

输入:

Your program is to read from standard input. First the digit sum of prime numbers and then the digit in the top left-hand corner of the square. The file contains two lines. There will always be a solution to the given test data.

输出:

Your program is to write to standard output. Output five lines for each solution found, where each line in turn consists of a five digit prime number. The solutions are sorted by the prime in the first row, then by the prime in the second row,etc. Output a blank line after each solution.

样例输入:

11
1

样例输出:

11351
14033
30323
53201
13313

11351
33203
30323
14033
33311

13313
13043
32303
50231
13331

解题代码:

//* @author: 
import java.util.*;
public class Main {
 public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  int sum=in.nextInt();
  int lefttop=in.nextInt();
  cnt=new int[11][11][11][11][11];
  for (int i = 0; i < cnt.length; i++) {
   for (int j = 0; j < cnt.length; j++) {
    for (int k = 0; k < cnt.length; k++) {
	for (int l = 0; l < cnt.length; l++) {
	  Arrays.fill(cnt[i][j][k][l], 0);
	}
    }
   }
  }
  for (int i = 10000; i < 100000; i++) {
    if(isPrime(i)&&dsum(i)==sum)
    {
	int[]x=new int[]{i/10000,i%10000/1000,i%1000/100,i%100/10,i%10};
	for (int j = 0; j < 1<< 5; j++) {
	  int[]y=new int[]{10,10,10,10,10};
	  for (int k = 0; k < 5; k++) {
	   int mark=1<< k;
	   mark&=j;
	   if(mark==0)
	   {
		y[k]=x[k];
	    }
	  }
	cnt[y[0]][y[1]][y[2]][y[3]][y[4]]++;
       }
      }
    }
    sq=new int[5][5];
    for (int[] is : sq) {
	 Arrays.fill(is, 10);
    }
    sq[0][0]=lefttop;
    list=new int[][]{{2,2},{0,4},{1,1},{1,3},{3,1},{3,3},{4,0},{4,4},
      {0,1},{0,2},{0,3},{1,0},{1,2},{1,4},{2,0},{2,1},{2,3},{2,4},{3,0},{3,2},{3,4},{4,1},{4,2},{4,3}};
    res=new ArrayList< Res>();
    dfs(0,24);
    Collections.sort(res);
    for (int i = 0; i < res.size(); i++) {
	for (int j = 0; j < 5; j++) {
	   System.out.println(res.get(i).r[j]);
	}
	System.out.println();
     }
    }
	
  static class Res implements Comparable< Res>
  {
    int r[];
		
    @Override
    public int compareTo(Res o) {
	if(r[0]==o.r[0])
       {
	   if(r[1]==o.r[1])
	   {
	     if(r[2]==o.r[2])
	     {
		if(r[3]==o.r[3])
		 {
		  return r[4]-o.r[4];
		  }
		else return r[3]-o.r[3];
	      }
	      else return r[2]-o.r[2];
	    }
	    else return r[1]-o.r[1];
	   }
	 else return r[0]-o.r[0];
     }

 public Res(int[] r) {
	super();
	this.r = r;
  }
}
	
 static int[][]sq;
 static int[][]list;
 static int[][][][][]cnt;
 static ArrayList< Res> res;
	
 static void dfs(int i,int n)
 {
   if(i==n)
    {
	int[]r=new int[]{0,0,0,0,0};
	for (int j = 0; j < 5; j++) {
	  for (int k = 0,l=10000; k < 5; k++,l/=10) {
	    r[j]+=sq[j][k]*l;
	  }
	}
	res.add(new Res(r));
     }
    else
    {
	int x=list[i][0],y=list[i][1];
	if(sq[x][y]!=10)dfs(i+1,n);
	else
	{
	  for (int j = 0; j < 10; j++,sq[x][y]=10) {
	   sq[x][y]=j;
	   if(cnt[sq[x][0]][sq[x][1]][sq[x][2]][sq[x][3]][sq[x][4]]==0)continue;
	   if(cnt[sq[0][y]][sq[1][y]][sq[2][y]][sq[3][y]][sq[4][y]]==0)continue;
	   if(x==y&&cnt[sq[0][0]][sq[1][1]][sq[2][2]][sq[3][3]][sq[4][4]]==0)continue;
	   if(x+y==4&&cnt[sq[4][0]][sq[3][1]][sq[2][2]][sq[1][3]][sq[0][4]]==0)continue;
		dfs(i+1,n);
	   }
	  }
     }
    }
	
  static int dsum(int i)
   {
	return i/10000+i%10000/1000+i%1000/100+i%100/10+i%10;
   }

   static boolean isPrime(int number)
    {
    	if (number < 2) return false;
    	if (number == 2) return true;
    	if (number % 2 == 0) return false;
    	for (int i = 3; i * i <= number; i += 2)
    		if (number % i == 0) return false;
    	return true;
    }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的