codeforces #407(div1c div 2e)The Great Mixing

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e4+5;
 4 int n,k;
 5 
 6 int a[maxn],b[maxn],v,tot=0;
 7 
 8 queue<int> q;
 9 
10 int main(){
11     scanf("%d%d",&n,&k);
12 
13     for(int i=0;i<k;i++){
14         scanf("%d",&v);
15         a[v]=1;
16     }
17 
18     if(a[n]==1){
19         puts("1");
20         return 0;
21     }
22 
23 
24 
25     for(int i=0;i<=1000;i++)if(a[i]==1){
26         b[tot++]=i;
27         q.push(i-n+1001);
28     }
29 
30     for(int i=0;i<tot;i++)a[b[i]-n+1001]=1;
31 
32     while(!q.empty()){
33         int val=q.front();q.pop();
34         val-=1001;
35 
36         for(int i=0;i<tot;i++){
37             int vv=val+b[i]-n;
38 
39             if(vv==0){
40                 printf("%d\n",a[val+1001]+1);
41                 return 0;
42             }
43             vv+=1001;
44             if(vv<0)
45             {
46                 continue;
47             }
48             if(!a[vv]){
49                 a[vv]=a[val+1001]+1;
50                 q.push(vv);
51             }
52         }
53     }
54 
55 
56     puts("-1");
57 
58 
59 
60 
61     return 0;
62 }