Prime Product Finder

Determine three distinct prime numbers between 1 and 100 whose product lies within a given range [l, r]. If no valid triplet exists, output -1.

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

bool check_prime(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; ++i) {
        if (num % i == 0) return false;
    }
    return true;
}

int main() {
    int lower_bound, upper_bound;
    cin >> lower_bound >> upper_bound;
    vector<int> prime_list;
    for (int candidate = 2; candidate <= 100; ++candidate) {
        if (check_prime(candidate)) prime_list.push_back(candidate);
    }
    for (int i = 0; i < prime_list.size(); ++i) {
        for (int j = i + 1; j < prime_list.size(); ++j) {
            for (int k = j + 1; k < prime_list.size(); ++k) {
                long long product = static_cast<long long>(prime_list[i]) * prime_list[j] * prime_list[k];
                if (product >= lower_bound && product <= upper_bound) {
                    cout << product << '\n';
                    return 0;
                }
            }
        }
    }
    cout << "-1\n";
    return 0;
}

Closest Element Adjustment

Sort one array and find the closest value for each element in the second array using binary search. Swap elements within the sorted array to minimize absolute differences.

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

int main() {
    int size;
    cin >> size;
    vector<int> array1(size), array2(size);
    for (int i = 0; i < size; ++i) cin >> array1[i];
    for (int i = 0; i < size; ++i) cin >> array2[i];
    sort(array1.begin(), array1.end());
    int min_diff = INT_MAX;
    int swap_pos1 = -1, swap_pos2 = -1;
    for (int i = 0; i < size; ++i) {
        auto it = lower_bound(array1.begin(), array1.end(), array2[i]);
        int diff1 = (it != array1.end()) ? abs(*it - array2[i]) : INT_MAX;
        int diff2 = (it != array1.begin()) ? abs(*prev(it) - array2[i]) : INT_MAX;
        int current_min = min(diff1, diff2);
        if (current_min < min_diff) {
            min_diff = current_min;
            swap_pos2 = i;
            swap_pos1 = (diff1 <= diff2) ? (it - array1.begin()) : (it - array1.begin() - 1);
        }
    }
    swap(array1[swap_pos1], array1[swap_pos2]);
    for (int val : array1) cout << val << " ";
    cout << '\n';
    return 0;
}

Fibonacci Sum Representation

Represent a number as the sum of up to three Fibonacci numbers from the precomputed sequence up to 1e9. Output the combination or -1 if impossible.

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

int main() {
    vector<long long> fibs = {0, 1};
    for (int i = 2; ; ++i) {
        long long next = fibs[i-1] + fibs[i-2];
        if (next > 1000000000) break;
        fibs.push_back(next);
    }
    int queries;
    cin >> queries;
    while (queries--) {
        long long target;
        cin >> target;
        vector<long long> result;
        int count = 0;
        for (int i = fibs.size() - 1; i >= 0; --i) {
            if (fibs[i] <= target) {
                result.push_back(fibs[i]);
                target -= fibs[i];
                if (++count >= 3) break;
            }
        }
        if (target == 0) {
            for (long long num : result) cout << num << " ";
            cout << '\n';
        } else {
            cout << "-1\n";
        }
    }
    return 0;
}

Probability Calculation

Compute the combined probability of two scenarios where one team wins three games and the other wins two, considering all possible orderings.

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

int main() {
    double p;
    cin >> p;
    double scenario1 = p * p * p * (1 - p) * (1 - p);
    double scenario2 = p * p * (1 - p) * (1 - p) * (1 - p);
    double total = scenario1 + scenario2;
    cout << fixed << setprecision(6) << total << '\n';
    return 0;
}

Game Outcome Prediction

Determine which team reaches the required wins first by processing a sequence of game results.

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

int main() {
    string input;
    cin >> input;
    int required = 0;
    for (int i = 1; i < input.size(); ++i) {
        required = required * 10 + (input[i] - '0');
    }
    required = (required + 1) / 2;
    string results;
    cin >> results;
    int teamA = 0, teamB = 0;
    for (char c : results) {
        if (c == 'R') teamA++;
        else teamB++;
        if (teamA == required) {
            cout << "Team A wins in " << teamA + teamB << " games.\n";
            return 0;
        }
        if (teamB == required) {
            cout << "Team B wins in " << teamA + teamB << " games.\n";
            return 0;
        }
    }
    cout << "Game continues after " << teamA + teamB << " games.\n";
    return 0;
}

Factor-Based Grouping

Group numbers using union-find based on shared prime factors, efficiently managing factor lists to avoid time limit issues.

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

int main() {
    int n;
    cin >> n;
    vector<int> nums(n + 1);
    vector<vector<int>> prime_factors(n + 1);
    unordered_map<int, vector<int>> factor_map;
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
        int num = nums[i];
        if (num == 1) {
            prime_factors[i].push_back(1);
            factor_map[1].push_back(i);
            continue;
        }
        for (int f = 2; f * f <= num; ++f) {
            if (num % f == 0) {
                prime_factors[i].push_back(f);
                factor_map[f].push_back(i);
                while (num % f == 0) num /= f;
            }
        }
        if (num > 1) {
            prime_factors[i].push_back(num);
            factor_map[num].push_back(i);
        }
    }
    vector<int> visited(n + 1, 0);
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int f : prime_factors[cur]) {
            for (int idx : factor_map[f]) {
                if (!visited[idx]) {
                    visited[idx] = 1;
                    q.push(idx);
                }
            }
            factor_map[f].clear();
        }
    }
    vector<int> group1, group2;
    for (int i = 1; i <= n; ++i) {
        if (visited[i]) group1.push_back(nums[i]);
        else group2.push_back(nums[i]);
    }
    if (group2.empty()) cout << "-1 -1\n";
    else {
        cout << group1.size() << " " << group2.size() << "\n";
        for (int num : group1) cout << num << " ";
        cout << "\n";
        for (int num : group2) cout << num << " ";
        cout << "\n";
    }
    return 0;
}

Constructive Array Generation

Build an alternating pattern of 2s and 1s, adjusting values to meet sum constraints while maintaining the required count of 2s.

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

int main() {
    int len, total, twos;
    cin >> len >> total >> twos;
    vector<int> arr(len, 1);
    int current_sum = len;
    int last_two = -1;
    for (int i = 0; i < len; ++i) {
        if (twos > 0) {
            arr[i] = 2;
            current_sum++;
            if (i > 0) twos--;
            if (twos == 0) last_two = i;
        }
    }
    if (twos > 0) {
        cout << "-1\n";
        return 0;
    }
    if (current_sum > total) {
        cout << "-1\n";
        return 0;
    }
    int extra = total - current_sum;
    if (last_two == len - 1) {
        int groups = (len + 1) / 2;
        if (extra < groups) {
            cout << "-1\n";
            return 0;
        }
        int base = extra / groups;
        int rem = extra % groups;
        for (int i = 0; i < len; ++i) {
            if (i % 2 == 0) arr[i] += base;
            else {
                int add = min(rem, base);
                arr[i] += add;
                rem -= add;
            }
        }
    } else {
        arr[last_two + 1] += extra;
    }
    for (int num : arr) cout << num << " ";
    cout << '\n';
    return 0;
}

Subarray Product Maximization

Compute maximum and minimum subarray sums for two arrays, then determine the largest product from all possible pairings of these sums.

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

int main() {
    int sizeA, sizeB;
    cin >> sizeA >> sizeB;
    vector<long long> arrA(sizeA), arrB(sizeB);
    for (int i = 0; i < sizeA; ++i) cin >> arrA[i];
    for (int i = 0; i < sizeB; ++i) cin >> arrB[i];
    long long maxA = arrA[0], minA = arrA[0], curr = 0;
    for (int i = 0; i < sizeA; ++i) {
        curr += arrA[i];
        maxA = max(maxA, curr);
        if (curr < 0) curr = 0;
    }
    curr = 0;
    for (int i = 0; i < sizeA; ++i) {
        curr += arrA[i];
        minA = min(minA, curr);
        if (curr > 0) curr = 0;
    }
    long long maxB = arrB[0], minB = arrB[0];
    curr = 0;
    for (int i = 0; i < sizeB; ++i) {
        curr += arrB[i];
        maxB = max(maxB, curr);
        if (curr < 0) curr = 0;
    }
    curr = 0;
    for (int i = 0; i < sizeB; ++i) {
        curr += arrB[i];
        minB = min(minB, curr);
        if (curr > 0) curr = 0;
    }
    long long candidate1 = maxA * maxB;
    long long candidate2 = maxA * minB;
    long long candidate3 = minA * minB;
    long long candidate4 = minA * maxB;
    cout << max({candidate1, candidate2, candidate3, candidate4}) << '\n';
    return 0;
}

Tree Node Value Assignment

Assign values to tree nodes such that each red node's subtree sum is divisible by three, adjusting values based on modulo condiitons.

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

vector<vector<int>> tree;
string node_colors;
vector<int> node_values;

bool validate(int node) {
    int white_children = 0;
    for (int child : tree[node]) {
        if (node_colors[child] == 'W') white_children++;
    }
    return (white_children > 0 || node_colors[node] != 'R');
}

void dfs(int node) {
    node_values[node] = 2;
    int subtree_sum = node_values[node];
    for (int child : tree[node]) {
        dfs(child);
        subtree_sum += node_values[child];
    }
    if (node_colors[node] == 'R') {
        if (subtree_sum % 3 == 1) node_values[node] = 1;
        else if (subtree_sum % 3 == 2) {
            node_values[node] = 1;
            for (int child : tree[node]) {
                if (node_colors[child] == 'W') {
                    node_values[child] = 1;
                    break;
                }
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    tree.resize(n + 1);
    node_colors = " " + string(n, ' ');
    for (int i = 2; i <= n; ++i) {
        int parent;
        cin >> parent;
        tree[parent].push_back(i);
    }
    cin >> node_colors.substr(1);
    for (int i = 1; i <= n; ++i) {
        if (!validate(i)) {
            cout << "-1\n";
            return 0;
        }
    }
    node_values.resize(n + 1);
    dfs(1);
    for (int i = 1; i <= n; ++i) cout << node_values[i];
    cout << '\n';
    return 0;
}