1087. The Time to Take Stones
Time Limit: 1.0 second
Memory Limit: 16 MB
You probably know the game where two players in turns take 1 to 3 stones from a pile. Looses the one who takes the last stone. We'll generalize this well known game. Assume that both of the players can take not 1, 2 or 3 stones, but k1, k2, …, km ones. Again we'll be interested in one question: who wins in the perfect game. It is guaranteed that it is possible to make next move irrespective to already made moves.
Input
The first line contains two integers: n and m (1 ≤ n ≤ 10000; 1 ≤ m ≤ 50) — they are an initial amount of stones in the pile and an amount of numbers k1, …, km. The second line consists of the numbers k1, …, km, separated with a space (1 ≤ ki ≤ n).
Output
Output 1, if the first player (the first to take stones) wins in a perfect game. Otherwise, output 2.
Sample
| input |
output |
17 3
1 3 4
|
2
|
Problem Author: Anton Botov
Problem Source: The 3rd high school children programming contest, USU, Yekaterinburg, Russia, March 4, 2001
/*
"Looses the one who takes the last stone" —— the one takes the last
stone loses the game !
*/
#include <stdio.h>
#include <memory>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <cmath>
#include <set>
#include <queue>
#include <time.h>
#include <limits>
using namespace std;
#define N 10005
#define M 55
int step[M], n, m;
bool state[N];
bool input(){
if(scanf("%d%d", &n, &m) == EOF) return false;
int i;
for(i = 0; i < m; i++) scanf("%d", step+i);
return true;
}
void solve(){
memset(state, 0, sizeof(bool) * (n+1));
int i, j, u;
for(i = 1; i <= n; i++){
for(j = 0; j < m; j++){
if((u = i - step[j]) >= 0){
if(u == 0){
state[i] = false;
}else{
if(!state[u]){
state[i] = true;
break;
}
}
}
}
}
//for(i = 0; i <= n; i++) printf("s[%d]=%d\n", i, state[i]);
if(state[n]) printf("1\n");
else printf("2\n");
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
while(input()) solve();
return 0;
}