2013
11-09

# 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;
}
}
}
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
不知道题目例子是怎么得出来的