fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 50005 ;
  6. int vis[MAX] , arr[MAX] , vis2[MAX];
  7. int n ;
  8. void dijkstra()
  9. {
  10.     for(int i = 0 ; i <= 50000 ; ++i)
  11.         vis[i] = 1e9+10 ;
  12.     priority_queue< pair<int , int> , vector< pair<int , int> > , greater< pair<int , int> > >q ;
  13.     q.push({0 , 0}) ;
  14.     vis[0] = 0 ;
  15.     while(!q.empty())
  16.     {
  17.         pair<int , int>p = q.top();
  18.         q.pop();
  19.         int now = p.first , cur = p.second ;
  20.         if(vis[cur] < now)
  21.             continue;
  22.         if(vis2[cur] == 1)
  23.             continue ;
  24.         vis2[cur] = 1 ;
  25.         for(int i = 0 ; i < n ; ++i)
  26.         {
  27.             int now2 = now + arr[i] ;
  28.             int cur2 = (cur + arr[i]) % arr[0] ;
  29.             //if(now2 > 1e9)
  30.             //    continue ;
  31.             if(now2 < vis[cur2] && now2 <= 1e9)
  32.             {
  33.                 vis[cur2] = now2 ;
  34.                 q.push({now2 , cur2}) ;
  35.             }
  36.         }
  37.     }
  38.     return ;
  39. }
  40.  
  41. int main()
  42. {
  43.     scanf("%d" , &n) ;
  44.     for(int i = 0 ; i < n ; ++i)
  45.         scanf("%d" , &arr[i]) ;
  46.     sort(arr , arr + n) ;
  47.     dijkstra();
  48.     int q ;
  49.     scanf("%d" , &q);
  50.     while(q--)
  51.     {
  52.         int x ;
  53.         scanf("%d" , &x);
  54.         if(vis[x % arr[0]] <= x)
  55.             puts("TAK");
  56.         else
  57.             puts("NIE");
  58.     }
  59.     return 0 ;
  60. }
Success #stdin #stdout 0s 15824KB
comments (?)
stdin
copy 
3
2
5
7
6
0
1
4
12
3
2
stdout
copy 
TAK
NIE
TAK
TAK
NIE
TAK
https://ideone.com/Iwd0ON
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!