#include <bits/stdc++.h>
using namespace std;
#if __cplusplus > 201703L
#include <ranges>
using namespace numbers;
#endif
int main(){
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(ios::badbit | ios::failbit);
int base, qn, dn, r;
cin >> base >> qn >> dn >> r;
vector<int> d(dn);
copy_n(istream_iterator<int>(cin), dn, d.begin());
sort(d.begin(), d.end());
for(auto qi = 0; qi < qn; ++ qi){
long long obj;
cin >> obj;
vector<long long> minval{obj};
vector dp(1, vector<int>(1, true));
vector prev(1, vector(1, array{-1, -1}));
for(auto i = 0; !dp[i].empty() && i <= 100; ++ i){
minval.push_back((minval.back() - d.back()) / base - 1);
dp.emplace_back();
prev.emplace_back();
for(auto x = 0; x < (int)dp[i].size(); ++ x){
if(!dp[i][x]){
continue;
}
for(auto y: d){
if((minval[i] + x - y) % base){
continue;
}
int nx = (minval[i] + x - y) / base - minval[i + 1];
assert(0 <= nx && nx <= 10000);
dp[i + 1].resize(max(nx + 1, (int)dp[i + 1].size()));
prev[i + 1].resize((int)dp[i + 1].size(), {-1, -1});
dp[i + 1][nx] = true;
prev[i + 1][nx] = {x, y};
}
if(0 <= -minval[i + 1] && -minval[i + 1] < (int)dp[i + 1].size() && dp[i + 1][-minval[i + 1]]){
for(auto x = -minval[i + 1]; i >= 0; -- i){
cout << prev[i + 1][x][1] << " ";
x = prev[i + 1][x][0];
}
cout << "\n";
goto NEXT;
}
}
}
cout << "IMPOSSIBLE\n";
NEXT:;
}
return 0;
}
/*
*/
////////////////////////////////////////////////////////////////////////////////////////
// //
// Coded by Aeren //
// //
////////////////////////////////////////////////////////////////////////////////////////
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
