Programming Competition Solutions

Problem A - Sum Calculation

#include <iostream>
#include <climits>

typedef long long ll;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    ll total = 0, limit = 0;
    std::cin >> limit;
    
    ll current = 1, accumulated = 0;
    while (accumulated < limit) {
        total += current * std::min(current, limit - accumulated);
        accumulated += current;
        current++;
    }
    
    std::cout << total << '\n';
    return 0;
}

Problem B - Binary Digit Counter

#include <iostream>
#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string input;
    std::cin >> input;
    
    int count = 0;
    for (char c : input) {
        if (c == '1') {
            count++;
        }
    }
    
    std::cout << count << '\n';
    return 0;
}

Problem C - Character Counter

#include <iostream>
#include <string>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::string text;
    std::getline(std::cin, text);
    
    int length = text.length();
    for (char c : text) {
        if (c == ' ') {
            length--;
        }
    }
    
    std::cout << length << '\n';
    return 0;
}

Problem D - Comparison

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    long long x, y, z;
    std::cin >> x >> y >> z;
    
    if (x * x > y * z) {
        std::cout << "Alice\n";
    } else {
        std::cout << "Bob\n";
    }
    
    return 0;
}

Problem E - Load Balancing

#include <iostream>
#include <vector>
#include <climits>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int items, containers;
    std::cin >> items >> containers;
    
    std::vector<int> weights(items);
    int max_weight = 0, total_weight = 0;
    
    for (int i = 0; i < items; i++) {
        std::cin >> weights[i];
        max_weight = std::max(max_weight, weights[i]);
        total_weight += weights[i];
    }
    
    if (items <= containers) {
        std::cout << max_weight << '\n';
    } else {
        std::vector<int> loads(containers, 0);
        
        for (int i = 0; i < items; i++) {
            int min_load = INT_MAX, min_index = -1;
            
            for (int j = 0; j < containers; j++) {
                if (loads[j] < min_load) {
                    min_load = loads[j];
                    min_index = j;
                }
            }
            
            loads[min_index] += weights[i];
        }
        
        int max_load = 0;
        for (int load : loads) {
            max_load = std::max(max_load, load);
        }
        
        std::cout << max_load << '\n';
    }
    
    return 0;
}

Problem F - Binary Decomposition

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int number;
    std::cin >> number;
    
    if (number % 2 != 0) {
        std::cout << "-1\n";
    } else {
        for (int i = 30; i >= 0; i--) {
            int power = 1 << i;
            if (number >= power) {
                std::cout << power << " ";
                number -= power;
            }
        }
        std::cout << '\n';
    }
    
    return 0;
}

Problem G - Grid Counter

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int rows, cols;
    std::cin >> rows >> cols;
    
    std::vector grid(rows);
    for (auto &row : grid) {
        std::cin >> row;
    }
    
    int dx[] = {1, 1, 1, -1, -1, -1, 0, 0};
    int dy[] = {1, 0, -1, 1, 0, -1, 1, -1};
    std::vector result(rows, std::vector<int>(cols, 0));
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '*') {
                for (int k = 0; k < 8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < rows && y >= 0 && y < cols) {
                        result[x][y]++;
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '*') {
                std::cout << '*';
            } else {
                std::cout << result[i][j];
            }
        }
        std::cout << '\n';
    }
    
    return 0;
}

Problem H - String Formatter

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int p1, p2, p3;
    std::string input;
    std::cin >> p1 >> p2 >> p3 >> input;
    
    std::string output = "";
    output += input[0];
    
    for (int i = 1; i < input.size() - 1; i++) {
        if (input[i] == '-' && input[i + 1] > input[i - 1]) {
            if (input[i - 1] + 1 == input[i + 1]) {
                continue;
            }
            
            std::string segment = "";
            char start = input[i - 1] + 1;
            char end = input[i + 1] - 1;
            
            if (input[i - 1] >= '0' && input[i + 1] <= '9') {
                for (char c = start; c <= end; c++) {
                    segment += std::string(p2, c);
                }
            } else if (input[i - 1] >= 'a' && input[i + 1] <= 'z') {
                if (p1 == 2) {
                    start -= 32;
                    end -= 32;
                }
                for (char c = start; c <= end; c++) {
                    segment += std::string(p2, c);
                }
            } else {
                output += input[i];
                continue;
            }
            
            if (p1 == 3) {
                segment = std::string(segment.size(), '*');
            }
            if (p3 == 2) {
                std::reverse(segment.begin(), segment.end());
            }
            
            output += segment;
        } else {
            output += input[i];
        }
    }
    output += input.back();
    
    std::cout << output;
    
    return 0;
}

Problem I - Gray Code Conversion

#include <iostream>
#include <string>

typedef long long ll;

void convertToGray(ll num, ll bits, std::string &result) {
    if (bits == 0) {
        std::cout << result << '\n';
        return;
    }
    
    if (num >= (1ll << (bits - 1))) {
        result += '1';
        convertToGray((1ll << bits) - 1 - num, bits - 1, result);
    } else {
        result += '0';
        convertToGray(num, bits - 1, result);
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    ll bits, number;
    std::cin >> bits >> number;
    
    std::string grayCode = "";
    convertToGray(number, bits, grayCode);
    
    return 0;
}

Problem J - Tournament Simulation

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int participants, rounds, query;
    std::cin >> participants >> rounds >> query;
    participants *= 2;
    query--;
    
    std::vector data(participants, std::vector<int>(3));
    std::vector winners(participants/2), losers(participants/2);
    
    for (int i = 0; i < participants; i++) {
        std::cin >> data[i][0];
        data[i][1] = i + 1;
    }
    
    for (int i = 0; i < participants; i++) {
        std::cin >> data[i][2];
    }
    
    auto compare = [](const std::vector<int> &a, const std::vector<int> &b) -> bool {
        if (a[0] == b[0]) {
            return a[1] < b[1];
        }
        return a[0] > b[0];
    };
    
    std::sort(data.begin(), data.end(), compare);
    
    while (rounds--) {
        for (int i = 0; i < participants; i += 2) {
            if (data[i][2] > data[i + 1][2]) {
                data[i][0]++;
                winners[i/2] = data[i];
                losers[i/2] = data[i + 1];
            } else {
                data[i + 1][0]++;
                winners[i/2] = data[i + 1];
                losers[i/2] = data[i];
            }
        }
        
        int left = 0, right = 0;
        for (int i = 0; i < participants; i++) {
            if (left < winners.size() && (right >= losers.size() || compare(winners[left], losers[right]))) {
                data[i] = winners[left++];
            } else {
                data[i] = losers[right++];
            }
        }
    }
    
    std::cout << data[query][1] << '\n';
    
    return 0;
}

Problem K - Sliding Window Tracker

#include <iostream>
#include <vector>
#include <deque>
#include <set>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::vector ships(n);
    std::deque<int> timestamps;
    std::vector<int> counts(100010, 0);
    std::set<int> unique_items;
    std::vector<int> times(n);
    
    for (int i = 0; i < n; i++) {
        int p;
        std::cin >> times[i] >> p;
        
        for (int j = 0; j < p; j++) {
            int item;
            std::cin >> item;
            ships[i].push_back(item);
            counts[item]++;
            unique_items.insert(item);
        }
        
        timestamps.push_back(i);
        
        while (times[timestamps.front()] <= times[i] - 86400) {
            int idx = timestamps.front();
            for (int item : ships[idx]) {
                if (!--counts[item]) {
                    unique_items.erase(item);
                }
            }
            timestamps.pop_front();
        }
        
        std::cout << unique_items.size() << '\n';
    }
    
    return 0;
}

Problem N - Maximum Subarrays

#include <iostream>
#include <queue>
#include <cmath>

typedef long long ll;

const int MAX = 500010;
ll prefix[MAX], st[MAX][20];

void buildST(int n) {
    for (int i = 1; i <= n; i++) {
        st[i][0] = i;
    }
    
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            int left = st[i][j - 1];
            int right = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = (prefix[left] > prefix[right]) ? left : right;
        }
    }
}

int queryRMQ(int l, int r) {
    if (r < l) return -1;
    int k = log2(r - l + 1);
    int left = st[l][k];
    int right = st[r - (1 << k) + 1][k];
    return (prefix[left] > prefix[right]) ? left : right;
}

struct Subarray {
    int origin, left, right, pos;
    
    Subarray(int o, int l, int r) : origin(o), left(l), right(r), pos(queryRMQ(l, r)) {}
    
    bool operator<(const Subarray &other) const {
        ll sum1 = prefix[pos] - prefix[origin - 1];
        ll sum2 = prefix[other.pos] - prefix[other.origin - 1];
        return sum1 < sum2;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, k, L, R;
    std::cin >> n >> k >> L >> R;
    
    for (int i = 1; i <= n; i++) {
        std::cin >> prefix[i];
        prefix[i] += prefix[i - 1];
    }
    
    buildST(n);
    
    std::priority_queue<Subarray> pq;
    
    for (int i = 1; i <= n; i++) {
        int left_bound = i + L - 1;
        int right_bound = std::min(i + R - 1, n);
        if (left_bound <= n) {
            pq.push(Subarray(i, left_bound, right_bound));
        }
    }
    
    ll total = 0;
    while (k--) {
        Subarray current = pq.top();
        pq.pop();
        
        total += prefix[current.pos] - prefix[current.origin - 1];
        
        if (current.left != current.pos) {
            pq.push(Subarray(current.origin, current.left, current.pos - 1));
        }
        
        if (current.right != current.pos) {
            pq.push(Subarray(current.origin, current.pos + 1, current.right));
        }
    }
    
    std::cout << total << '\n';
    return 0;
}