The input consists of an arithmetic expression in the form a + b or a - b. Parse the expression and output the computed result.

int main() {
    int operand1, operand2;
    char operation;
    std::cin >> operand1 >> operation >> operand2;
    
    if (operation == '+') {
        std::cout << operand1 + operand2 << "\n";
    } else {
        std::cout << operand1 - operand2 << "\n";
    }
    return 0;
}

Problem B: Contest with Energy Drinks

Problem Statement:

A programming contest has N problems. Solving the i-th problem requires T[i] seconds.

There are M energy drinks available. The i-th drink reduces the solving time of problem P[i] to X[i] seconds, without affecting other problems.

The total solving time is the sum of time needed for all problems. For each of the M queries, determine the total time required if you consume exactly the i-th drink.

Constraints: 1 ≤ N, M ≤ 100, 1 ≤ T[i], X[i] ≤ 10^5, 1 ≤ P[i] ≤ N

Solution:

First, precompute the total time totalTime = Σ T[i] for all problems. For each query i, the answer is simply totalTime - T[P[i]] + X[i], since we replace the original time for problem P[i] with the new time X[i].

Time complexity: O(N + M).

int main() {
    int numProblems;
    std::cin >> numProblems;
    
    std::vector<long long=""> solveTime(numProblems + 1);
    long long totalTime = 0;
    
    for (int i = 1; i <= numProblems; i++) {
        std::cin >> solveTime[i];
        totalTime += solveTime[i];
    }
    
    int numQueries;
    std::cin >> numQueries;
    
    for (int q = 0; q < numQueries; q++) {
        int problemIdx, newTime;
        std::cin >> problemIdx >> newTime;
        std::cout << totalTime - solveTime[problemIdx] + newTime << "\n";
    }
    
    return 0;
}
</long>

Problem C: Recovering Line Arrangement

Problem Statement:

N people stood in a line yesterday, but today they forgot their positions. Each person i remembers only one piece of information: the absolute difference between the number of people on their left and the number of people on they right, denoted as A[i].

Determine the number of possible valid arrangements from yesterday. Output the result modulo 10^9 + 7. If the information is inconsistent (no valid arrangement exists), output 0.

Constraints: 1 ≤ N ≤ 10^5, 0 ≤ A[i] ≤ N - 1

Solution:

Let pos[i] denote the position of person i yesterday. Define left[i] as the number of people to the left of person i, and right[i] as the number to their right. We have:

left[i] + right[i] = N - 1
|left[i] - right[i]| = A[i]

Solving these equations yields two possible positions for each person (or one position if they coincide):

pos[i] can be (N - 1 + A[i]) / 2 + 1 or (N - 1 - A[i]) / 2 + 1

For a valid arrangement, the parity condition (N - 1 + A[i]) % 2 == 0 must hold. We count how many people can occupy each position:

• If N is even: each position must have exactly 2 candidates.
• If N is odd: exactly one position has 1 candidate (the center), and all other positions have 2 candidates.

For each valid pair of people who can occupy the same position, they can be arranged in 2 ways. Thus, the answer is 2^(N/2) if valid.

Time complexity: O(N).

const int MOD = 1e9 + 7;

int main() {
    int N;
    std::cin >> N;
    
    std::vector<int> A(N);
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
    }
    
    std::vector<int> positionCount(N, 0);
    bool valid = true;
    
    for (int i = 0; i < N && valid; i++) {
        if ((N - 1 + A[i]) % 2 != 0) {
            valid = false;
            break;
        }
        
        int pos1 = (N - 1 - A[i]) / 2;
        int pos2 = (N - 1 + A[i]) / 2;
        
        positionCount[pos1]++;
        if (pos1 != pos2) {
            positionCount[pos2]++;
        }
    }
    
    if (N % 2 == 0) {
        for (int i = 0; i < N; i++) {
            if (positionCount[i] != 2) valid = false;
        }
    } else {
        int ones = 0, twos = 0;
        for (int i = 0; i < N; i++) {
            if (positionCount[i] == 1) ones++;
            else if (positionCount[i] == 2) twos++;
            else valid = false;
        }
        if (ones != 1 || twos != N - 1) valid = false;
    }
    
    if (!valid) {
        std::cout << 0 << "\n";
    } else {
        long long result = 1;
        int pairs = N / 2;
        while (pairs--) {
            result = (result * 2) % MOD;
        }
        std::cout << result << "\n";
    }
    
    return 0;
}
</int></int>

Problem D: XOR and Sum Pairs

Problem Statement:

Given a positive integer N, count the number of pairs (u, v) where 0 ≤ u, v ≤ N such that there exist non-negative integers a, b satisfying:

a XOR b = u
a + b = v

Output the result modulo 10^9 + 7.

Constraints: 1 ≤ N ≤ 10^18

Solution:

Since XOR represents addition with out carry in binary, we always have u ≤ v. The problem asks us to count pairs (u, v) by iterating over v and counting valid u values.

We use memoization to compute f(v), which represents the number of valid u values for a given v. The key insight is the transition relation:

f(v) = f(v/2) + f((v-1)/2) + f((v-2)/2)

This corresponds to the three possible carry scenarios when adding two bits. We use a hashmap for memoization to handle the large constraint efficiently.

Time complexity: O(log N) states, each computed in constant time.

const long long MOD = 1e9 + 7;

std::unordered_map<long long=""> memo;

long long solve(long long v) {
    if (v == 0) return 1;
    if (memo.count(v)) return memo[v];
    
    long long result = 0;
    result = (result + solve(v / 2)) % MOD;
    result = (result + solve((v - 1) / 2)) % MOD;
    result = (result + solve((v - 2) / 2)) % MOD;
    
    return memo[v] = result;
}

int main() {
    long long N;
    std::cin >> N;
    std::cout << solve(N) << "\n";
    return 0;
}
</long>