//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;
} else if (std::abs(num) < M) {
return IMPOSSIBLE;
}
for (auto digit: digits) {
int newNum = num - digit;
if (newNum % 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;
}
std::stack<int> result;
while (number) {
// int next = (number % K);
// next = (next + std::abs(next) * K) % K;
int digit = dp(number);
// if (digits.count(next)) {
// digit = next;
// } else if (digits.count(next - K)) {
// digit = next - K;
// } else if (digits.count(next + K)) {
// digit = next + K;
// } else {
// goto broken;
// }
if (digit == IMPOSSIBLE) goto broken;
result.push(digit);
number -= digit;
number /= K;
}
while (!result.empty()) {
std::cout << result.top() << " ";
result.pop();
}
std::cout << std::endl;
continue;
broken:
std::cout << "IMPOSSIBLE" << std::endl;
}
}
| # |
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 |
- |
