#include<bits/stdc++.h>
using namespace std;
const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = -1;
void solve() {
int k,q,d,m;
cin >> k >> q >> d >> m;
vector<int> a;
for(int i = 1; i <= d; i++) {
int x; cin >> x;
a.pb(x);
}
sort(all(a));
a.erase(unique(all(a)),a.end());
while(q--) {
int n; cin >> n;
if(n == 0) {
bool ok = false;
for(auto x : a) if(x == 0) ok = true;
if(ok) cout << 0 << endl;
else cout << "IMPOSSIBLE" << endl;
break;
}
vector<map<int,int>> dp(65);
dp[0][n] = 0;
int i = 0;
while(dp[i].count(0) == 0 && dp[i].size() != 0) {
for(auto X : dp[i]) {
int nn = X.fr;
for(auto x : a) {
if((x%k+k)%k == (nn%k+k)%k) {
dp[i+1][(nn-x)/k] = x;
}
}
}
i++;
}
if(dp[i].count(0) != 0) {
vector<int> ans;
int nn = 0;
while(i != 0) {
ans.pb(dp[i][nn]);
nn = nn*k+dp[i][nn];
// cout << nn << endl;
i--;
}
for(auto x : ans) cout << x << " ";
cout << endl;
}
else {
cout << "IMPOSSIBLE" << endl;
}
}
}
int32_t main() {
ios::sync_with_stdio(false); cin.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
int tt = 1;
// cin >> tt;
while(tt--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
