#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int K, Q, D, M;
cin >> K >> Q >> D >> M;
vector<int> digits(D);
for (int i = 0; i < D; i++) {
cin >> digits[i];
}
while (Q--) {
long long N;
cin >> N;
map<long long, int> par;
for (int d : digits) {
par[d] = d;
}
const int IMPOSSIBLE = 6785;
auto backtrack = [&](auto self, long long n) -> bool {
if (par.count(n)) return par[n] != IMPOSSIBLE;
for (int d : digits) {
if ((n - d) % K == 0 && self(self, (n - d) / K)) {
par[n] = d;
return true;
}
}
par[n] = IMPOSSIBLE;
return false;
};
if (!backtrack(backtrack, N)) {
cout << "IMPOSSIBLE\n";
} else {
vector<int> ans;
while (par.count(N)) {
int d = par[N];
ans.push_back(d);
N = (N - d) / K;
}
for (int i = ans.size() - 1; i >= 0; i--) {
cout << ans[i] << " \n"[i == 0];
}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |