zoj1039 Number Game 게임 + DP+ 상태 압축
Time Limit: 10 Seconds
Memory Limit: 32768 KB
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.
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.
Source: Mid-Central European Regional Contest 2000
상태 압축 지식을 좀 배웠어요.
한 상태에서 어떤 위치의 수를 빼야 합니다state&=~(1<(i)
한 상태에 어떤 위치를 추가할 수 state|=(1한 상태에 어떤 위치를 포함하는지 판단하는 수if(state&(1오류가 있으면 지적해 주세요 ~
제목: 2~20이라는 19개의 수에서 수대국을 선택하여 매번 한 개의 수를 가져간 후 이 수의 배수의 수는 다시 뽑을 수 없고 어떤 두 개의 뽑을 수 없는 수의 합도 다시 뽑을 수 없다.
19개밖에 안 되기 때문에 우리는 상태 압축을 진행할 수 있다. 전체 상태는 1<19이다.
하나의 수를 가져간 후에 어떻게 이 수와 이 수의 배수를 제거합니까?
for(int i=x;i<=20;i+=x)
state&=~(1<왜 집합에 없는 수와 이 수를 빼요?
여기서 우리는 역방향으로 생각해야 한다. 만약에 어떤 수가 이 집합에 있다고 가정하면 그것으로 x를 끊임없이 빼야 한다. 만약에 얻은 차치가 이 집합에 없다면 이 수는 불법이기 때문에 빼야 한다.
한 상태의 승패를 판단하는 데 쓰이는 것은 바로 바둑의 PN의 기본적인 성질이므로 더 이상 군말하지 않겠다.
#include<iostream>
#include<cstdlib>
#include<stdio.h>
#include<memory.h>
using namespace std;
int dp[524289];
int get_solve(int state,int x)
{
// x x
int ret=state;
for(int i=x;i<=20;i+=x)
ret&=~(1<<(i-2));
// x
for(int i=2;i<=20;i++)
{
if(ret&(1<<(i-2)))// i
for(int j=x;i-j-2>=0;j+=x)
{
if(!(ret&(1<<(i-j-2))))
{
ret&=~(1<<(i-2));
break;//
}
}
}
return ret;
}
int dfs(int state)
{
if(dp[state]!=-1) return dp[state];
for(int i=2;i<=20;i++)
{
if(state&(1<<(i-2)))
{
if(dfs(get_solve(state,i))==0)
return dp[state]=1;
}
}
return dp[state]=0;
}
int main()
{
//cout<<(1<<19)<<endl;
int t,n,a[21];
int count=1;
memset(dp,-1,sizeof(dp));
dp[0]=0;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
int state=0;
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
state|=1<<(a[i]-2);
}
printf("Scenario #%d:
",count++);
if(dfs(state)==0)
puts("There is no winning move.
");
else
{
printf("The winning moves are:");
for(int i=0;i<n;i++)
{
if(dfs(get_solve(state,a[i]))==0)
printf(" %d",a[i]);
}
puts(".
");
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[SwiftUI]List화한 CoreData를 가로 스와이프로 행 삭제하는 방법상당히 조사했지만 일본어 자료가 없었기 때문에 비망록으로 남겨 둔다. 아래와 같이 CoreData를 참조한 리스트를 가로 스와이프로 삭제하고 싶었다. UI 요소뿐만 아니라 원본 데이터 당 삭제합니다. 잘 다른 페이지...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.