T1 - Reading Plan

Problem: A book has (n) pages. On the first day, a person reads (x) pages. Each subsequent day, they read (y) pages more than the previous day. How many days are needed to finish the book?

Input: Three integers (n), (x), (y) ((20 \le n \le 5000, 1 \le x, y \le 20)) separated by spaces. Output: A single integer representing the number of days.

Sample Enput: 100 10 5 Sample Output: 5

Approach: A straightforward simulation using a while loop. Initialize a counter for days and a variable for the current day's reading target. Encrement the target by (y) each day and subtract from (n) until (n \le 0).

T2 - Digit Swap

Problem: Given a positive integer (n), swap its most significant digit (MSD) and least significant digit (LSD). Remove any leading zeros from the result before output.

Input: A single integer (n) ((100 \le n \le 10^9)). Output: The resulting integer after the swap.

Sample Input: 173 Sample Output: 371

Approach: Read the input as a string. Use std::swap to exchange the first and last characters. Then, find the first non-zero character's index and output the substring starting from that index using substr().

T3 - Number Appearing Odd Times

Problem: Given (n) integers, exactly one number appears an odd number of times. Find this number.

Input:

• First line: an integer (n) ((1 \le n \le 10^5)).
• Second line: (n) integres ((1 \le \text{each integer} \le 10^9)) separated by spaces. Output: The integer that appears an odd number of times.

Sample Input:

7
6 2 4 6 4 2 6

Sample Output: 6

Approach: Utilize the XOR bitwise operation's property: (a \oplus a = 0) and (a \oplus 0 = a). XOR-ing all numbers together cancels out those appearing an even number of times, leaving the one appearing an odd number of times.

Code Example:

#include <iostream>
int main() {
    int count, value, result = 0;
    std::cin >> count;
    for (int i = 0; i < count; ++i) {
        std::cin >> value;
        result ^= value;
    }
    std::cout << result << std::endl;
    return 0;
}

T4 - Letter Shifting

Problem: Givan a lowercase string (s) of length (n) and a sequence of (n) positive integers (a_1, a_2, ..., a_n), perform (n) operations. For the (i)-th operation:

• Shift the first (i) characters of the current string.
• The direction is left if (i) is odd, right if (i) is even.
• The shift amount is (a_i) positions within the alphabet, wrapping around ('a' left of 'z', 'z' right of 'a'). Output the final string.

Input:

• First line: integer (n).
• Second line: string (s).
• Third line: (n) integers (a_1 ... a_n). Output: The final string after all operations.

Sample Input:

5
abcde
1 3 5 7 9

Sample Output: vxvbv

Approach: Direct simulation for each prefix is (O(n^2)) and may time out. Optimize by claculating the net shift for each character. Character (s[j]) (0-indexed) is affected by operations from index (j) to (n-1). Its net shift is the alternating sum (\sum_{k=j}^{n-1} (-1)^{k+1} * a_{k+1}) (where sign depends on operation index parity). Compute this efficiently using a running total from the end. Apply the net shift modulo 26 to each character.

Key Implementation Detail: Handle negative shifts by adding 26. Use int for shift calculations.

T5 - Minimum Initial Energy for Game Tasks

Problem: There are (n) tasks. Each task has an activation energy (start_i) and a completion cost (cost_i) ((cost_i \le start_i)). A task can only be started if the player's current energy is at least (start_i). Upon completion, energy decreases by (cost_i). Tasks can be completed in any order. Find the minimum initial energy required to complete all tasks.

Input:

• First line: integer (n).
• Next (n) lines: two integers (start_i) and (cost_i) per line. Output: The minimum initial energy.

Sample Input:

3
2 2
9 5
7 4

Sample Output: 12

Approach: Combine binary search on the answer with a greedy validation.

1. Greedy Ordering: Sort tasks by ((start_i - cost_i)) in descending order. This prioritizes tasks that yield higher net energy gain (or lower net loss) relative to their activation threshold.
2. Validation Function check(initial_energy): Simulate processing tasks in the sorted order. If current_energy < start_i, return false. Otherwise, current_energy -= cost_i. If all tasks can be completed, return true.
3. Binary Search: Search for the minimum initial_energy between a lower bound (e.g., 1) and an upper bound (e.g., sum of all start_i).

T6 - Item Grouping (Series Segmentation)

Problem: Given a sequence (A) of (N) positive integers, partition it into (M) ((M \le N)) contiguous segments. Minimize the maximum sum of any segment.

Input:

• First line: (N) and (M).
• Second line: (N) integers (A_1 ... A_N). Output: The minimized maximum segment sum.

Sample Input:

5 2
6 1 3 8 4

Sample Output: 12

Approach: Binary search on the answer max_sum.

• Lower Bound (low): The maximum single element in (A) (a segment must contain at least one element).
• Upper Bound (high): The sum of all elements in (A) (one segment).
• Validation Function check(max_sum): Greedily form segments. Iterate through (A), adding elements to the current segment while its sum does not exceed max_sum. If adding the next element would exceed max_sum, start a new segment. Count the number of segments formed. Return true if the count is (\le M), else false.
• The smallest max_sum for which check returns true is the answer.

Code Example:

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

int seq_len, num_segments;
int sequence[100005];

bool can_partition(int limit) {
    int segments_used = 1, current_sum = 0;
    for (int i = 0; i < seq_len; ++i) {
        if (current_sum + sequence[i] <= limit) {
            current_sum += sequence[i];
        } else {
            current_sum = sequence[i];
            ++segments_used;
        }
    }
    return segments_used <= num_segments;
}

int main() {
    cin >> seq_len >> num_segments;
    int low = 0, high = 0;
    for (int i = 0; i < seq_len; ++i) {
        cin >> sequence[i];
        high += sequence[i];
        if (sequence[i] > low) low = sequence[i];
    }
    int answer = high;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (can_partition(mid)) {
            answer = mid;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    cout << answer << endl;
    return 0;
}