Problem 1: Decrypting S Country's Military Cipher

Description

R and S are at war. R's spy, Xiao C, has obtained S's encryption rule: each uppercase letter maps to a unique uppercase letter (bijection). Given a known encrypted string and its original string, build the substitution table. Then translate a new intercepted encrypted string. If the mapping is incomplete (26 letters not covered) or inconsistent (duplicate mapping), output Failed.

Input Format

Three lines, each containing a string of uppercase letters (length 1–100):

1. Known encrypted text
2. Corresponding original text
3. New encrypted text to decode

Output Format

• Failed if mapping is invalid or incomplete.
• Otherwise, output the decoded original text.

Sample 1

Input:

AA
AB
EOWIE

Output:

Failed

Sample 2

Input:

QWERTYUIOPLKJHGFDSAZXCVBN
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO

Output:

Failed

Sample 3

Input:

MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO

Output:

NOIP

Solution Code

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

const int MAP_SIZE = 26;
const int STR_MAX = 105;

char forwardMap[MAP_SIZE];
char seen[MAP_SIZE];
char encKey[STR_MAX], plainRef[STR_MAX], targetMsg[STR_MAX];

int main() {
    cin >> encKey >> plainRef >> targetMsg;
    memset(forwardMap, 0, sizeof(forwardMap));
    memset(seen, 0, sizeof(seen));

    for (int i = 0; encKey[i]; ++i) {
        int from = encKey[i] - 'A';
        int to = plainRef[i];
        if (forwardMap[from] == 0) {
            forwardMap[from] = to;
        } else if (forwardMap[from] != to) {
            cout << "Failed";
            return 0;
        }
    }

    for (int i = 0; i < MAP_SIZE; ++i) {
        if (forwardMap[i] == 0) {
            cout << "Failed";
            return 0;
        }
    }

    for (int i = 0; i < MAP_SIZE; ++i) {
        if (seen[forwardMap[i] - 'A'] == 1) {
            cout << "Failed";
            return 0;
        }
        seen[forwardMap[i] - 'A'] = 1;
    }

    for (int i = 0; targetMsg[i]; ++i) {
        cout << forwardMap[targetMsg[i] - 'A'];
    }
    return 0;
}

---

Problem 2: Hankson's Inverse GCD and LCM Problem

Description

Given integers a0, a1, b0, b1, find how many positive integers x satisfy:

• gcd(x, a0) = a1
• lcm(x, b0) = b1

Input Format

• First line: integer n (number of test cases)
• Next n lines: four integers a0 a1 b0 b1

Output Format

For each case, output the count of valid x. Output 0 if none exist.

Sample Input

2
41 1 96 288
95 1 37 1776

Sample Output

6
2

Solution Code

#include <iostream>
using namespace std;

int computeGcd(int x, int y) {
    while (y) {
        int temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        int a0, a1, b0, b1;
        cin >> a0 >> a1 >> b0 >> b1;
        int factorA = a0 / a1;
        int factorB = b1 / b0;
        int result = 0;

        for (int d = 1; d * d <= b1; ++d) {
            if (b1 % d != 0) continue;
            int candidates[2] = {d, b1 / d};
            for (int val : candidates) {
                if (val == d && val * val != b1) continue;
                if (val % a1 != 0) continue;
                if (computeGcd(val / a1, factorA) != 1) continue;
                if (computeGcd(b1 / val, factorB) != 1) continue;
                if (d * d == b1 && val == d) {
                    result++;
                } else if (val != d) {
                    result++;
                }
            }
        }
        cout << result << endl;
    }
    return 0;
}

---

Problem 3: Maximizing Trade Profit in C Country

Description

A merchant travels from city 1 to city n. Each city has a crystal price. He may buy once and sell once later (or not at all). Find the maximum possible profit.

Input Format

• Line 1: n m (cities and roads)
• Line 2: n integers (prices in each city)
• Next m lines: x y z (road from x to y; z=1 one-way, z=2 two-way)

Output Format

Maximum profit (or 0 if no trade).

Sample Input

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

Sample Output

5

Solution Code

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

const int MAX_CITY = 100005;
const int MAX_ROAD = 500005;
const int INF = 0x3f3f3f3f;

struct Road {
    int to, next, dir;
} edges[MAX_ROAD * 2];

int head[MAX_CITY], edgeCnt;
int price[MAX_CITY];
int minCost[MAX_CITY], maxGain[MAX_CITY];
bool inQueue[MAX_CITY];

void addRoad(int u, int v, int type) {
    edges[edgeCnt] = {v, head[u], type};
    head[u] = edgeCnt++;
}

void spfaMin(int start) {
    memset(minCost, 0x3f, sizeof(minCost));
    memset(inQueue, 0, sizeof(inQueue));
    queue<int> q;
    q.push(start);
    minCost[start] = price[start];
    inQueue[start] = true;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        inQueue[cur] = false;
        for (int i = head[cur]; i != -1; i = edges[i].next) {
            if (edges[i].dir == 1) {
                int nxt = edges[i].to;
                if (minCost[nxt] > min(minCost[cur], price[nxt])) {
                    minCost[nxt] = min(minCost[cur], price[nxt]);
                    if (!inQueue[nxt]) {
                        q.push(nxt);
                        inQueue[nxt] = true;
                    }
                }
            }
        }
    }
}

void spfaMax(int end) {
    memset(maxGain, -0x3f, sizeof(maxGain));
    memset(inQueue, 0, sizeof(inQueue));
    queue<int> q;
    q.push(end);
    maxGain[end] = price[end];
    inQueue[end] = true;

    while (!q.empty()) {
        int cur = q.front(); q.pop();
        inQueue[cur] = false;
        for (int i = head[cur]; i != -1; i = edges[i].next) {
            if (edges[i].dir == 0) {
                int nxt = edges[i].to;
                if (maxGain[nxt] < max(maxGain[cur], price[nxt])) {
                    maxGain[nxt] = max(maxGain[cur], price[nxt]);
                    if (!inQueue[nxt]) {
                        q.push(nxt);
                        inQueue[nxt] = true;
                    }
                }
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    memset(head, -1, sizeof(head));
    edgeCnt = 0;

    for (int i = 1; i <= n; ++i) cin >> price[i];
    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        addRoad(x, y, 1);
        if (z == 2) addRoad(y, x, 1);
        addRoad(y, x, 0);
        if (z == 2) addRoad(x, y, 0);
    }

    spfaMin(1);
    spfaMax(n);

    int best = 0;
    for (int i = 1; i <= n; ++i) {
        best = max(best, maxGain[i] - minCost[i]);
    }
    cout << best;
    return 0;
}

---

Problem 4: Target-Shaped Sudoku Maximum Score

Description

Solve a 9×9 Sudoku with scoring zones:

• Center cell: 10 points
• Next ring: 9 points
• Next: 8 points
• Next: 7 points
• Outer ring: 6 points

Score = sum of (cell value × zone score). Find the maximum possible score.

Input Format

9 lines, each with 9 integers (0 for empty).

Output Format

Maximum score, or -1 if unsolvable.

Sample Input 1

7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2

Output 1

2829

Sample Input 2

0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6

Output 2

2852

Solution Code

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

int board[9][9];
bool rowUsed[9][10], colUsed[9][10], boxUsed[9][10];
int maxScore = -1;

int getZoneScore(int r, int c) {
    int layer = min(min(r, 8 - r), min(c, 8 - c));
    if (layer == 0) return 10;
    if (layer == 1) return 9;
    if (layer == 2) return 8;
    if (layer == 3) return 7;
    return 6;
}

int calcTotalScore() {
    int total = 0;
    for (int i = 0; i < 9; ++i)
        for (int j = 0; j < 9; ++j)
            total += board[i][j] * getZoneScore(i, j);
    return total;
}

int getBoxId(int r, int c) {
    return (r / 3) * 3 + (c / 3);
}

void placeNumber(int r, int c, int num, bool put) {
    if (put) {
        board[r][c] = num;
        rowUsed[r][num] = colUsed[c][num] = boxUsed[getBoxId(r, c)][num] = true;
    } else {
        board[r][c] = 0;
        rowUsed[r][num] = colUsed[c][num] = boxUsed[getBoxId(r, c)][num] = false;
    }
}

bool canPlace(int r, int c, int num) {
    return !rowUsed[r][num] && !colUsed[c][num] && !boxUsed[getBoxId(r, c)][num];
}

void dfs(int pos) {
    if (pos == 81) {
        maxScore = max(maxScore, calcTotalScore());
        return;
    }
    int r = pos / 9, c = pos % 9;
    if (board[r][c] != 0) {
        dfs(pos + 1);
    } else {
        for (int n = 1; n <= 9; ++n) {
            if (canPlace(r, c, n)) {
                placeNumber(r, c, n, true);
                dfs(pos + 1);
                placeNumber(r, c, n, false);
            }
        }
    }
}

int main() {
    for (int i = 8; i >= 0; --i) {
        for (int j = 8; j >= 0; --j) {
            int val;
            cin >> val;
            if (val != 0) placeNumber(i, j, val, true);
        }
    }
    dfs(0);
    cout << (maxScore == -1 ? -1 : maxScore);
    return 0;
}