HDU 2177 돌 빼 기 게임

돌멩이 놀이
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 567    Accepted Submission(s): 348
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
 
Author
Zhousc
 
Source
ECJTU 2008 Summer Contest
 
 
이 돌 을 따 는 것 은 매우 재미있다.YY 의
생각:
{
   우선 기이 한 상태 인지 아 닌 지 를 판단 하 는 것 이다. 물론 간단 하 다.
   그렇다면 출력 0;
   만약 그렇지 않다 면, 먼저 1 을 출력 한 다음 에 1 을 출력 하여 기이 한 상 태 를 형성 하 는 상황 이다.
 
  문 제 는 당연히 여기에 있다.
  여기까지 우 리 는 두 가지 전략 이 있다.
   1. 두 무더기 에서 동시에 가 져 오기
   2. 한 무더기 에서 꺼낸다.
  먼저 해결 1: 이것 도 간단 합 니 다. 기이 한 상 태 를 판단 하 는 것 을 알 면 쉽 습 니 다.
               k 를 통 해 aj, bj 를 구 할 수 있 습 니 다. 그러면 판단 할 수 있 습 니 다.
  어 려 운 점 은 2: 이 를 분류 하고 입력 한 숫자 가 각각 n, m 이면
                만약 n 이 aj 라면 bj 를 구하 고 bj 가 bj < = m; / (1) 를 만족 시 키 는 지 판단 합 니 다.
                만약 n 이 bj 라면 aj 를 구하 고 aj 가 aj < = n; / (2) 를 만족 시 키 는 지 판단 합 니 다.
                만약 m 가 aj 라면 bj 를 구하 고 bj 를 판단 합 니 다.
                만약 m 가 bj 라면 aj 를 구하 고 aj 를 판단 합 니 다.
 때문에
 토론 이 끝 났 는데 어떻게 구 합 니까?
   
 bk = ak + k, ak = (k * (1 + sqrt (5.) / 2.0) 때문에 각 값 을 구 합 니 다.
       그러나 이렇게 되면 기이 한 상태의 특징 (어떤 자연수 든 하나의 기이 한 상태 에 만 존재 한다) 과 모순 된다.
       n 에 있어 서 (1) 또는 (2) 중의 하나 만 존재 할 수 있 기 때문에 이런 생각 을 하면
       두 가지 가 더 있 을 거 예요.
       이제 막 꼬 였 어.
    
다른 사고방식: 시 계 를 치다.
       폭력 으로 모든 것 을 해결 하고 k 를 통 해 시 계 를 치면 첫 번 째 사고의 문 제 를 피 할 수 있 고 2 분 으로 찾 을 수 있다.
    물론 한 가지 문 제 를 처리 해 야 한다. (2) (3) 의 결 과 는 같 을 수 있 으 므 로 tmp 의 역할 을 판단 해 야 한다.
                                  
}
데이터 가 0 ms 가 넘 었 다 는 뜻 입 니 다.오류 가 있 을 수도 있 고 데이터 가 지 났 습 니 다.
 
 

#include
#include
int f[500003]={0},q[500003]={0};
void dabiao()
{
    int k,aj,bj;
    double tmp;
    tmp=(1.0+sqrt(5.0))/2.0;
    for(k=1;k<=500000;k++)
    {
        aj=(int)(k*tmp);
        bj=aj+k;
        f[k]=aj;
        q[k]=bj;
    }
}
int EF(int l,int r,int num,int a[500003])
{
    int mid;
    mid=(l+r)/2;
    while(l<r)
    {
        if(a[mid]>num)
            r=mid-1;
        else if(a[mid]<num)
            l=mid+1;
        else return mid;
        mid=(l+r)/2;
    }
    return mid;
}
int main()
{
    int k,n,m,t,aj,bj,tmp;
    dabiao();
    while(scanf("%d%d",&n,&m)>0)
    {
        if(n==0&&m==0)break;
        k=m-n;
        t=(int) (k*(1.0+sqrt(5.0))/2.0);
        if(t==n)
        {
            printf("0
");
            continue;
        }
        printf("1
");
        aj=t;
        bj=t+k;
        if(aj<=n&&bj<=m)
            printf("%d %d
",aj,bj);
        k=EF(1,500000,n,f); //n  aj
        if(f[k]==n)
        {
            if(q[k]<=m)
            {
                printf("%d %d
",f[k],q[k]);
            }
        }
        tmp=-1;
        k=EF(1,500000,n,q); // n   bj
        if(q[k]==n)
        {
            if(f[k]<=m)
            {
                printf("%d %d
",f[k],q[k]);
                tmp=q[k]-f[k];
            }
        }
        k=EF(1,500000,m,q); // m  bj
        if(q[k]==m)
        {
            if(f[k]<=n&&tmp==-1)
                printf("%d %d
",f[k],q[k]);
        }
    }
    return 0;
}

 
 
 
 
다음으로 전송:https://www.cnblogs.com/tom987690183/archive/2013/05/27/3102570.html