$$2015 German Collegiate Programming Contest (GCPC 15) + POI 10-T3$$
(A. Journey to Greece)
状压DP，TSP，先考虑找出这些关键点之间的最短路，然后就是旅行商问题，其中可以用一次(taxi)，考虑(dp)状态为(f[i][msk][tag])，表示当前所在位置为(i)点，已经经过的节点集合为(msk)，是否用过(taxi)的情况下，所化的最小时间，最后再从走遍了所有点的状态往(0)转移即可。
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 2e4+7;
const int INF = 0x3f3f3f3f;
int n,p,m,g,t,dist[21][MAXN],f[17][1<<16][2];
vector<int> node;
pair<int,int> sta[MAXN];
vector<pair<int,int> > G[MAXN];
vector<int> vec;
void Dijkstra(int s, int* dis){
priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > > que;
dis[s] = 0; que.push(make_pair(dis[s],s));
while(!que.empty()){
auto pp = que.top(); que.pop();
int u = pp.second, d = pp.first;
if(dis[u]!=d) continue;
for(auto e : G[u]){
int v = e.first, w = e.second;
if(dis[u]+w<dis[v]){
dis[v] = dis[u] + w;
que.push(make_pair(dis[v],v));
}
}
}
}
void giao(){
for(int idx = 0; idx < (int)vec.size(); idx++){
int msk = vec[idx];
for(int i = 0; i < p; i++){
if((msk&(1<<i))==0) continue;
for(int j = 0; j < p; j++){
if(msk&(1<<j)) continue;
f[j][msk|(1<<j)][0] = min(f[j][msk|(1<<j)][0],f[i][msk][0] + dist[i][node[j]] + sta[j].second);
f[j][msk|(1<<j)][1] = min(f[j][msk|(1<<j)][1],min(f[i][msk][1]+dist[i][node[j]],f[i][msk][0]+t)+sta[j].second);
}
}
}
int msk = (1<<p) - 1;
for(int i = 0; i < p; i++){
f[0][1<<p][0] = min(f[0][1<<p][0],f[i][msk][0]+dist[i][0]);
f[0][1<<p][1] = min(f[0][1<<p][1],min(f[i][msk][0]+t,f[i][msk][1]+dist[i][0]));
}
}
int main(){
____();
cin >> n >> p >> m >> g >> t;
for(int i = 0; i < p; i++) cin >> sta[i].first >> sta[i].second;
sort(sta,sta+p);
for(int i = 0; i < p; i++) node.emplace_back(sta[i].first);
for(int i = 0; i < m; i++){
int u, v, w; cin >> u >> v >> w;
G[u].emplace_back(make_pair(v,w));
G[v].emplace_back(make_pair(u,w));
}
memset(dist,0x3f,sizeof(dist));
Dijkstra(0,dist[20]);
for(int i = 0; i < p; i++) Dijkstra(node[i],dist[i]);
for(int i = 1; i < (1<<p) - 1; i++) if(__builtin_popcount(i)>=1) vec.emplace_back(i);
sort(vec.begin(),vec.end(),[](const int x, const int rhs){
return __builtin_popcount(x) < __builtin_popcount(rhs);
});
memset(f,0x3f,sizeof(f));
for(int i = 0; i < p; i++){
f[i][1<<i][0] = dist[20][node[i]] + sta[i].second;
f[i][1<<i][1] = t + sta[i].second;
}
giao();
if(f[0][1<<p][0]<=g) cout << "possible without taxi" << endl;
else if(f[0][1<<p][1]<=g) cout << "possible with taxi" << endl;
else cout << "impossible" << endl;
return 0;
}
(B.Bounty Hunter II)
DAG最小路径覆盖 = 点数 - 最大匹配
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1111;
int vis[MAXN],n,match[MAXN];
vector<int> G[MAXN];
bool dfs(int u){
vis[u] = true;
for(int v : G[u]){
if(match[v]==-1 or (!vis[match[v]] and dfs(match[v]))){
match[v] = u;
return true;
}
}
return false;
}
int hungary(){
memset(match,255,sizeof(match));
int tot = 0;
for(int i = 0; i < n; i++){
memset(vis,0,sizeof(vis));
if(dfs(i)) tot++;
}
return tot;
}
int main(){
____();
cin >> n;
for(int i = 0; i < n; i++){
int m; cin >> m;
for(int j = 0; j < m; j++){
int v; cin >> v;
G[i].emplace_back(v);
}
}
cout << n - hungary() << endl;
return 0;
}
(C.Cake)
先计算出总面积(area)，对于每个角(x)，切掉的面积为(frac{e_1cdot e_2 cdot sinx / 2}{s^2})，其中(e_1，e_2)分别为角连的两边，(s)为切割比例，假设切掉的大小和为(S= sum frac{e_1cdot e_2 cdot sinx_i / 2}{s^2})，那么可以得到方程：(frac{area-S}{area}=a Rightarrow S=area-acdot area)接可以算出(s)了
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 111;
const double eps = 1e-7;
vector<double> edge,sinx;
pair<double,double> pt[MAXN];
double up,area;
int n;
double xpro(const pair<double,double> &A, const pair<double,double> &B){
return A.first * B.second - A.second * B.first;
}
pair<double,double> vect(const pair<double,double> &A, const pair<double,double> &B){
return make_pair(B.first-A.first,B.second-A.second);
}
double dist(const pair<double ,double> &A, const pair<double,double> &B){
return sqrt((A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second));
}
double calcutarea(){
double cutarea = 0;
cutarea += edge[0] * edge[n-1] * sinx[0] / 2;
for(int i = 1; i < n; i++) cutarea += edge[i-1] * edge[i] *sinx[i] / 2;
return cutarea;
}
int main(){
cin >> up >> n;
for(int i = 0; i < n; i++) cin >> pt[i].first >> pt[i].second;
for(int i = 1; i < n; i++) edge.emplace_back(dist(pt[i],pt[i-1]));
edge.emplace_back(dist(pt[n-1],pt[0]));
for(int i = 1; i < n - 1; i++) area += abs(xpro(vect(pt[0],pt[i]),vect(pt[0],pt[i+1]))/2);
sinx.emplace_back(xpro(vect(pt[0],pt[1]),vect(pt[0],pt[n-1]))/(edge[0]*edge[n-1]));
for(int i = 1; i < n - 1; i++) sinx.emplace_back(xpro(vect(pt[i],pt[i-1]),vect(pt[i],pt[i+1]))/(edge[i]*edge[i-1]));
sinx.emplace_back(xpro(vect(pt[n-1],pt[n-2]),vect(pt[n-1],pt[0]))/(edge[n-1]*edge[n-2]));
for(auto &s : sinx) s = fabs(s);
double cutarea = calcutarea();
cout << fixed << setprecision(10) << 1./sqrt((1-up)*area/cutarea) << endl;
return 0;
}
(D.Carpets)
给出一个大矩形和一些小矩形，问是否可以用其中一些小矩形组成大矩形。
考虑到小矩形只有7个，暴力枚举小矩形的放置方向和排列，然后按顺序放到大矩形中去，放入的规则是，找到在大矩形中还没有填充的最低点放置，如果放不下或者超出高度那就说明这样的排列是不行的。可以用set来维护一段连续的区间，由于还有高度，所以可以用map。
复杂度大概为(O(2^ncdot n!cdot n^2 logn))
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
vector<pair<int,int> > cp;
int w,h,c,n;
bool giao(vector<pair<int,int>> &vec){
map<pair<int,int>,int> seg;
int area = 0;
seg.insert(make_pair(make_pair(0,w),0));
for(auto rec : vec){
auto it = seg.begin();
for(auto p = seg.begin(); p != seg.end(); p++) if(p->second<it->second) it = p;
auto pr = make_pair(it->first,it->second);
seg.erase(it);
if(pr.first.second-pr.first.first<rec.first) return false;
if(pr.second+rec.second>h) return false;
area += rec.first * rec.second;
if(area==w*h) return true;
bool mg = false;
for(auto it = seg.begin(); it != seg.end(); it++){
if(it->first.second==pr.first.first and it->second==pr.second+rec.second){
auto np = make_pair(make_pair(it->first.first,pr.first.first+rec.first),pr.second+rec.second);
seg.erase(it);
seg.insert(np);
mg = true;
break;
}
}
if(!mg) seg.insert(make_pair(make_pair(pr.first.first,pr.first.first+rec.first),pr.second+rec.second));
if(pr.first.second-pr.first.first!=rec.first)
seg.insert(make_pair(make_pair(pr.first.first+rec.first,pr.first.second),pr.second));
}
return false;
}
bool solve(vector<pair<int,int> > &vec){
vector<int> permutation;
for(int i = 0; i < n; i++) permutation.emplace_back(i);
do{
vector<pair<int,int> > vv;
for(int i = 0; i < n; i++) vv.emplace_back(vec[permutation[i]]);
if(giao(vv)) return true;
}while(next_permutation(permutation.begin(),permutation.end()));
return false;
}
int main(){
____();
cin >> w >> h >> c;
for(int i = 1; i <= c; i++){
int num, x ,y;
cin >> num >> x >> y;
while(num--) cp.emplace_back(make_pair(x,y));
}
n = cp.size();
for(int msk = 0; msk < (1<<n); msk++){
vector<pair<int,int> > vec;
for(int i = 0; i < n; i++){
if(msk&(1<<i)) vec.emplace_back(make_pair(cp[i].second,cp[i].first));
else vec.emplace_back(cp[i]);
}
if(solve(vec)){
cout << "yes" << endl;
return 0;
}
}
cout << "no" << endl;
return 0;
}
(E.Change of Scenery)
输入的K是没有用的，就是问最短路是否不唯一
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
const int INF = 0x3f3f3f3f;
vector<pair<int,int>> G[MAXN];
int n,m,k,dist[MAXN],cnt[MAXN];
void Dijkstra(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
memset(dist,0x3f,sizeof(dist));
dist[1] = 0;
cnt[1] = 1;
que.push(make_pair(dist[1],1));
while(!que.empty()){
auto pp = que.top();
que.pop();
int u = pp.second, d = pp.first;
if(dist[u]!=d) continue;
for(auto e : G[u]){
int v = e.first, w = e.second;
if(dist[u]+w<dist[v]){
dist[v] = dist[u] + w;
que.push(make_pair(dist[v],v));
cnt[v] = cnt[u];
}
else if(dist[u]+w==dist[v]) cnt[v] += cnt[u];
cnt[v] = cnt[v] >= 2 ? 2 : cnt[v];
}
}
}
int main(){
scanf("%d %d %d",&n,&m,&k);
for(int i = 1; i <= k; i++){
int u;
cin >> u;
}
for(int i = 1; i <= m; i++){
int u, v, w;
cin >> u >> v >> w;
G[u].emplace_back(make_pair(v,w));
G[v].emplace_back(make_pair(u,w));
}
Dijkstra();
if(cnt[n]>1) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
(F.Divisions)
给一个数(n le 1e18)，问它有多少因子。
考虑大于(1e9)的时候通过(pollard\_rho)进行分解因子，小于(1e9)暴力分解，然后直到分出质因子，记录各个质因子出现的数量，现在就要通过这些质因子组成不同的数，假设各因子出现的次数为(a_1,a_2,a_3,...,a_p)，则易得答案为(Pi_{i=1}^p(a_i+1))
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
#define S 3
#define C 2730
using ll = int_fast64_t;
ll N;
map<ll,int> msk;
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll mul(ll a,ll b,ll n){return (a*b-(ll)(a/(long double)n*b+1e-3)*n+n)%n;}
inline ll pow(ll a,ll b, ll n){
ll d=1;
a%=n;
while(b){
if(b&1)d=mul(d,a,n);
a=mul(a,a,n);
b>>=1;
}
return d;
}
inline bool check(ll a,ll n){
ll m=n-1,x,y; int i,j=0;
while(!(m&1))m>>=1,j++;
x=pow(a,m,n);
for(i=1;i<=j;x=y,i++){
y=pow(x,2,n);
if((y==1)&&(x!=1)&&(x!=n-1))return 1;
}
return y!=1;
}
inline bool miller_rabin(int times, ll n){
if(n==1)return 0;
if(n==2)return 1;
if(!(n&1))return 0;
while(times--)if(check(rand()%(n-1)+1,n))return 0;
return 1;
}
inline ll pollard_rho(ll n,int c){
ll i=1,k=2,x=rand()%n,y=x,d;
while(1){
i++,x=(mul(x,x,n)+c)%n,d=gcd(y-x,n);
if(d>1&&d<n)return d;
if(y==x)return n;
if(i==k)y=x,k<<=1;
}
}
ll F=-1;
inline void findfac(ll n,int c){
if(n==1)return ;
if(miller_rabin(S,n)){
F=max(F,n);
return ;
}
ll m=n;
while(m==n)m=pollard_rho(n,c--);
findfac(m,c),findfac(n/m,c);
}
void solve(ll x){
if(x<=1e9){
for(int i = 2; i * i <= x; i++){
if(x%i!=0) continue;
while(x%i==0){
msk[i]++;
x/=i;
}
}
if(x!=1) msk[x]++;
return;
}
F = -1;
findfac(x,C);
if(F==x){
msk[F]++;
return;
}
ll y = x / F;
x = F;
solve(x); solve(y);
}
int main(){
cin >> N;
solve(N);
//findfac(N,C);
ll ret = 1;
for(auto p : msk) ret *= p.second + 1;
cout << ret << endl;
return 0;
}
(G.Extreme Sort)
签到，判断是否是排好序的序列即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1111;
int n,A[MAXN];
int main(){
____();
cin >> n;
for(int i = 1; i <= n; i++) cin >> A[i];
bool ok = true;
for(int i = 2; i <= n; i++){
if(A[i]<A[i-1]){
ok = false;
break;
}
}
if(!ok) cout << "no" << endl;
else cout << "yes" << endl;
return 0;
}
(H.Legacy Code)
签到
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 444;
int n,ID;
bool vis[MAXN];
map<string,int> mp;
vector<int> G[MAXN];
void dfs(int u){
vis[u] = true;
for(int v : G[u]) if(!vis[v]) dfs(v);
}
int main(){
____();
cin >> n;
for(int i = 1; i <= n; i++){
string s;
int m;
cin >> s >> m;
if(!mp.count(s)) mp.insert(make_pair(s,++ID));
int cid = mp.at(s);
while(m--){
cin >> s;
if(!mp.count(s)) mp.insert(make_pair(s,++ID));
G[mp.at(s)].emplace_back(cid);
}
}
for(auto p : mp){
if(vis[p.second]) continue;
string s = p.first;
int pos = find(s.begin(),s.end(),':') - s.begin();
string ns = s.substr(pos+2);
if(ns=="PROGRAM") dfs(p.second);
}
int ret = 0;
for(int i = 1; i <= n; i++) if(!vis[i]) ret++;
cout << ret << endl;
return 0;
}
(I.Milling machines)
签到，只要找每列能到达的最大位置即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e4+7;
int w,s,x,y,A[MAXN];
vector<int> pce[MAXN];
int main(){
____();
cin >> w >> s >> x >> y;
for(int i = 1; i <= w; i++){
pce[i].resize(x);
for(int j = 0; j < x; j++) cin >> pce[i][j];
}
for(int i = 1; i <= s; i++){
for(int j = 0; j < x; j++){
int p; cin >> p;
A[j] = max(A[j],p);
}
}
for(int i = 1; i <= w; i++){
for(int j = 0; j < x; j++) cout << pce[i][j] - max(0,(A[j]-y+pce[i][j])) << ' ';
cout << endl;
}
return 0;
}
(J.Souvenirs)
考虑(DP[i][x][y])表示现在在第(i)个商人的位置，金币还有(x)个，银币还有(y)个的情况下，能够买的最多是多少。
考虑转移，第一种情况就是不买，然后就是对于商人类别分类讨论即可，只有遇到(generous)的商人的时候才必须要花出去银币
利用滚动数组来优化空间
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 111;
int g,c,n,f[2][MAXN][MAXN*MAXN];
char buf[MAXN];
int main(){
____();
cin >> g >> c >> n;
int tag = 0,maxx = 0;
memset(f,255,sizeof(f));
f[tag][c][0] = 0;
for(int i = 1; i <= n; i++){
tag ^= 1;
memset(f[tag],255,sizeof(f[tag]));
int fc, p;
cin >> buf >> fc >> p;
for(int x = 0; x <= c; x++) for(int y = 0; y <= g * g; y++){
f[tag][x][y] = max(f[tag][x][y],f[tag^1][x][y]);
if((x==0 and y<p) or f[tag^1][x][y]==-1) continue;
if(buf[1]=='e'){
if(y>=p) f[tag][x][y-p] = max(f[tag][x][y-p],f[tag^1][x][y]+1);
else if(x){
int lft = ((g-p)/fc+((g-p)%fc?1:0)) * fc;
lft += y;
f[tag][x-1][lft] = max(f[tag][x-1][lft],f[tag^1][x][y]+1);
}
}
else{
if(y>=p) f[tag][x][y-p] = max(f[tag][x][y-p],f[tag^1][x][y]+1);
if(x){
int lft;
if(buf[0]=='g') lft = (g-p)/fc*fc;
else lft = round(1.*(g-p)/fc)*fc;
f[tag][x-1][y+lft] = max(f[tag][x-1][y+lft],f[tag^1][x][y]+1);
}
}
}
}
for(int i = 0; i <= c; i++) for(int j = 0; j <= g * g; j++) maxx = max(maxx,f[tag][i][j]);
cout << maxx << endl;
return 0;
}
(K.Upside down primes)
判断翻转串是否合法，然后对原串和翻转串判断是否是素数即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
using ll = int_fast64_t;
#define C 2750
#define S 3
ll n;
int exc(int x){
if(x==0 or x==2 or x==5 or x==8 or x==1) return x;
else if(x==6) return x + 3;
else return x - 3;
}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
inline ll mul(ll a,ll b,ll n){return (a*b-(ll)(a/(long double)n*b+1e-3)*n+n)%n;}
inline ll pow(ll a,ll b, ll n){
ll d=1;
a%=n;
while(b){
if(b&1)d=mul(d,a,n);
a=mul(a,a,n);
b>>=1;
}
return d;
}
inline bool check(ll a,ll n){
ll m=n-1,x,y; int i,j=0;
while(!(m&1))m>>=1,j++;
x=pow(a,m,n);
for(i=1;i<=j;x=y,i++){
y=pow(x,2,n);
if((y==1)&&(x!=1)&&(x!=n-1))return 1;
}
return y!=1;
}
inline bool miller_rabin(int times, ll n){
ll a;
if(n==1)return 0;
if(n==2)return 1;
if(!(n&1))return 0;
while(times--)if(check(rand()%(n-1)+1,n))return 0;
return 1;
}
inline ll pollard_rho(ll n,int c){
ll i=1,k=2,x=rand()%n,y=x,d;
while(1){
i++,x=(mul(x,x,n)+c)%n,d=gcd(y-x,n);
if(d>1&&d<n)return d;
if(y==x)return n;
if(i==k)y=x,k<<=1;
}
}
ll F=-1;
inline void findfac(ll n,int c){
if(n==1)return ;
if(miller_rabin(S,n)){
F=max(F,n);
return ;
}
ll m=n;
while(m==n)m=pollard_rho(n,c--);
findfac(m,c),findfac(n/m,c);
}
bool isprime(ll x){
F = -1;
findfac(x,C);
return F==x;
}
int main(){
cin >> n;
if(!isprime(n)){
cout << "no" << endl;
return 0;
}
ll m = 0;
bool ok = true;
while(n){
if(n%10==3 or n%10==4 or n%10==7){
ok = false;
break;
}
m = m * 10 + exc(n%10);
n /= 10;
}
if(!ok){
cout << "no" << endl;
return 0;
}
if(isprime(m)) cout << "yes" << endl;
else cout << "no" << endl;
return 0;
}
(L.Treasure)
(M.Sums)
同余最短路模板题，以(a_0)为模，建边跑最短路，设当前位置为(u)，模为(A_0)，分两种情况
- (u+A_i<A_0)，此时(u)向(u+A_i)连边距离为(0)
- (u+A_i>=A_0)，此时(u)向((u+A_i)%A_0)连边的距离为(1)
得到的是模(A_0)意义下最小的那个可以到达的数的循环次数
最后判断(x)是否可达，只要判断(dist[x%A_0])是否小于等于(x/A_0)即可
//#pragma GCC optimize("O3")
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 5e4+7;
const int INF = 0x3f3f3f3f;
vector<int> A;
int n,m,dist[MAXN];
void Dijkstra(){
memset(dist,0x3f,sizeof(dist));
dist[0] = 0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;
que.push(make_pair(dist[0],0));
while(!que.empty()){
auto p = que.top();
que.pop();
int d = p.first, u = p.second;
if(dist[u]!=d) continue;
for(int i = 1; i < n; i++){
int v = (u+A[i])%A[0];
int w = (u+A[i])/A[0];
if(dist[u]+w<dist[v]){
dist[v] = dist[u] + w;
que.push(make_pair(dist[v],v));
}
}
}
}
int main(){
____();
cin >> n;
A.resize(n);
for(int i = 0; i < n; i++) cin >> A[i];
Dijkstra();
cin >> m;
while(m--){
int x; cin >> x;
cout << (dist[x%A[0]]<=x/A[0]?"TAK":"NIE") << endl;
}
return 0;
}