돌 을 뽑다

67. 돌 뽑 기 (15 분)  C 시간 제한: 3000 밀리초 | C 메모리 제한: 3000 Kb 제목 내용: 돌 한 무더기 가 있 습 니 다. A, B 두 사람 이 돌아 가면 서 돌 을 꺼 냅 니 다. 매번 꺼 낸 돌의 수 는 1, 3, 7 또는 8 밖 에 되 지 않 습 니 다. 마지막 돌 은 누가 찾 으 면 지 는 쪽 입 니 다.A, B 두 사람 은 충분히 똑똑 해서 잘못된 판단 을 하지 않 는 다.현재 일정한 숫자의 돌 을 제시 합 니 다. A 는 먼저 돌 을 취하 고 A 는 최종 적 으로 지 는 것 이 이 기 는 것 인지 계산 합 니 다. 이 기 는 것 은 1 로 표시 하고 지 는 것 은 0 으로 표시 합 니 다. 첫 번 째 행 위 를 묘사 하 는 정수 n (0 < n < 100) 을 입력 하면 n 게임 을 하 는 것 을 의미 합 니 다. 그 다음 에 n 행 은 줄 마다 하나의 정수 가 있 고 해당 하 는 국 에서 제공 하 는 돌 수 (10000 보다 크 지 않 음) 를 표시 합 니 다.
출력 설명 프로 그래 밍 출력 A 에 대응 하 는 n 세트 는 이기 고 지 는 것 입 니 다. 출력 1 을 이기 고 출력 0 을 지 는 것 입 니 다.
샘플 입력 3 1 3 10
출력 샘플
 제목 은 간단 한 게임 이론 이다. 게임 이론의 제목 에서 전형 적 인 SG 함수 의 개념 은 여기 서 군더더기 에 불과 하 다. 나중에 게임 이론의 제목 을 다시 이야기 하 자.
현재 문제 논제 에 대해 우 리 는 먼저 임의의 돌 수 n 을 살 펴 보 자.그것 의 승 부 는 반드시 그 앞의 상태 n - 1, n - 3, n - 7, n - 8 에 의 해 얻어 진다. 그리고 A, B 는 충분히 똑똑 하 다. 그들 은 최종 상태 전의 한 상태 에서 이 길 수 있 으 면 기 회 를 놓 치지 않 을 것 이다.그러면 우 리 는 n - 1, n - 3, n - 7, n - 8 의 상태 에 만 관심 을 가지 면 되 지만 그들의 상 태 는 그들의 이전 상태 와 관계 가 있다.실제로 종말 상태의 전 상 태 를 풀기 위해 서 는 모든 상태, 즉 모든 돌 수의 승 부 를 구 해 야 한다.
#include"iostream"
using namespace std;
bool dp[10001];
int N;
int main(){
	dp[0]=0;
	dp[1]=0;
	dp[2]=1;
	dp[3]=0;
	dp[4]=1;
	dp[5]=0;
	dp[6]=1;
	dp[7]=0;
	dp[8]=1;//  8         ,        ,       ( 8 i - 8        ,    ,            ,         )
	for(int i = 9;i<=10000-1;i++)
		if(!dp[i-1]||!dp[i-3]||!dp[i-7]||!dp[i-8])
		dp[i]=1;
	cin >> N;
	for(int i = 0;i < N;i++){
		 int a;
		cin >> a;
		cout <

좋은 웹페이지 즐겨찾기