Problem Solutions

Problem 1: Commute Calculation

#include <iostream>
using namespace std;

int main() {
    int base, bonus1, bonus2;
    cin >> base >> bonus1 >> bonus2;
    cout << base + min(bonus1, bonus2) << endl;
    return 0;
}

Problem 2: Adoration Count

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

int main() {
    int n, low, high;
    scanf("%d%d%d", &n, &low, &high);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        int val;
        scanf("%d", &val);
        if (val > high) cnt += 3;
    }
    printf("%d\n", cnt);
    return 0;
}

Problem 3: Square Bean Patterns

Tags: Recursion, String Manipulation

Approach

Construct patterns through recursive grid expansion. Time complexity: (O(4^n)).

n = int(input())
pattern = ['******', '******', '******', '***...', '***...', '***...']
inverted = ['......', '......', '......', '...***', '...***', '...***']

for _ in range(n-1):
    size = len(pattern)
    new_pat = [''] * (2 * size)
    new_inv = [''] * (2 * size)
    
    for i in range(size):
        new_pat[i] = inverted[i] + inverted[i]
        new_pat[i+size] = inverted[i] + pattern[i]
    for i in range(size):
        new_inv[i] = pattern[i] + pattern[i]
        new_inv[i+size] = pattern[i] + inverted[i]
    
    pattern, inverted = new_pat, new_inv

for line in pattern:
    print(line)

Problem 4: Matrix Traversal Optimization

Tags: BFS, Priority Queue

Approach 1

Use priority-queue BFS to handle variable move costs. Time complexity: (O(n^2 \log n)).

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Cell {
    int row, col, cost;
    bool operator>(const Cell& other) const {
        return cost > other.cost;
    }
};

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};

int main() {
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<char>> grid(rows+1, vector<char>(cols+1));
    vector<vector<bool>> visited(rows+1, vector<bool>(cols+1, false));
    
    for (int i = 1; i <= rows; i++)
        for (int j = 1; j <= cols; j++)
            cin >> grid[i][j];
    
    priority_queue<Cell, vector<Cell>, greater<Cell>> pq;
    pq.push({1, 1, 0});
    visited[1][1] = true;
    
    while (!pq.empty()) {
        Cell cur = pq.top(); pq.pop();
        if (cur.row == rows && cur.col == cols) {
            cout << cur.cost << endl;
            return 0;
        }
        for (int d = 0; d < 4; d++) {
            int nr = cur.row + dx[d], nc = cur.col + dy[d];
            if (nr < 1 || nc < 1 || nr > rows || nc > cols || visited[nr][nc]) continue;
            visited[nr][nc] = true;
            
            if (grid[cur.row][cur.col] != grid[nr][nc]) {
                pq.push({nr, nc, cur.cost + 1});
            } else {
                grid[nr][nc] = (grid[cur.row][cur.col] == '0') ? '1' : '0';
                pq.push({nr, nc, cur.cost + 2});
            }
        }
    }
    return 0;
}

Alternative Approach: Model as graph with edge weights 1 or 2 and run Dijkstra.

Problem 5: Counting Special Sequences

Tags: Dynamic Programming, Prefix Sums

Approach

Let (dp[i][j]) count sequences of length (i) with sum (i \times j). Transition: [dp[i][j] = \sum_{l=l_{\min}}^{l_{\max}} dp[i-1][l]] where (l) bounds are derived from (a_i) constraints. Use prefix sums for efficient range queries.

Note: Handle index bounds carefully to avoid overflow.

#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1e9+7;

int main() {
    int len, max_val;
    cin >> len >> max_val;
    vector<vector<int>> dp(len+1, vector<int>(max_val+1, 0));
    vector<int> prefix(max_val+1, 0);
    
    for (int j = 1; j <= max_val; j++) {
        dp[1][j] = 1;
        prefix[j] = (prefix[j-1] + 1) % MOD;
    }
    
    for (int i = 2; i <= len; i++) {
        vector<int> new_dp(max_val+1, 0);
        for (int j = 1; j <= max_val; j++) {
            int low_bound = max(1, (i*j - max_val + i - 2) / (i-1));
            int high_bound = min(max_val, (i*j - 1) / (i-1));
            if (low_bound <= high_bound) {
                new_dp[j] = (prefix[high_bound] - prefix[low_bound-1] + MOD) % MOD;
            }
        }
        dp[i] = new_dp;
        prefix[0] = 0;
        for (int j = 1; j <= max_val; j++)
            prefix[j] = (prefix[j-1] + dp[i][j]) % MOD;
    }
    
    int total = 0;
    for (int j = 1; j <= max_val; j++)
        total = (total + dp[len][j]) % MOD;
    cout << total << endl;
}

Problem 6: Card Game Simulation

Tags: Probability, Recursion

Approach

Recursively compute win probabilities by enumerating all card swaps. Time complexity: (O(27n)).

MOD = 10**9+7

def is_winning(hand):
    return sorted(hand) == ['i','n','w']

def simulate(handA, handB, handC, turns, max_turns):
    if is_winning(handA): return 1
    if is_winning(handB) or is_winning(handC): return 0
    if turns == max_turns: return 0
    
    prob = 0
    if len(set(handA)) == 1 or len(set(handA)) == 3:
        swap_options = [0,1,2]
        denom = pow(27, MOD-2, MOD)
    else:
        dup_index = 0 if handA[0]==handA[1] else (0 if handA[0]==handA[2] else 1)
        swap_options = [dup_index, 2-dup_index]  # indices of duplicates
        denom = pow(18, MOD-2, MOD)
    
    for i in swap_options:
        for j in range(3):
            for k in renge(3):
                newA = handA.copy()
                newB = handB.copy()
                newC = handC.copy()
                newA[i], newB[j], newC[k] = newC[k], newA[i], newB[j]
                prob = (prob + simulate(newA, newB, newC, turns+1, max_turns) * denom) % MOD
    return prob

n_turns = int(input())
handA = sorted(list(input().strip()))
handB = sorted(list(input().strip()))
handC = sorted(list(input().strip()))
print(simulate(handA, handB, handC, 0, n_turns))