Division Problem

Approach

This problem requires careful attention to output format. The last line with 0 should not output extra spaces. It's recommended to use a flag at the beginning to control newline output.

Since digits range from 0 to 9, one might consider permutations, but generating all permutations for each n would be too slow at O(10!) complexity. We can preprocess all permutaitons of 0-9 digits and check relationships between the first 5 digits and last 5 digits with respect to y.

A more optimized approach: since x/y = n where 2 ≤ n ≤ 79 and x is a fixed 5-digit number, we can directly enumerate from 10234 to 98765, divide by n to get y, then verify if x and y satisfy the permutation condition.

Preprocessing with Permutations

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

struct Solution {
    int numerator, denominator;
};

vector<Solution> results[80];
int solution_count[80] = {0};

int main() {
    int digits[] = {0,1,2,3,4,5,6,7,8,9};
    
    do {
        int num = 0, den = 0;
        for (int i = 0; i < 5; i++) {
            num = num * 10 + digits[i];
            den = den * 10 + digits[i+5];
        }
        
        if (num % den == 0 && num / den <= 79) {
            int ratio = num / den;
            results[ratio].push_back({num, den});
            solution_count[ratio]++;
        }
    } while (next_permutation(digits, digits+10));
    
    int n, first_case = 0;
    while (scanf("%d", &n) && n != 0) {
        if (first_case) printf("\n");
        first_case = 1;
        
        if (solution_count[n] == 0) {
            printf("There are no solutions for %d.\n", n);
        } else {
            for (auto sol : results[n]) {
                printf("%05d / %05d = %d\n", sol.numerator, sol.denominator, n);
            }
        }
    }
    return 0;
}

Optimized Enumeration

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

int main() {
    int n, first_output = 0;
    while (scanf("%d", &n) && n != 0) {
        if (first_output) printf("\n");
        first_output = 1;
        
        int count = 0;
        for (int num = 10234; num <= 98765; num++) {
            if (num % n == 0) {
                int den = num / n;
                if (den < 1000 || den > 99999) continue;
                
                int digit_count[10] = {0};
                for (int base = 1; base <= 10000; base *= 10) {
                    digit_count[num / base % 10]++;
                    digit_count[den / base % 10]++;
                }
                
                bool valid = true;
                for (int i = 0; i <= 9; i++) {
                    if (digit_count[i] == 0) {
                        valid = false;
                        break;
                    }
                }
                
                if (valid) {
                    count++;
                    printf("%05d / %05d = %d\n", num, den, n);
                }
            }
        }
        
        if (count == 0) {
            printf("There are no solutions for %d.\n", n);
        }
    }
    return 0;
}

Maximum Product Problem

Approach

Enumerate all possible subarray ranges, calculate the product for each subarray, and track the maximum value. Note that the answer may exceed int range, requiring long long.

Implementation

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

int main() {
    int n, case_num = 0;
    while (cin >> n) {
        vector<long long> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        
        long long max_product = 0;
        for (int start = 0; start < n; start++) {
            for (int end = start; end < n; end++) {
                long long product = 1;
                for (int k = start; k <= end; k++) {
                    product *= arr[k];
                }
                max_product = max(max_product, product);
            }
        }
        
        cout << "Case #" << ++case_num << ": The maximum product is " << max_product << ".\n\n";
    }
    return 0;
}

Fraction Decomposition

Approach

Given that x and y are positive integers with x ≥ y, we have 1/x ≤ 1/y. From the equation 1/k = 1/x + 1/y, we can derive x = ky/(y-k). Since x must be positive, y > k. Also, from 1/k - 1/y ≤ 1/y, we get y ≤ 2k. Therefore, we can enumerate y from k+1 to 2k, calculate x, and record valid solutions.

Implementation

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

int main() {
    int k;
    while (cin >> k) {
        vector<pair<int, int>> solutions;
        
        for (int den = k + 1; den <= 2 * k; den++) {
            if (k * den % (den - k) == 0) {
                int num = k * den / (den - k);
                solutions.push_back({num, den});
            }
        }
        
        cout << solutions.size() << '\n';
        for (auto sol : solutions) {
            cout << "1/" << k << " = 1/" << sol.first << " + 1/" << sol.second << '\n';
        }
    }
    return 0;
}

Abacus Mental Calculation Test

Approach

We need to find numbers in set A that equal the sum of two distinct numbers from the same set. Since the data size is small, we can use triple loops to enumerate all combinations. Note that multiple pairs summing to the same number count only once, so we use a marker array to track which sums have been found.

Implementation

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

int main() {
    int n;
    cin >> n;
    vector<int> numbers(n);
    vector<bool> valid_sum(20010, false);
    
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (numbers[i] != numbers[j] && numbers[i] + numbers[j] == numbers[k]) {
                    valid_sum[numbers[k]] = true;
                }
            }
        }
    }
    
    int count = 0;
    for (bool found : valid_sum) {
        if (found) count++;
    }
    cout << count << '\n';
    
    return 0;
}

Array Pair Sum

Approach

The problem requires calculating the sum of all a_i × a_j where i < j. A naive double loop would be O(n²), which is too slow for n up to 2×10⁵. We can optimize using prefix sums: calculate the total sum first, then for each element, multiply it by the sum of all subsequent elements.

Implementation

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

int main() {
    int n;
    cin >> n;
    vector<long long> arr(n);
    long long total_sum = 0;
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        total_sum += arr[i];
    }
    
    long long result = 0;
    for (int i = 0; i < n; i++) {
        total_sum -= arr[i];
        result += total_sum * arr[i];
    }
    
    cout << result << '\n';
    return 0;
}

Triple Combination Problem

Approach

We need to find three distinct 3-digit numbers using digits 1-9 exactly once that satisfy given ratios. We can generate all permutations of digits 1-9 and check if the first three digits, next three digits, and last three digits satisfy the ratio conditions.

Implementation with Permutations

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

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    
    int digits[] = {1,2,3,4,5,6,7,8,9};
    bool found = false;
    
    do {
        int x = 0, y = 0, z = 0;
        for (int i = 0; i < 3; i++) {
            x = x * 10 + digits[i];
            y = y * 10 + digits[i+3];
            z = z * 10 + digits[i+6];
        }
        
        if (b * x == a * y && c * y == b * z) {
            cout << x << ' ' << y << ' ' << z << '\n';
            found = true;
        }
    } while (next_permutation(digits, digits+9));
    
    if (!found) {
        cout << "No!!!\n";
    }
    
    return 0;
}

Score Ranking System

Approach

This problem requires custom sorting with multiple criteria. After sorting by the specified rules, we need to assign ranks and then restore the original order to output each student's rank.

Implementation

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

struct Student {
    int chinese, math, english;
    int original_index, final_rank;
};

bool compare_ranking(const Student& s1, const Student& s2) {
    int total1 = s1.chinese + s1.math + s1.english;
    int total2 = s2.chinese + s2.math + s2.english;
    if (total1 != total2) return total1 > total2;
    
    int cm1 = s1.chinese + s1.math;
    int cm2 = s2.chinese + s2.math;
    if (cm1 != cm2) return cm1 > cm2;
    
    int max_cm1 = max(s1.chinese, s1.math);
    int max_cm2 = max(s2.chinese, s2.math);
    if (max_cm1 != max_cm2) return max_cm1 > max_cm2;
    
    return true;
}

bool restore_order(const Student& s1, const Student& s2) {
    return s1.original_index < s2.original_index;
}

int main() {
    int n;
    cin >> n;
    vector<Student> students(n);
    
    for (int i = 0; i < n; i++) {
        cin >> students[i].chinese >> students[i].math >> students[i].english;
        students[i].original_index = i;
    }
    
    sort(students.begin(), students.end(), compare_ranking);
    
    students[0].final_rank = 1;
    for (int i = 1; i < n; i++) {
        students[i].final_rank = i + 1;
        Student& curr = students[i];
        Student& prev = students[i-1];
        
        if (curr.chinese + curr.math + curr.english == prev.chinese + prev.math + prev.english) {
            if (curr.chinese + curr.math == prev.chinese + prev.math) {
                if (max(curr.chinese, curr.math) == max(prev.chinese, prev.math)) {
                    curr.final_rank = prev.final_rank;
                }
            }
        }
    }
    
    sort(students.begin(), students.end(), restore_order);
    
    for (const auto& student : students) {
        cout << student.final_rank << '\n';
    }
    
    return 0;
}

Sorting Template

Implementation

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

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    sort(arr.begin(), arr.end());
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
    cout << '\n';
    
    return 0;
}

Bookshelf Problem

Approach

We need the minimum number of cows to reach a target height. This is a classic greedy problem: sort heights in descending order and accumulate until we reach or exceed the target height.

Implementation

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

int main() {
    int n, target_height;
    cin >> n >> target_height;
    vector<int> heights(n);
    
    for (int i = 0; i < n; i++) {
        cin >> heights[i];
    }
    
    sort(heights.rbegin(), heights.rend());
    
    int current_height = 0;
    for (int i = 0; i < n; i++) {
        current_height += heights[i];
        if (current_height >= target_height) {
            cout << i + 1 << '\n';
            return 0;
        }
    }
    
    return 0;
}

Apple Picking Problem

Approach

We need to maximize the number of apples picked within given strength constraints. Only apples within reach (height ≤ a + b) are considered. We sort apples by effort required and pick the easiest ones first until strength is exhausted.

Implementation

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

int main() {
    int n, strength, reach_a, reach_b;
    cin >> n >> strength >> reach_a >> reach_b;
    
    vector<int> efforts;
    for (int i = 0; i < n; i++) {
        int height, effort;
        cin >> height >> effort;
        if (height <= reach_a + reach_b) {
            efforts.push_back(effort);
        }
    }
    
    sort(efforts.begin(), efforts.end());
    
    int count = 0;
    for (int effort : efforts) {
        if (strength >= effort) {
            strength -= effort;
            count++;
        } else {
            break;
        }
    }
    
    cout << count << '\n';
    return 0;
}

Water Fetching Queue

Approach

To minimize average waiting time, people with shorter fetching times should go first. This ensures that subsequent people wait less. The solution involves sorting by fetching time and calculating cumulative waiting times.

Implementation

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

struct Person {
    int time, id;
};

bool compare_time(const Person& p1, const Person& p2) {
    return p1.time < p2.time;
}

int main() {
    int n;
    cin >> n;
    vector<Person> people(n);
    
    for (int i = 0; i < n; i++) {
        cin >> people[i].time;
        people[i].id = i + 1;
    }
    
    sort(people.begin(), people.end(), compare_time);
    
    double total_wait = 0, current_time = 0;
    for (const auto& person : people) {
        cout << person.id << ' ';
        total_wait += current_time;
        current_time += person.time;
    }
    
    double average_wait = total_wait / n;
    cout << '\n' << fixed << setprecision(2) << average_wait << '\n';
    
    return 0;
}