Task 1 – Factor Splitting

Given a positive integer n that is the product of two distinct primes, output the larger one.

Input: One integer n (≤ 2·109).
Output: The larger prime factor.

Observation: The first divisor (other than 1) must be the smaller prime, so the answer is n / i once the smallest i > 1 with n % i == 0 is found.

#include <iostream>
using namespace std;
int main() {
    long long n;  cin >> n;
    for (long long d = 2; d * d <= n; ++d)
        if (n % d == 0) { cout << n / d; return 0; }
    return 0;
}

Task 2 – Treasure Hunt

A tower has N floors (numbered 1..N) plus a top floor. Each floor i has M rooms arranged in a circle (0..M-1). Every room contains two integers:

• stair: 1 if the room has a staircase to the next floor, 0 otherwise.
• skip: the number of staircase rooms to skip (starting from the current room) before taking the next staircase.

Starting from a given room on floor 1, accumulate the skip values of the first room visited on each floor (mod 20123). Output the total.

Algorithm: For each floor, pre-count how many stairacse rooms exist. Then simulate the circular walk, counting only staircase rooms.

#include <iostream>
using namespace std;
const int MOD = 20123;
int main() {
    ios::sync_with_stdio(false);
    int N, M;  cin >> N >> M;
    bool stair[N+1][M];
    int  skip[N+1][M], cnt[N+1] = {0};
    for (int i = 1; i <= N; ++i)
        for (int j = 0; j < M; ++j) {
            cin >> stair[i][j] >> skip[i][j];
            cnt[i] += stair[i][j];
        }
    int pos;  cin >> pos;
    int key = 0;
    for (int fl = 1; fl <= N; ++fl) {
        key = (key + skip[fl][pos]) % MOD;
        int need = skip[fl][pos] % cnt[fl];
        if (need == 0) need = cnt[fl];
        while (need) {
            if (stair[fl][pos]) --need;
            if (need) { pos = (pos + 1) % M; }
        }
    }
    cout << key;
    return 0;
}

Task 3 – Flower Arrangement

Place m identical pots into n distinct kinds of flowers. Flowers must appear in ascending order of their labels, and kind i can supply at most a<sub>i</sub> pots. Count the number of distinct arrangements modulo 1 000 007.

DP: Let f[i][j] = ways to use the first i kinds to fill exactly j pots.

Transition: f[i][j] = Σ f[i-1][j-k] for 0 ≤ k ≤ min(a[i], j).

#include <iostream>
using namespace std;
const int MOD = 1000007;
int main() {
    int n, m;  cin >> n >> m;
    int a[n+1];
    for (int i = 1; i <= n; ++i) cin >> a[i];

    int dp[n+1][m+1] = {0};
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= min(a[i], j); ++k)
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD;
    cout << dp[n][m];
    return 0;
}

Task 4 – Cultural Journey

A traveler starts at country S and wants to reach country T. Each country has a culture. The traveler:

• learns the culture of every visited country once;
• cannot visit any country whose culture he already knows;
• cannot enter countries whose culture rejects any culture he currently possesses.

Given the cultural matrix and bidirectional weighted roads, compute the shortest path from S to T, or -1 if impossible.

Solution: Run Dijkstra on the state graph where a state is (current country, bitmask of learned cultures). With N ≤ 100 and K ≤ 100, a bitmask is impractical; instead, note that the set of learned cultures is exactly the culutres of the countries on the path. Thus we can simply forbid entering a country whose culture is already known or rejected by any known culture.

#include <iostream>
#include <queue>
#include <climits>
using namespace std;
const int MAX = 105;
int C[MAX], ban[MAX][MAX], adj[MAX][MAX], dist[MAX];
bool vis[MAX];

int main() {
    int N, K, M, S, T;
    cin >> N >> K >> M >> S >> T;
    for (int i = 1; i <= N; ++i) cin >> C[i];
    for (int i = 1; i <= K; ++i)
        for (int j = 1; j <= K; ++j) cin >> ban[i][j];

    for (int i = 1; i <= M; ++i) {
        int u, v, d;  cin >> u >> v >> d;
        if (adj[u][v] == 0 || adj[u][v] > d) adj[u][v] = adj[v][u] = d;
    }

    fill(dist, dist + MAX, INT_MAX);
    dist[S] = 0;

    for (int step = 0; step < N; ++step) {
        int u = -1;
        for (int i = 1; i <= N; ++i)
            if (!vis[i] && (u == -1 || dist[i] < dist[u])) u = i;
        if (u == -1 || dist[u] == INT_MAX) break;
        vis[u] = true;

        for (int v = 1; v <= N; ++v) if (adj[u][v]) {
            bool ok = true;
            for (int k = 1; k <= N; ++k)
                if (vis[k] && (C[k] == C[v] || ban[C[v]][C[k]])) { ok = false; break; }
            if (ok && dist[v] > dist[u] + adj[u][v])
                dist[v] = dist[u] + adj[u][v];
        }
    }
    cout << (dist[T] == INT_MAX ? -1 : dist[T]);
    return 0;
}