Problem A: Counting Non-Unit Integers

The objective is to determine the count of numbers that are either prime or composite within a given sequence. Since the number 1 is neither prime nor composite, the solution involves counting all input values excluding those equal to 1.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    if (!(cin >> count)) return 0;

    int valid_entries = 0;
    for (int i = 0; i < count; ++i) {
        int value;
        cin >> value;
        if (value != 1) {
            valid_entries++;
        }
    }

    cout << valid_entries << endl;
    return 0;
}

Problem B: String Pattern Matching with Dynamic Programming

This problem requires calculating a score based on specific substring occurrences within a larger string. The scoring mechanism utilizes a Fibonacci-like sequence for weighting. Several variation of the target pattern "mygo" (including spaces) must be detected.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAX_LEN = 200010;

long long dp[MAX_LEN];

bool matchesPattern(const string& segment, const string& pattern) {
    if (segment.length() != pattern.length()) return false;
    for (size_t i = 0; i < segment.length(); ++i) {
        if (pattern[i] == ' ') continue;
        if (segment[i] != pattern[i]) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    string input;
    cin >> input;
    int n = input.length();

    string s = "!" + input + "soyorinlove";

    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i <= n; ++i) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
    }

    vector<string> targets = {
        "mygo", "m ygo", "m y go", "m y g o",
        "my go", "my g o", "myg o", "m yg o"
    };

    long long total_score = 0;
    for (int i = 1; i <= n; ++i) {
        for (const auto& pat : targets) {
            if (i + pat.length() - 1 > n) continue;
            string sub = s.substr(i, pat.length());
            if (matchesPattern(sub, pat)) {
                long long ways = (dp[i - 1] * dp[n - (i + (int)pat.length()) + 1]) % MOD;
                total_score = (total_score + ways) % MOD;
            }
        }
    }

    cout << total_score << endl;
    return 0;
}

Problem C: Greedy Reduction Strategy

The core logic involves manipulating array elements where inserting zeros between numbers is mathematically equivalent to reducing the adjacent values. A greedy approach minimizes the values by subtracting the maximum possible amount from neighbors.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    
    vector<ll> arr(2 * n + 5, 0);

    for (int i = 2; i <= 2 * n; i += 2) {
        cin >> arr[i];
    }
    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    arr[0] = 1e9;
    arr[2 * n + 2] = 1e9;

    ll reduction_count = 0;
    for (int i = 1; i <= 2 * n + 1; i += 2) {
        ll decrease = min(arr[i + 1] - 1, arr[i - 1] - 1);
        arr[i + 1] -= decrease;
        arr[i - 1] -= decrease;
        reduction_count += decrease;
    }

    cout << reduction_count << "\n";
    return 0;
}

Problem E: Array Sortability Check

This task verifies if an array can be sorted using specific operations. The logic depends on the parity of the array length. For odd lengths, a simulation of operations is required to check if the sorted condition is achievable.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    if (n % 2 == 0) {
        cout << "YES" << "\n";
        return;
    }

    ll accumulated = 0;
    for (int i = n - 1; i >= 2; i -= 2) {
        a[i] += accumulated * i;
        a[i - 1] += accumulated * (i - 1);

        if (a[i] > a[i + 1]) {
            cout << "NO" << "\n";
            return;
        }

        ll diff = (a[i + 1] - a[i]) / i;
        accumulated += diff;
        a[i] += diff * i;
        a[i - 1] += diff * (i - 1);
    }

    if (is_sorted(a.begin() + 1, a.end())) {
        cout << "YES" << "\n";
    } else {
        cout << "NO" << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Problem G: Prime Sum Permutation

Construct a permutation of numbers from 1 to N such that the sum of adjacent elements is prime. A depth-first search combined with a sieve method identifies valid configurations.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_VAL = 4000;
bool is_composite[MAX_VAL];

void precomputePrimes(int limit) {
    is_composite[0] = is_composite[1] = true;
    for (int i = 2; i * i <= limit; ++i) {
        if (!is_composite[i]) {
            for (int j = i * i; j <= limit; j += i)
                is_composite[j] = true;
        }
    }
}

void generatePermutation(int n) {
    if (n == 0) return;
    if (n == 1) {
        cout << 1 << " ";
        return;
    }
    if (n == 2) {
        cout << 2 << " " << 1 << " ";
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!is_composite[n + i]) {
            generatePermutation(i - 1);
            for (int j = n; j >= i; --j) {
                cout << j << " ";
            }
            return;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    precomputePrimes(2 * n);
    generatePermutation(n);
    cout << endl;
    return 0;
}

Problem I: Coordinate Path Calculation

Calculate the minimum path cost based on target position t, acceleration a, and a threshold k. The solution involves conditional logic based on the signs and magnitudes of the input parameters.

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long t, a, k;
    cin >> t >> a >> k;

    if (t * a > 0) {
        if (abs(t) > abs(a)) {
            cout << abs(t) << endl;
        } else {
            cout << 2 * abs(a) - abs(t) << endl;
        }
    } else if (t * a < 0) {
        if (k > abs(a)) {
            cout << 2 * abs(a) + abs(t) << endl;
        } else {
            cout << 2 * (abs(t) + abs(a)) + abs(t) << endl;
        }
    } else {
        if (a == 0) {
            cout << abs(t) << endl;
        } else if (t == 0) {
            cout << abs(a) << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

Problem L: Game Victory Condition

Determine if a player can reach a target score n starting from m given specific game rules. A solution exists if the difference between the target and current score is even.

#include <iostream>

using namespace std;

int main() {
    int target, current;
    cin >> target >> current;

    if (current > target) {
        cout << -1 << endl;
        return 0;
    }

    int diff = target - current;
    if (diff % 2 == 0) {
        cout << (diff / 2 + current) << " " << (diff / 2) << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

Problem M: Permutation Index Displacemetn

Analyze two permutations to determine connectivity based on the displacement of elements. The solution checks the absolute difference between indices of identical values in both permutations.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> posA(n + 1), posB(n + 1);
    int val;

    for (int i = 1; i <= n; ++i) {
        cin >> val;
        posA[val] = i;
    }
    for (int i = 1; i <= n; ++i) {
        cin >> val;
        posB[val] = i;
    }

    if (n <= 1) {
        cout << -1 << '\n';
        return;
    }

    if (n == 2) {
        if (posA[1] == posB[1] && posA[2] == posB[2]) {
            cout << -1 << '\n';
        } else {
            cout << 1 << '\n';
        }
        return;
    }

    bool found = false;
    for (int i = 1; i <= n; ++i) {
        int diff = abs(posA[i] - posB[i]);
        if (diff <= 1) {
            if (diff == 0 && (i == 1 || i == n)) {
                continue;
            }
            cout << 1 << '\n';
            found = true;
            break;
        }
    }

    if (!found) {
        cout << 2 << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}