돌 채취 게임 (알고리즘)
어느 날, 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.