2013
12-12

# Number Game

Background

Christiane and Matthias are playing a new game, the Number Game. The rules of the Number Game are:

Christian and Matthias take turns in choosing integer numbers greater than or equal to 2. The following rules restrict the set of numbers which may be chosen:

R1 A number which has already been chosen by one of the players or a multiple of such a number cannot be chosen. (A number z is a multiple of a number y if z can be written as y * x and x is a positive integer.)

R2 A sum of two such multiples cannot be chosen either.

R3 For simplicity, a number which is greater than 20 cannot be chosen either. This enables a lot more NPCs (Non-Personal-Computers) to play this game.

The player who cannot choose any number anymore looses the Number Game.

Here is an example: Matthias starts by choosing 4. Then Christiane is not allowed to choose 4, 8, 12, etc. Let us assume her move is 3. Now, the numbers 3, 6, 9, etc. are excluded, too; furthermore, numbers like: 7 = 3 + 4, 10 = 2 * 3 + 4, 11 = 3 + 2 * 4, 13 = 3 * 3 + 4, . . . are not available. So, in fact, the only numbers left are 2 and 5. Matthias now says 2. Since 5 = 2 + 3 is now forbidden, too, he wins because there is no number for Christiane’s move left.

Your task is to write a program which will help to play the Number Game. In general, i.e., without rule R3, this game may go on forever. However, with rule R3, it is possible to write a program that finds a strategy to win the game.

Problem

Given a game situation (a list of numbers which are not yet forbidden), your program should output all winning moves. A winning move is a move by which the player whose turn it is can force a win no matter what the other player will do. Now we define these terms more formally:

A loosing position is a position in which either

1. all numbers are forbidden, or

2. no winning move exists.

A winning position is a position in which a winning move exists.

A winning move is a move after which the position is a loosing position.

The first line contains the number of scenarios.

The input for each scenario describes a game position. It begins with a line containing the number a, 0 <= a < 20 of numbers which are still available. Next follows a single line with the a numbers still available, separated by single blanks.

You may assume that all game positions in the input could really occur in the Number Game (for example, if 3 is not in the list of numbers available, 6 will not be, either).

The output for each scenario begins with a line containing "Scenario #i:" where i is the number of the scenario starting at 1. In the next line either print "There is no winning move." if this is true for the position of the current scenario, or "The winning moves are: w1 w2 . . . wk." where the wi are all the winning moves, in ascending order, separated by single blanks. The output for each scenario should be followed by a blank line.

2
1
2
2
2 3

Scenario #1:
The winning moves are: 2.

Scenario #2:
There is no winning move.

import java.io.*;
import java.util.*;
public class Main {
public static boolean mark[];
public static Integer a[];
public static boolean boo;
public static int edge,sum;
public static int n,m;
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
PrintWriter pw=new PrintWriter( new BufferedOutputStream(System.out),true);
n=sc.nextInt();
for(int i=0;i<n;i++){

m=sc.nextInt();

boo=false;
mark=new boolean[m];
a=new Integer[m];
sum=0;
edge=0;
for(int j=0;j<m;j++){
a[j]=sc.nextInt();
sum+=a[j];
}
Arrays.sort(a,new Comparator<Integer>(){//排序
public int compare(Integer o1, Integer o2) {
return o1>o2?-1:1;//按降序排序
}

});
edge=sum>>2;//右一位除以2
if(sum%4==0&&edge>=a[0]){
DFS(0,0,0);
if(boo)
pw.println("yes");
else
pw.println("no");
}else{
pw.println("no");
}
}

}
// 第一个变量是有几条边，第二个变量是每次循环边长的大小， 第三个变量是第几个元素
public static void DFS(int length,int size,int index){
//如果为真就返回
if(boo)
return;
//等于四条边就退出循环
if(length==4){
boo=true;
}
if(size==edge){
DFS(length+1,0,length+1);
}
else{
for(int i=index;i<m;i++){
if(!mark[i]&&size+a[i]<=edge){
mark[i]=true;
DFS(length,size+a[i],i+1);
mark[i]=false;//回溯
}
}
}
}
}
import java.io.*;
import java.util.*;
public class Main {
public static int n,m,sum,edge;
public static boolean mark[];
public static int a[];
public static void main(String[] args) {
Scanner sc=new Scanner(new BufferedInputStream(System.in));
PrintWriter pw=new PrintWriter(new BufferedOutputStream(System.out),true);
n=sc.nextInt();
for(int i=0;i<n;i++){
m=sc.nextInt();
mark=new boolean[m];
a=new int[m];
sum=0;
for(int j=0;j<m;j++){
a[j]=sc.nextInt();
sum+=a[j];
}
edge=sum>>2;//右移一位除以2
Arrays.sort(a);//排序
if(sum%4==0&&edge>=a[a.length-1]){//边长要大于等于数组里里面的元素的最大值
if(DFS(0,0,0))
pw.println("yes");
else
pw.println("no");
}else
pw.println("no");
}
}
// 第一个变量是有几条边，第二个变量是每次循环边长的大小， 第三个变量是第几个元素
public static boolean DFS(int length,int size,int index){
//等于四条边的就退出循环
if(length==4)
return true;
if(size==edge){
if(DFS(length+1,0,length+1))
return true;
else
return false;
}
else{
for(int i=index;i<m;i++){
if(!mark[i]&&size+a[i]<=edge){
mark[i]=true;
if(DFS(length,size+a[i],i+1))
return true;
mark[i]=false;
}
}
}
return false;
}
}

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。