돌 채취 게임 (알고리즘)

2169 단어
묘사 하 다.
어느 날, TT 는 침실 에서 한가 하고 심심 해서 같은 침대 에 있 는 사람과 돌 채취 놀 이 를 하기 시 작 했 는데 조건 이 제한 되 어 있 기 때문에 그 / 그들 은 왕 자 만 두 를 돌 로 삼 았 다.게임 의 규칙 은 이렇다.한 무더기 의 돌 이 설치 되 어 있 고 수량 은 N (1 ≤ N ≤ 1000000) 이 며, 두 사람 은 번갈아 그 중의 몇 개 를 꺼 내 고, 매번 최대 M (1 ≤ M ≤ 1000000) 개 를 취하 고, 가장 먼저 돌 을 다 얻 은 자 는 승리 한다.우 리 는 TT 와 그 / 그녀의 룸메이트 가 모두 매우 총명 하 다 는 것 을 알 고 있 습 니 다. 그러면 TT 가 먼저 이기 면 그 / 그녀 는 게임 의 승 리 를 거 둘 수 있 습 니까?
출력
먼저 취한 TT 가 게임 을 이 길 수 있다 면 1 을 출력 하고 그렇지 않 으 면 0 을 출력 합 니 다.
바 시 보 혁: n 개의 물건 만 있 고 두 사람 은 돌아 가면 서 이 물건 에서 물건 을 찾 습 니 다. 매번 에 적어도 하 나 를 찾 고 최대 m 개 를 찾 도록 규정 합 니 다.마지막 으로 빛 을 얻 은 사람 이 이긴다.
분명 한 것 은 n = m + 1 이 라면 한 번 에 최대 m 개 만 가 질 수 있 기 때문에 선 취 자가 몇 개 를 가 져 가든 후 취 자 는 한 번 에 남 은 물건 을 가 져 갈 수 있 고 후 자 는 이 길 수 있다.따라서 우 리 는 어떻게 이 기 는 지 의 법칙 을 발견 했다. 만약 n = (m + 1) r + s, (r 는 임 의 자연수, s ≤ m), 그러면 선 취 자 는 s 개의 아 이 템 을 가 져 가 야 한다. 만약 후 취 자가 k (≤ m) 개 를 가 져 가면 선 취 자 는 m + 1 - k 개 를 가 져 가 고 결 과 는 (m + 1) 개 (r - 1) 개 를 남 겨 두 고 이런 취 법 을 유지 하면 선 취 자 는 반드시 이 길 것 이다. 한 마디 로 하면 상대방 에 게 (m + 1) 개 를 남 겨 야 한다.의 배수 로 마지막 에 이 길 수 있다.
쉽게 말 하면 마지막 손 으로 자신 에 게 < = m 개 를 남 기 는 것 이다.
Δ:만약 두 사람 이 모두 총명 하지 않 았 다 면 바 시 보 혁 을 사용 할 수 없 었 을 것 이다.)
#include 
#include 

/*
   
*/
int main()
{
    int n=0,m=0;
    printf("N M:");
    scanf("%d %d",&n,&m);

    if(n%(m+1)==0)
        printf("0");
    else
        printf("1");

    return 0;
}

좋은 웹페이지 즐겨찾기