oj.uz

답안 #732546

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
732546 2023-04-29T05:52:20 Z Programmer123 Weird Numeral System (CCO21_day1problem2) C++17
0 / 25
 0 ms 212 KB 
//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;
            }
        } else {
            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;
            }
        }
    }
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Expected integer, but "IMPOSSIBLE" found
2 Halted 0 ms 0 KB -