HDU 1850 Being a Good Boy in Spring Festival(Nim 바둑)

6373 단어 spring
Being a Good Boy in Spring Festival
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 3142    Accepted Submission(s): 1821
Problem Description
일년 내 내 외지 에 있 으 면 부모 가 늘 걱정한다.
설날 에 집에 돌아 오 면 너 는 며칠 동안 좋 은 아이 가 될 수 있 니
겨울방학 에 다음 일 을 해 보 세 요.
어머니 를 모시 고 채소시장 을 한 번 구경 하 다
아빠 에 게 몰래 작은 선물 을 사다.
주동 적 으로 강력하게 설 거 지 를 요구 하 다
어느 날 일찍 일어나 부모님 께 열심히 아침 식 사 를 해 드 렸 습 니 다.
원한 다 면 부모님 께 말씀 드 려 도 돼 요.
우리 작은 게임 하 자.ACM 수업 다 녔 는데~
다음은 2 인 미니 게임 입 니 다.책상 위 에 M 더미 의 카드 가 있 습 니 다.각 카드 의 수량 은 각각 Ni(i=1...M)이다.두 사람 이 돌아 가면 서 진행한다.한 걸음 한 걸음 걸 을 때마다 임의로 한 무 더 기 를 선택 하고 그 중의 임의의 카드 를 가 져 갈 수 있다.책상 위의 카드 를 모두 제거 하면 게임 이 끝 납 니 다.마지막 으로 카드 를 뽑 은 사람 이 승자 다.
지금 우 리 는 선수 가 이 기 는 지 마이너스 가 되 는 지 연구 하고 싶 지 않다.나 는 단지 여러분 에 게 묻 고 싶 을 뿐이다.
-"선수 가 이기 고 싶다 면 첫 번 째 단 계 는 몇 가지 선택 이 있 습 니까?"
 
 
Input
입력 데 이 터 는 여러 개의 테스트 용례 를 포함 하고 각 테스트 용례 는 2 줄 을 차지한다.먼저 한 줄 은 하나의 정수 M(1 
 
Output
만약 선수 가 이 길 수 있다 면,그의 첫 번 째 실행 가능 한 방안 수 를 출력 하 십시오.그렇지 않 으 면 0 을 출력 하 십시오.모든 인 스 턴 스 의 출력 이 한 줄 을 차지 합 니 다.
 
 
Sample Input
3 5 7 9 0
 
 
Sample Output
1
 
 
Author
lcy
 
 
Source
ACM Short Term Exam_2007/12/13
 
 
Recommend
lcy
 
 
하나      만약 a1^a2^a3^...^an=0(즉:nim-sum=0)은 선수 가 반드시 이 길 전략 이 없다 는 것 을 설명 하고 방법 수 는 0 일 것 이다.둘.
      선수 가 있 는 사람 이 반드시 이 기 는 전략 이 있다 고 가정 하 다.
            문 제 는=>임의의 한 무더기 에서 임의의 K 장의 카드 를 가 져 오고 나머지 모든 더미 의 nim-sum=0(P-position)의 프로젝트 총수 로 바 뀌 었 다.
                     1. 지금 우 리 는 먼저 예(5,7,9)를 보고 첫 번 째 더미 에서 임의의 K 장의 카드 를 가 져 올 것 이 라 고 가정 한다.
                              첫 번 째 카드 를 제외 한 nim-sum 은 7^9=14 입 니 다.
                                            0111
                                          ^1001
                                          -------
                                            1110
                              모든 더미 의 nim-sum=0 을 만 들 려 면 첫 번 째 더 미 는 K 장 을 제거 한 후 반드시 1110 이 어야 합 니 다.X^X=0 이기 때 문 입 니 다.
                              따라서 5-k=14 k>0 이 성립 되 는 것 을 관찰 해 야 한다.이 예(첫 번 째 더미 에서 임의의 K 장 카드 를 가 져 오 는 것)는 뚜렷하게 성립 되 지 않 는 다.그러나 두 번 째 나 세 번 째 더미 에서 임의의 K 장의 카드 를 가 져 오 는 것 이 성립 되 지 않 는 다 는 것 은 아니다.
                     2. 지금 두 번 째 예(15,7,9)를 보고 첫 번 째 더미 에서 임의의 K 장의 카드 를 가 져 온다 고 가정 한다.
                              줄 을 서 있 는 첫 번 째 카드 의 nim-sum 은 7^9=14 로 첫 번 째 예 와 같 기 때문에 문 제 는 15-k=14 k>0 이 성립 되 는 지 관찰 하 는 것 으로 바 뀌 었 다.
                              물론 이 예 는 성립 된 것 이다.
셋.      총 결 결과:
            임의의 한 무더기 에서 임의의 K 장 패 를 가 져 오고 모든 무더기 의 nim-sum=0 이 성립 되 는 조건 은 K 장 패 를 제거 한 그 무더기 의 nim-sum 은 이 무더기 의 수량(예 2)보다 적어 야 한다.그렇지 않 으 면 이 더미 에서 임의의 K 장 패 를 가 져 와 모든 무더기 의 nim-sum=0 을 성립 시 킬 수 없다.(예 1)
            그러므로 총 방안 수 는(임의의 한 무더기 에서 임의의 K 장의 카드 를 가 져 오고 모든 무더기 의 nim-sum=0 이 성립 됨)의 총수 이다.
 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

int n,a[110];

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d",&n) && n){
        int ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            ans^=a[i];
        }
        if(ans==0){
            puts("0");
            continue;
        }
        int cnt=0;
        for(int i=0;i<n;i++)
            if((a[i]^ans)<=a[i])    //                (            )
                cnt++;
        printf("%d
",cnt); } return 0; }

 

좋은 웹페이지 즐겨찾기