//8 out of 25 marks - no overflows possible
#include <bits/stdc++.h>
#define int long long int
#define IMPOSSIBLE 10000
std::set<int> digits;
int K, M;
std::unordered_map<int, int> answer;
int dp(int num) {
if (answer.count(num)) return answer[num];
if (digits.count(num)) {
answer[num] = num;
return num;
}
for (auto digit: digits) {
int newNum = num - digit;
if ((newNum + std::abs(newNum) * K) % K) continue;
if (dp(newNum / K) == IMPOSSIBLE) continue;
answer[num] = digit;
return digit;
}
answer[num] = IMPOSSIBLE;
return IMPOSSIBLE;
}
signed main() {
int Q, D;
std::cin >> K >> Q >> D >> M;
bool has0 = false;
for (int i = 0; i < D; ++i) {
int a;
std::cin >> a;
if (a == 0) has0 = true;
digits.insert(a);
}
for (int _ = 0; _ < Q; ++_) {
int number;
std::cin >> number;
if (number == 0) {
if (has0) {
std::cout << "0" << std::endl;
} else {
std::cout << "IMPOSSIBLE" << std::endl;
}
continue;
}
if (dp(number) != IMPOSSIBLE) {
std::stack<int> result;
while (number) {
int digit = dp(number);
assert(digit != IMPOSSIBLE);
result.push(digit);
number -= digit;
number /= K;
}
while (!result.empty()) {
std::cout << result.top() << " ";
result.pop();
}
std::cout << std::endl;
} else {
std::cout << "IMPOSSIBLE" << std::endl;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Expected integer, but "IMPOSSIBLE" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
