[알고리즘 실험 4] - [동적 계획] - 땅콩 (2)

1083. 땅콩 (2)
시한: 1000 ms 메모리 제한: 10000 K 총 시한: 3000 ms
묘사 하 다.
노동절 연 휴 다음날 톰 과 제 리 는 창 고 를 산책 하 다가 땅콩 한 무 더 기 를 발견 했다.이번 Tom 은 땅콩 을 나 누 는 규칙 을 다음 과 같이 제정 했다.       1. 톰 과 제 리 는 돌아 가면 서 더미 에서 k 알 의 땅콩 을 꺼 내 먹는다. k 는 1, 5, 10 중의 임의의 숫자 일 수 있다.       2. 규칙 의 형 평성 을 나타 내기 위해 Jerry 는 선 취 또는 후 취 를 선택 할 수 있 습 니 다.제 리 는 물론 마지막 땅콩 을 톰 에 게 먹 혔 으 면 좋 겠 다.제 리 가 목적 을 달성 하기 위해 먼저 취해 야 하 는 지, 아니면 나중에 취해 야 하 는 지 계산 해 보 세 요.
 
입력
이 문 제 는 여러 개의 측정 사례 가 있 는데 모든 측정 사례 의 입력 은 하나의 정수 n 이 고 n 이 0 보다 크 면 1000 보다 작 으 며 땅콩 의 수량 을 대표 한다.n 은 0 과 같 아서 입력 이 끝 났 음 을 표시 하고 처리 할 필요 가 없습니다.
 
출력
모든 테스트 예 는 한 줄 에 하나의 정 수 를 출력 합 니 다: Jerry 가 먼저 출력 1 을 가 져 옵 니 다.Tom 먼저 출력 0.
 
입력 샘플
1 2 3 4 0
 
출력 샘플
0 1 0 1
해석: 이 문 제 는 동적 기획 알고리즘 으로 해답 을 구하 고 사고방식 을 말 해 보 세 요.매번 에 1, 5, 10 개의 땅콩 을 가 져 갈 수 있 는데 찾 는 방법 은 어떻게 든 가 져 가 는 것 이 어야 한다. 톰 이 가 질 차례 가 되 었 을 때 한 개 만 남 았 고 톰 은 이 유일한 하 나 를 가 져 갈 수 밖 에 없 었 다. 왜냐하면 그 는 가 져 가지 않 을 수 없 었 기 때문이다.따라서 입력 한 땅콩 n 개 에 대해 10 보다 적 을 때 1 개 또는 5 만 가 져 갈 수 있 기 때문에 10 이내 의 수량, 짝수 개 는 Jerry 가 먼저 가 져 갑 니 다. 한 사람 이 홀수 개 만 가 져 갈 수 있 기 때문에 자신 은 한 알 만 가 져 가면 Tom 에 게 마지막 하 나 를 가 져 갈 수 있 습 니 다. 물론 10 개 도 Jerry 가 먼저 가 져 갑 니 다. 한 번 에 10 개 만 가 져 가지 않 으 면 1 개 또는 5 는 Tom 이 마지막 을 가 져 오기 때 문 입 니 다.10 개가 넘 는 것 에 대해 서 는 이번에 다 따 면 (1, 5, 10 에서 몇 개 를 따 든) 제 리 가 이 기 는 것 이 라면 톰 에 게 먼저 하 라 고 하 세 요. 그렇지 않 으 면 반드시 자신 이 먼저 해 야 합 니 다.그래서 여기 판단 조건 은

for(int i=11;i<=1000;i++)
{
     if(peanut[i-1]==1&&peanut[i-5]==1&&peanut[i-10]==1)
          peanut[i]=0;
     else 
          peanut[i]=1;
}

여기 서 현재 상 태 는 Tom 이 몇 개 를 취하 든 마지막 에 Jerry 가 이 긴 다 는 뜻 입 니 다. 그러면 저 는 Tom 에 게 먼저 하 라 고 하 겠 습 니 다. 그렇지 않 으 면 저 는 반드시 제 가 먼저 하 겠 습 니 다. 왜냐하면 저 는 제 가 얻 은 수량 을 스스로 통제 하여 뒤의 Tom 이 마지막 하 나 를 얻 도록 할 수 있 기 때 문 입 니 다.코드 는 다음 과 같 습 니 다:

#include 
#include
using namespace std;
int n;
int peanut[1001];
int take()
{
    for(int i=1;i<=10;i++)
    {
        if(i%2==0)
            peanut[i]=1;
        else
            peanut[i]=0;
    }
    for(int i=11;i<=1000;i++)
    {
         if(peanut[i-1]==1&&peanut[i-5]==1&&peanut[i-10]==1)
              peanut[i]=0;
         else
              peanut[i]=1;
    }
    return 0;
}
int main()
{
    take();
    while(scanf("%d",&n)&&n)
        cout<