№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
88131654 |
Дорешивание:
Mihari |
788C
- 38
|
GNU C++11
|
Неправильный ответ на тесте 11
|
124 мс
|
7944 КБ
|
2020-07-27 16:45:00 |
2020-07-27 16:45:00 |
|
#include<queue>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int MAXN=1000;
const int MAXK=1e6;
int a[MAXK+5];
bool t[MAXN+5];
int n,k;
inline void Init(){
scanf("%d %d",&n,&k);
for(int i=1;i<=k;++i)scanf("%d",&a[i]),t[a[i]]=true;
k=0;int sign=0,flg=1;
for(int i=1;i<=MAXN;++i)if(t[i]){
a[++k]=i-n;
if(a[k]==0){puts("1");exit(0);}
if((a[k]<0 && sign==1) || (a[k]>0 && sign==-1))flg=0;
if(a[k]<0)sign=-1;
else sign=1;
}
if(flg){puts("-1");exit(0);}
}
struct node{int w,s;};
queue<node>Q;
bool vis[MAXN*2+5];
inline bool inside(const int x){
return -MAXN<=x && x<=MAXN;
}
inline void Bfs(){
for(int i=1;i<=k;++i)Q.push(node{a[i],1}),vis[a[i]+MAXN]=true;
while(!Q.empty()){
node now=Q.front();Q.pop();
int tw;
for(int i=1;i<=k;++i){
tw=now.w+a[i];
if(!inside(tw) || vis[tw+MAXN])continue;
if(tw==0){
printf("%d\n",now.s+1);
return;
}
vis[tw+MAXN]=true;
Q.push(node{tw,now.s+1});
}
}
}
int main(){
Init();
Bfs();
return 0;
}
Время: ? ms, память: ? КБ