HDU 2177 취 (2 더미) 돌 게임 (위 조 프 게임)
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2280 Accepted Submission(s): 1384
Problem Description
두 무더기 의 돌 이 있 는데, 수량 이 임의로 다 를 수 있다.게임 은 두 사람 이 돌아 가면 서 돌 을 채취 하기 시작 했다.게임 규정 에 따 르 면 매번 두 가지 서로 다른 취 법 이 있 는데 하 나 는 임의의 한 무더기 에서 임의의 많은 돌 을 가 져 갈 수 있다.둘 째 는 두 더미 에서 같은 양의 돌 을 동시에 가 져 갈 수 있다.마지막 으로 돌 을 모두 가 져 온 자가 승자 다.지금 은 최초의 두 무더기 의 돌 수 를 제시 합 니 다. 만약 당신 이 먼저 취 할 차례 라면 쌍방 이 모두 가장 좋 은 전략 을 취한 다 고 가정 하고 마지막 에 당신 이 승자 인지 패자 인지 물 어보 세 요.만약 네가 이기 면, 너 는 첫 번 째 로 어떻게 자식 을 얻 니?
Input
몇 줄 을 포함 하 는 지 입력 하면 몇 가지 돌의 초기 상황 을 나타 낸다. 그 중에서 한 줄 에 두 개의 부정 정수 a 와 b 를 포함 하고 두 개의 돌의 수 를 나타 낸다. a 와 b 는 모두 1, 000, 000 보다 크 지 않 고 a < = b.a = b = 0 종료.
Output
출력 도 몇 줄 이 있 습 니 다. 마지막 에 당신 이 패자 라면 0 입 니 다. 반대로 1 을 출력 하고 당신 을 이 긴 당신 이 첫 번 째 로 돌 을 뽑 은 후에 남 은 두 무더기 의 돌 수량 x, y, x < = y 를 출력 합 니 다.만약 에 임의의 한 무더기 에서 돌 을 가 져 가면 이 길 수 있 고 두 무더기 에서 같은 수량의 돌 을 동시에 가 져 가도 이 길 수 있다. 먼저 같은 수량의 돌 을 가 져 가 는 상황 을 수출 한다.
Sample Input
1 2 5 8 4 7 2 2 0 0
Sample Output
0 1 4 7 3 5 0 1 0 0 1 2
思路：威佐夫博弈，遇到奇异局势则必败第k个奇异局势(a(k), b(k))，a(k)是前面没有出现过的最小自然数（a(k)=(int)(k*(sqrt(5.0)+1)/2），b(k)=a(k)+k，采用适当的方法，这里不再证明，接下来只要判断就行了
同时从两堆中取相同数量的石头或者从一堆中取一定数量的石头，可以将非奇异局势变为奇异局势
#include
#include
#include
using namespace std;
double g = (sqrt(5.0) + 1) / 2; // 1.618...
int main()
{
int a, b;
while(scanf("%d %d", &a, &b) == 2) {
if(a == 0 && b == 0)
break;
int k = b - a;
if(a == (int)(g * k)) // a ， b=a+k
{
printf("0
");
}
else
{
printf("1
");
//
for(int i=1; i<=a; i++) // ， 1 a
{
int x = a - i, y = b - i;
int k = y - x;
if(x == (int)(g * k))
printf("%d %d
", x, y);
}
for(int i=b-1; i>=0; i--) // ， b-1 0
{
int x = a, y = i;
if(x > y)
swap(x, y);
int k = y - x;
if(x == (int)(g * k))
printf("%d %d
", x, y);
}
}
}
return 0;
} 인터넷 에서 코드 를 보 니 귀 찮 지만 모든 상황 을 다 썼 다.
#include
#include
#include
#include
#include
using namespace std;
int vis[1000005]= {0};
int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
for(int i=1; i<1000005; i++)
vis[i]=(int)(i*1.0*(1+sqrt(5))/2);
int n, m;
while(scanf("%d%d",&n,&m)&&(n||m))
{
int k=m-n;
if(vis[k]==n)
{
printf("0
");
continue;
}
printf("1
");
if(n>vis[k]&&m>vis[k]+k)
printf("%d %d
",vis[k],vis[k]+k);
for(int i=1; i<1000005; i++)
if(vis[i]==n)
{
if(m>vis[i]+i)
printf("%d %d
",vis[i],vis[i]+i);
break;
}else if(vis[i]==m)
{
if(n>vis[i]+i)
printf("%d %d
",vis[i],vis[i]+i);
break;
}
for(int i=1; i<1000005; i++)
if(vis[i]+i==m)
{
if(n>vis[i])
printf("%d %d
",vis[i],vis[i]+i);
break;
}else if(vis[i]+i==n)
{
if(m>vis[i]+i)
printf("%d %d
",vis[i],vis[i]+i);
break;
}
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
hdu 2188 간단 한 게임 바 쉬 게임그 중에서 재 해 를 구 하 는 무장 경찰 부대, 치료 와 방역 의 의료진, 그리고 심리 적 소통 을 하 는 심리학 전문 가 를 포함한다.요구 에 따라 우리 학교 에 도 재해 지역 에 가서 재 해 를 구 하 는 정원...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
