동전 게임 > 문제은행

본문 바로가기


문제은행

2915 : 동전 게임

제한시간: 1Sec    메모리제한: 128mb
해결횟수: 147회    시도횟수: 666회   



영희와 동수는 동전 던지기 게임을 하고 있다. 이 게임은 K번 라운드로 구성되고 다음과 같은 규칙들을 따른다:
1. 한 라운드에서 영희와 동수는 한 번씩 동전을 던지고 항상 영희가 먼저 던진다.
2. 동전을 던져 앞면이 나오면 1점을 얻고, 뒷면이 나오면 점수를 얻지 못한다.
3. 한 명이 남은 기회에 모든 점수를 얻더라도 상대방이 현재까지 얻은 점수보다 작게 되면 게임 도중 어떤 시점에서도 게임은 바로 끝난다.

 

0 이상 K 이하인 임의의 정수 M과 N에 대해서, 이것이 항상 게임이 끝난 후 영희와 동수가 얻는 점수가 되는 것은 아니다. 예를 들어서, K=2인 경우에, M과 N의 모든 경우에 대해서, 이것이 영희와 동수가 얻는 점수가 될 수 있는 지의 여부는 다음 표와 같다:

 

efc6e5f9d670c6da62174cf11a66a8c2_1449741

 


위 표에서 영희와 동수의 점수가 0과 2가 되는 것이 불가능한 이유는 두 번째 라운드에서 영희가 뒷면이 나와서 점수를 얻지 못하는 순간 게임의 규칙 3에 의해서 0과 1로 게임이 끝나기 때문이다.
 

0이상 K이하인 정수 M과 N이 주어질 때, 이 두 정수가 각각 영희와 동수의 점수가 될 수 있는지 여부를 판별하는 프로그램을 작성하시오.


다음 정보가 표준 입력으로 주어진다. 
첫 줄에 게임의 라운드 수를 나타내는 정수 K(1≤K≤1,000)가 주어진다. 
두 번째 줄에는 입력의 개수를 나타내는 정수 C(1≤C≤100,000)가 주어진다. 
다음 이어지는 C개의 줄 각각에는 하나의 입력을 나타내는 두 정수 M과 N(0≤M,N≤K)이 주어진다.


다음 정보를 표준 출력으로 출력한다. 
출력은 C개의 줄로 구성된다. 
게임에서 영희와 동수의 점수가 각각 M과 N이 될 수 있다면 1, 아니면 0을 각 줄에 출력한다.

부분문제의 제약 조건
• 부분문제 1: 전체 점수 100점 중 9점에 해당하며, K=2이다.
• 부분문제 2: 전체 점수 100점 중 19점에 해당하며, K=3이다.
• 부분문제 3: 전체 점수 100점 중 21점에 해당하며, K=5이다.
• 부분문제 4: 전체 점수 100점 중 51점에 해당하며, 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
5
4
5 5
5 1
0 3
1 4
[Copy]
1
0
1
0




HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.