http://acm.tju.edu.cn/toj/showp1017.html
1017. Number Game
--------------------------------------------------------------------------------
Time Limit: 5.0 Seconds Memory Limit: 65536K
Total Runs: 175 Accepted Runs: 72
--------------------------------------------------------------------------------
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:
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.)
A sum of two such multiples cannot be chosen either.
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 3, this game may go on forever. However, with rule 3, 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
all numbers are forbidden, or
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.
Input
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).
Output
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.
Sample Input
2
1
2
2
2 3
Sample Output
Scenario #1:
The winning moves are: 2.
Scenario #2:
There is no winning move.
这题直接搜索超时，我改用备忘录法超时到是不超了，一直Wrong Answer，在第6次之后我觉得发到这来给大家玩吧
下面是我WA的代码
程序代码：
#include <iostream>
#include <map>
using namespace std;int arr2i(int arr[20+1])
{
int res=0;
for(int i=1;i<=20;i++){
if(arr[i]){
res=(res|(1<<(i-1)));
}
}
return res;
}void i2arr(int x,int arr[20+1])
{
for(int i=2;i<=20;i++){
if(x&(1<<(i-1))){
arr[i]=1;
}
else {
arr[i]=0;
}
}
}void take(int arr[20+1],int n)
{
for(int i=2;i<=20;i++){
if(!arr[i])continue;
for(int j=n;i+j<=20;j+=n){
arr[i+j]=0;
}
}
for(int j=n;j<=20;j+=n){
arr[j]=0;
}
}
map<int,int> M;
int s(int x)
{
if(!x) return 0;
if(M.find(x)!=M.end())return M[x];
int t,arr[20+1];
for(int i=2;i<=20;i++){
if(x&(1<<(i-1))){
i2arr(x,arr);
take(arr,i);
t=arr2i(arr);
if(!s(t)){
return (M[x]=1);
}
}
}
return (M[x]=0);
}int solve(int x)
{
if(!x) return 0;
int t,res=0,arr[20+1];
for(int i=2;i<=20;i++){
if(x&(1<<(i-1))){
i2arr(x,arr);
take(arr,i);
t=arr2i(arr);
if(!s(t)){
res=(res|(1<<(i-1)));
}
}
}
return res;
}int main()
{
int T,cnt=0;
scanf(\"%d\",&T);
while(T--){
int n,arr[20]={0},t;
scanf(\"%d\",&n);
for(int i=0;i<n;i++){
scanf(\"%d\",&t);
arr[t]=1;
}
int res=solve(arr2i(arr));
printf(\"Scenario #%d:\n\",++cnt);
if(res){
printf(\"The winning moves are: \");
i2arr(res,arr);
int first=1;
for(int i=1;i<=20;i++){
if(arr[i]){
if(first){
first=0;
}
else {
printf(\" \");
}
printf(\"%d\",i);
}
}
printf(\".\n\");
}
else {
printf(\"There is no winning move.\n\");
}
printf(\"\n\");
}
}
[此贴子已经被作者于2007-7-29 1:54:07编辑过]
