Power Decomposition

Given an integer n, output its representation as a sum of distinct powers of two in descending order, or -1 if n is odd.

#include <iostream>
using namespace std;

int main() {
    int val;
    cin >> val;
    if (val % 2 != 0) {
        cout << "-1";
        return 0;
    }
    for (int exponent = 30; exponent >= 0; --exponent) {
        if (val & (1 << exponent)) {
            cout << (1 << exponent) << " ";
        }
    }
    return 0;
}

Score Ranking

For each new score x in a sequence, detemrine the score at the max(1, i * w / 100)-th position in the sorted list of scores seen so far, where i is the count of scores.

#include <iostream>
#include <algorithm>
using namespace std;

int freq[601];

int main() {
    int totalScores, percentage;
    cin >> totalScores >> percentage;
    for (int idx = 1; idx <= totalScores; ++idx) {
        int score;
        cin >> score;
        ++freq[score];
        int currentCount = freq[600];
        int targetRank = max(1, idx * percentage / 100);
        for (int j = 599; j >= 0; --j) {
            currentCount += freq[j];
            if (currentCount >= targetRank) {
                cout << j << " ";
                break;
            }
        }
    }
    return 0;
}

Boolean Expression Evaluation

Evaluate a boolean expression tree and determine for each variable whether changing its value affects the overall result.

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int type; // >0: variable index, -2: AND, -3: OR
    int left, right;
    bool value;
    bool inverted;
} nodes[1000010];

bool varValues[100010];
bool isIrrelevant[100010];
stack<int> nodeStack;
int nodeCount;

void markIrrelevant(int nodeIdx) {
    if (nodeIdx == -1) return;
    if (nodes[nodeIdx].type > 0 && isIrrelevant[nodes[nodeIdx].type]) return;
    if (nodes[nodeIdx].type > 0) {
        isIrrelevant[nodes[nodeIdx].type] = true;
    } else {
        markIrrelevant(nodes[nodeIdx].left);
        markIrrelevant(nodes[nodeIdx].right);
    }
}

int main() {
    char ch;
    while ((ch = getchar()) >= 32) {
        if (ch == ' ') continue;
        if (ch == 'x') {
            int varIdx;
            scanf("%d", &varIdx);
            nodes[++nodeCount].type = varIdx;
            nodes[nodeCount].left = nodes[nodeCount].right = -1;
            nodeStack.push(nodeCount);
        }
        if (ch == '!') nodes[nodeStack.top()].inverted ^= 1;
        if (ch == '&') {
            nodes[++nodeCount].type = -2;
            nodes[nodeCount].right = nodeStack.top(); nodeStack.pop();
            nodes[nodeCount].left = nodeStack.top(); nodeStack.pop();
            nodeStack.push(nodeCount);
        }
        if (ch == '|') {
            nodes[++nodeCount].type = -3;
            nodes[nodeCount].right = nodeStack.top(); nodeStack.pop();
            nodes[nodeCount].left = nodeStack.top(); nodeStack.pop();
            nodeStack.push(nodeCount);
        }
    }
    int varCount;
    cin >> varCount;
    for (int i = 1; i <= varCount; ++i) {
        while ((ch = getchar()) <= 32);
        varValues[i] = ch - '0';
    }
    for (int i = 1; i <= nodeCount; ++i) {
        if (nodes[i].type > 0) {
            nodes[i].value = varValues[nodes[i].type] ^ nodes[i].inverted;
        }
        if (nodes[i].type == -2) {
            bool leftVal = nodes[nodes[i].left].value;
            bool rightVal = nodes[nodes[i].right].value;
            if (!leftVal) markIrrelevant(nodes[i].right);
            if (!rightVal) markIrrelevant(nodes[i].left);
            nodes[i].value = (leftVal & rightVal) ^ nodes[i].inverted;
        }
        if (nodes[i].type == -3) {
            bool leftVal = nodes[nodes[i].left].value;
            bool rightVal = nodes[nodes[i].right].value;
            if (leftVal) markIrrelevant(nodes[i].right);
            if (rightVal) markIrrelevant(nodes[i].left);
            nodes[i].value = (leftVal | rightVal) ^ nodes[i].inverted;
        }
    }
    int queries;
    cin >> queries;
    while (queries--) {
        int varIdx;
        cin >> varIdx;
        cout << (isIrrelevant[varIdx] ? nodes[nodeCount].value : !nodes[nodeCount].value) << endl;
    }
    return 0;
}

Grid Path Maximization

Find the maximum sum path from the top-left to bottom-right in a grid, moving right, up, or down, without revisiting cells.

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const LL NEG_INF = -1e18;
int grid[1001][1001];
LL memo[1001][1001][2];
int rows, cols;

LL maxThree(LL a, LL b, LL c) {
    return max(a, max(b, c));
}

LL explore(int r, int c, int dir) {
    if (r < 1 || r > rows || c < 1 || c > cols) return NEG_INF;
    if (memo[r][c][dir] != NEG_INF) return memo[r][c][dir];
    if (dir == 0) {
        memo[r][c][dir] = maxThree(explore(r - 1, c, 0), explore(r, c - 1, 0), explore(r, c - 1, 1)) + grid[r][c];
    } else {
        memo[r][c][dir] = maxThree(explore(r + 1, c, 1), explore(r, c - 1, 0), explore(r, c - 1, 1)) + grid[r][c];
    }
    return memo[r][c][dir];
}

int main() {
    cin >> rows >> cols;
    for (int i = 1; i <= rows; ++i) {
        for (int j = 1; j <= cols; ++j) {
            cin >> grid[i][j];
            memo[i][j][0] = memo[i][j][1] = NEG_INF;
        }
    }
    memo[1][1][0] = memo[1][1][1] = grid[1][1];
    cout << explore(rows, cols, 0);
    return 0;
}

Julian Date Conversion

Convert a day count since a reference date into a calendar date, handling Julian and Gregorian calendar rules.

#include <iostream>
using namespace std;

int monthDays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

struct Date {
    int month, day;
};

Date dayToDate(int dayOfYear, bool isLeap) {
    Date result = {1, 1};
    int currentDay = 0;
    while (currentDay < dayOfYear) {
        ++currentDay;
        ++result.day;
        if (result.day > 28) {
            if (result.month == 2) {
                if (!isLeap && result.day == 29) {
                    result.month = 3;
                    result.day = 1;
                }
                if (isLeap && result.day == 30) {
                    result.month = 3;
                    result.day = 1;
                }
            } else if (result.day > monthDays[result.month]) {
                ++result.month;
                result.day = 1;
            }
        }
    }
    return result;
}

void convertDate(long long days) {
    if (days <= 1721423) {
        int year = -4713;
        year += 4 * (days / 1461);
        days %= 1461;
        if (days < 366) {
            Date d = dayToDate(days, true);
            cout << d.day << " " << d.month << " " << -year << " BC" << endl;
            return;
        } else {
            --days;
            year += days / 365;
            days %= 365;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " " << -year << " BC" << endl;
            return;
        }
    }
    if (days <= 2299160) {
        days -= 1721424;
        int year = 1;
        year += 4 * (days / 1461);
        days %= 1461;
        if (days < 1095) {
            year += days / 365;
            days %= 365;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        } else {
            year += 3;
            days -= 1095;
            Date d = dayToDate(days, true);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        }
    }
    if (days <= 2305813) {
        if (days <= 2299238) {
            days -= 2299161;
            days += 15;
            if (days <= 31) cout << days << " 10 1582" << endl;
            else if (days <= 61) cout << days - 31 << " 11 1582" << endl;
            else cout << days - 61 << " 12 1582" << endl;
            return;
        }
        if (days <= 2299603) {
            days -= 2299239;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " 1583" << endl;
            return;
        }
        if (days <= 2299969) {
            days -= 2299604;
            Date d = dayToDate(days, true);
            cout << d.day << " " << d.month << " 1584" << endl;
            return;
        }
        days -= 2299970;
        int year = 1585;
        year += 4 * (days / 1461);
        days %= 1461;
        if (days < 1095) {
            year += days / 365;
            days %= 365;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        } else {
            year += 3;
            days -= 1095;
            Date d = dayToDate(days, true);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        }
    }
    days -= 2305814;
    long long year = 1601;
    year += 400 * (days / 146097);
    days %= 146097;
    if (days <= 109572) {
        year += 100 * (days / 36524);
        days %= 36524;
        if (days <= 35064) {
            year += 4 * (days / 1461);
            days %= 1461;
            if (days <= 1095) {
                year += days / 365;
                days %= 365;
                Date d = dayToDate(days, false);
                cout << d.day << " " << d.month << " " << year << endl;
                return;
            } else {
                year += 3;
                days -= 1095;
                Date d = dayToDate(days, true);
                cout << d.day << " " << d.month << " " << year << endl;
                return;
            }
        } else {
            year += 96;
            days -= 35064;
            year += days / 365;
            days %= 365;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        }
    } else {
        year += 300;
        days -= 109572;
        year += 4 * (days / 1461);
        days %= 1461;
        if (days <= 1095) {
            year += days / 365;
            days %= 365;
            Date d = dayToDate(days, false);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        } else {
            year += 3;
            days -= 1095;
            Date d = dayToDate(days, true);
            cout << d.day << " " << d.month << " " << year << endl;
            return;
        }
    }
}

int main() {
    int queries;
    cin >> queries;
    while (queries--) {
        long long days;
        cin >> days;
        convertDate(days);
    }
    return 0;
}

Zoo Animal Countign

Calculate the number of possible new animals that can be added to a zoo based on existing animals and feed requirements.

#include <iostream>
using namespace std;

typedef unsigned long long ULL;

int main() {
    int existing, feeds, bits, totalBits;
    cin >> existing >> feeds >> bits >> totalBits;
    ULL animalMask = 0;
    for (int i = 0; i < existing; ++i) {
        ULL animal;
        cin >> animal;
        animalMask |= animal;
    }
    bool hasBit[65] = {false};
    bool needsFeed[65] = {false};
    for (int i = 0; i < totalBits; ++i) {
        hasBit[i] = animalMask & 1;
        animalMask >>= 1;
    }
    for (int i = 0; i < feeds; ++i) {
        int bitPos;
        ULL feedType;
        cin >> bitPos >> feedType;
        needsFeed[bitPos] = true;
    }
    int freeBits = 0;
    for (int i = 0; i < totalBits; ++i) {
        if (hasBit[i] || !needsFeed[i]) {
            ++freeBits;
        }
    }
    ULL totalPossible = (ULL(1) << freeBits);
    if (freeBits == 64 && existing == 0) {
        cout << "18446744073709551616";
    } else if (freeBits == 0) {
        cout << "0";
    } else {
        cout << totalPossible - existing;
    }
    return 0;
}