Submission #732541

#	Time	Username	Problem	Language	Result	Execution time	Memory
732541		Programmer123	Weird Numeral System (CCO21_day1problem2)	C++17	0 / 25	1 ms	212 KiB

Main

//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;
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17