Scholarship Allocation

A school distributes scholarships after each semester's final exams. There are five scholarship types available:

1. Academician Scholarship: 8000 yuan for students with final exam scores > 80 and atleast one published paper
2. May Fourth Scholarship: 4000 yuan for students with final exam scores > 85 and peer evaluation scores > 80
3. Excellence Award: 2000 yuan for students with final exam scores > 90
4. Western Region Scholarship: 1000 yuan for western region stuednts with final exam scores > 85
5. Contribution Award: 850 yuan for student leaders with peer evaluation scores > 80

Students can receive multiple scholarships simultaneously. Given student data, determine who receives the highest total amount.

Input/Output Format

Input begins with integer N (1 ≤ N ≤ 100) representing student count. Each of the next N lines contains: name, final score, peer score, leadership status (Y/N), western region status (Y/N), and paper count.

Output three lines: top earner's name, their total amount, and sum of all scholarships awarded.

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

struct Student {
    string name;
    int finalScore, peerScore, papers;
    char isLeader, isWestern;
    int totalAward;
    int index;
};

bool compare(Student a, Student b) {
    if (a.totalAward != b.totalAward)
        return a.totalAward > b.totalAward;
    return a.index < b.index;
}

int main() {
    int n;
    cin >> n;
    Student students[100];
    
    int totalAllAwards = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> students[i].name >> students[i].finalScore >> students[i].peerScore >> 
               students[i].isLeader >> students[i].isWestern >> students[i].papers;
        
        students[i].totalAward = 0;
        
        // Academician Scholarship
        if (students[i].finalScore > 80 && students[i].papers >= 1)
            students[i].totalAward += 8000;
        
        // May Fourth Scholarship
        if (students[i].finalScore > 85 && students[i].peerScore > 80)
            students[i].totalAward += 4000;
        
        // Excellence Award
        if (students[i].finalScore > 90)
            students[i].totalAward += 2000;
        
        // Western Region Scholarship
        if (students[i].finalScore > 85 && students[i].isWestern == 'Y')
            students[i].totalAward += 1000;
        
        // Contribution Award
        if (students[i].peerScore > 80 && students[i].isLeader == 'Y')
            students[i].totalAward += 850;
        
        totalAllAwards += students[i].totalAward;
        students[i].index = i;
    }
    
    sort(students, students + n, compare);
    
    cout << students[0].name << endl;
    cout << students[0].totalAward << endl;
    cout << totalAllAwards << endl;
    
    return 0;
}

River Crossing

A frog wants to cross a bridge of length L by jumping distances between S and T. Some positions have stones that the frog dislikes stepping on. Determine the minimum number of stones the frog must step on to cross the bridge.

Input/Output Format

First line: bridge length L (1 ≤ L ≤ 10^9). Second line: S, T, M representing min jump, max jump, and stone count. Third line: M distinct positions of stones.

Output the minimum number of stones stepped on.

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

const int MAX_STONES = 105;
const int MOD = 105;

int dp[MOD];
int stones[MAX_STONES];

int main() {
    int L, S, T, M;
    cin >> L >> S >> T >> M;
    
    for (int i = 0; i < M; i++)
        cin >> stones[i];
    
    sort(stones, stones + M);
    
    // Special case when jump distance is fixed
    if (S == T) {
        int result = 0;
        for (int i = 0; i < M; i++)
            if (stones[i] % S == 0)
                result++;
        cout << result << endl;
        return 0;
    }
    
    // Initialize DP array
    for (int i = 0; i < MOD; i++)
        dp[i] = INT_MAX;
    dp[0] = 0;
    
    int stoneIndex = 0;
    int consecutiveCount = 0;
    int lastValue = 0;
    
    for (int pos = 1; pos <= L + T; pos++) {
        int currentMod = pos % MOD;
        dp[currentMod] = INT_MAX;
        
        // Check all possible previous positions
        for (int jump = S; jump <= T; jump++) {
            int prevPos = pos - jump;
            if (prevPos >= 0) {
                int prevMod = prevPos % MOD;
                dp[currentMod] = min(dp[currentMod], dp[prevMod]);
            }
        }
        
        // Add stone penalty if current position has stone
        if (stoneIndex < M && stones[stoneIndex] == pos) {
            dp[currentMod]++;
            stoneIndex++;
        }
        
        // Optimization: detect repeating patterns
        if (dp[currentMod] == lastValue)
            consecutiveCount++;
        else {
            lastValue = dp[currentMod];
            consecutiveCount = 1;
        }
        
        if (consecutiveCount >= T) {
            if (stoneIndex >= M) {
                cout << dp[currentMod] << endl;
                return 0;
            } else {
                pos = stones[stoneIndex] - 1;
            }
        }
    }
    
    int result = INT_MAX;
    for (int i = 0; i < MOD; i++)
        result = min(result, dp[i]);
    
    cout << result << endl;
    return 0;
}

Equivalent Expressions

Given an algebraic expression and multiple options, determine which options are equivalent to the given expression. Expressions may contain variable 'a', integers, operators (+,-,*,^), and parentheses.

Input/Output Format

First line: main expression. Second line: N (2 ≤ N ≤ 26) option count. Next N lines: option expressions labeled A-Z.

Output letters of equivalent expressions in alphabetical order without spaces.

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

typedef long long ll;
const ll MOD = 1000000007;
const int TEST_VALUES = 13;

ll power(ll base, ll exp) {
    ll result = 1;
    for (int i = 0; i < exp; i++) {
        result = (result * base) % MOD;
    }
    return result;
}

ll evaluate(const string& expr, ll value) {
    stack<ll> values;
    stack<char> ops;
    
    for (int i = 0; i < expr.length(); i++) {
        if (expr[i] == ' ') continue;
        
        if (isdigit(expr[i])) {
            ll num = 0;
            while (i < expr.length() && isdigit(expr[i])) {
                num = (num * 10 + (expr[i] - '0')) % MOD;
                i++;
            }
            i--;
            values.push(num);
        }
        else if (expr[i] == 'a') {
            values.push(value);
        }
        else if (expr[i] == '(') {
            ops.push(expr[i]);
        }
        else if (expr[i] == ')') {
            while (!ops.empty() && ops.top() != '(') {
                ll b = values.top(); values.pop();
                ll a = values.top(); values.pop();
                char op = ops.top(); ops.pop();
                
                if (op == '+') values.push((a + b) % MOD);
                else if (op == '-') values.push((a - b + MOD) % MOD);
                else if (op == '*') values.push((a * b) % MOD);
                else if (op == '^') values.push(power(a, b));
            }
            ops.pop(); // Remove '('
        }
        else {
            while (!ops.empty() && ops.top() != '(') {
                if ((expr[i] == '+' || expr[i] == '-') && (ops.top() == '*' || ops.top() == '^')) {
                    ll b = values.top(); values.pop();
                    ll a = values.top(); values.pop();
                    char op = ops.top(); ops.pop();
                    
                    if (op == '*') values.push((a * b) % MOD);
                    else if (op == '^') values.push(power(a, b));
                } else break;
            }
            ops.push(expr[i]);
        }
    }
    
    while (!ops.empty()) {
        ll b = values.top(); values.pop();
        ll a = values.top(); values.pop();
        char op = ops.top(); ops.pop();
        
        if (op == '+') values.push((a + b) % MOD);
        else if (op == '-') values.push((a - b + MOD) % MOD);
        else if (op == '*') values.push((a * b) % MOD);
        else if (op == '^') values.push(power(a, b));
    }
    
    return values.top();
}

int main() {
    string mainExpr;
    getline(cin, mainExpr);
    
    int n;
    cin >> n;
    cin.ignore();
    
    ll testValues[TEST_VALUES];
    ll mainResults[TEST_VALUES];
    
    // Generate test values
    for (int i = 0; i < TEST_VALUES; i++)
        testValues[i] = i - 6;
    
    // Evaluate main expression
    for (int i = 0; i < TEST_VALUES; i++)
        mainResults[i] = evaluate(mainExpr, testValues[i]);
    
    // Check each option
    for (int i = 0; i < n; i++) {
        string option;
        getline(cin, option);
        
        bool equivalent = true;
        for (int j = 0; j < TEST_VALUES; j++) {
            if (evaluate(option, testValues[j]) != mainResults[j]) {
                equivalent = false;
                break;
            }
        }
        
        if (equivalent)
            cout << char('A' + i);
    }
    
    cout << endl;
    return 0;
}

Bonfire Party

N students sit in a circle numbered 1 to N. Each student has two preferred neighbors. Commands can reorder students in form (b1, b2, ..., bm) where bi moves to bi+1's position and bm moves to b1's position. Cost equals m. Find minimum cost to satisfy all preferences.

Input/Output Format

First line: N (3 ≤ N ≤ 50000). Next N lines: for student i, two preferred neighbors.

Output minimum total cost, or -1 if impossible.

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

const int MAXN = 50005;

int n;
int head[MAXN], nextNode[MAXN], prevNode[MAXN];
int sequence[MAXN];
int positionCount1[MAXN], positionCount2[MAXN];

struct Edge {
    int to, next;
} edges[MAXN * 4];

int edgeCount = 0;

void addEdge(int from, int to) {
    edges[edgeCount] = {to, head[from]};
    head[from] = edgeCount++;
    
    edges[edgeCount] = {from, head[to]};
    head[to] = edgeCount++;
}

bool buildSequence() {
    int current = 0;
    nextNode[current] = edges[0].to;
    prevNode[edges[0].to] = current;
    current = edges[0].to;
    
    while (true) {
        int nextStudent = -1;
        bool found = false;
        bool multipleOptions = false;
        
        for (int i = head[current]; i != -1; i = edges[i].next) {
            int neighbor = edges[i].to;
            if (nextNode[neighbor] == current || prevNode[neighbor] == current)
                continue;
            
            if (prevNode[neighbor] == -1) {
                if (nextNode[current] == -1) {
                    prevNode[neighbor] = current;
                    nextNode[current] = neighbor;
                    nextStudent = neighbor;
                    found = true;
                } else {
                    multipleOptions = true;
                    break;
                }
            } else {
                multipleOptions = true;
                break;
            }
        }
        
        if (!found) break;
        if (multipleOptions) return false;
        current = nextStudent;
    }
    
    current = 0;
    int count = 1;
    while (true) {
        sequence[count++] = current;
        current = nextNode[current];
        if (current == 0) break;
    }
    
    return true;
}

int main() {
    memset(nextNode, -1, sizeof(nextNode));
    memset(prevNode, -1, sizeof(prevNode));
    memset(head, -1, sizeof(head));
    
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        addEdge(i, a - 1);
        addEdge(b - 1, i);
    }
    
    if (!buildSequence()) {
        cout << "-1" << endl;
        return 0;
    }
    
    int maxMatch = 0;
    
    for (int i = 1; i <= n; i++) {
        int diff1 = (sequence[i] - i + n) % n;
        positionCount1[diff1]++;
        maxMatch = max(maxMatch, positionCount1[diff1]);
        
        int diff2 = (sequence[n - i + 1] - i + n) % n;
        positionCount2[diff2]++;
        maxMatch = max(maxMatch, positionCount2[diff2]);
    }
    
    cout << n - maxMatch << endl;
    return 0;
}