#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
const int NM = 5005;
i128 LIM = 1;
int K, Q, D, M, sz, a[NM+5];
vector <i128> pw;
i128 n;
pair <int, pii> dp[105][NM+5][2];
vector <int> ans;
void solve(){
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= D; i++){
if (a[i] > n/pw[sz-1]) continue;
if (n/pw[sz-1]-a[i] > 2*M) continue;
dp[sz-1][n/pw[sz-1]-a[i]][i != D] = mp(i, mp(-1, -1));
}
for (int i = sz-1; i > 0; i--){
for (int j = 0; j <= 2*M; j++)
for (int b = 0; b < 2; b++){
if (dp[i][j][b].fi == -1) continue;
for (int t = 1; t <= D; t++){
ll tmp = 1LL*j*K+(n/pw[i-1])%K-a[t];
if (tmp < 0 || tmp > 2*M) continue;
if (b == 1 && t == D) continue;
dp[i-1][tmp][b|(t < D)] = mp(t, mp(j, b));
}
}
}
if (dp[0][0][1].fi == -1){
cout << "IMPOSSIBLE\n";
return;
}
ans.clear();
int j = 0;
for (int i = 0; i < sz; i++){
ans.push_back(a[dp[i][j][1].fi]-M);
if (dp[i][j][1].se.se == 0) break;
j = dp[i][j][1].se.fi;
}
while ((int)ans.size() > 1 && ans.back() == 0) ans.pop_back();
reverse(ans.begin(), ans.end());
for (int x : ans) cout << x << ' ';
cout << '\n';
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for (int i = 1; i <= 24; i++) LIM *= 10;
cin >> K >> Q >> D >> M;
for (int i = 1; i <= D; i++){
cin >> a[i];
a[i] += M;
}
a[++D] = M;
pw.push_back(1);
while (true){
i128 x = pw.back()*K;
pw.push_back(x);
if (x > LIM) break;
}
sz = (int)pw.size();
while (Q--){
ll x; cin >> x;
n = x;
for (i128 x : pw) n += M*x;
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12624 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12624 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
