#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 - K * (newNum / K) != 0) 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;
for (int i = 0; i < D; ++i) {
int a;
std::cin >> a;
if (a == IMPOSSIBLE) {
assert(false);
}
digits.insert(a);
}
for (int _ = 0; _ < Q; ++_) {
int number;
std::cin >> number;
if (dp(number) != IMPOSSIBLE) {
std::stack<int> result;
result.push(dp(number));
number = (number - dp(number)) / K;
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 |
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 |
- |
