T1 Neural Network Propagation

A neural network is modeled as a directed graph where nodes represent neurons. Each neuron may have multiple input chennels (Xi) and output channels (Yi). State C_i of a neuron depends on incoming signals and its threshold U_i. For non-input layers, initial C_i is zero.

Propagation follows:

C_i = C_i - U_i
if C_i > 0: neuron fires and sends signal C_i * W_ji to connected neurons

Input

• First line: n (neurons), p (connections)
• Next n lines: initial state and threshold for each neuron
• Next p lines: i j w meaning edge from i to j with weight w

Output

List all output-layer neurons (those with no outgoing edges) having final C_i > 0, sorted by index ascending. Print NULL if none.

Approach

Simulate propagation using topological processing: repeatedly process neurons with no pending inputs and positive net signal until stable.

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

const int MAXN = 205;

struct Link {
    int target, weight, nextIdx;
} conn[MAXN * MAXN];
int head[MAXN], degIn[MAXN], state[MAXN], thresh[MAXN], proc[MAXN];
int nodeCnt, netSize, linkCnt;

void attachEdge(int src, int tgt, int w) {
    conn[linkCnt] = {tgt, w, head[src]};
    head[src] = linkCnt++;
    degIn[tgt]++;
}

void fireNeuron(int idx) {
    state[idx] -= thresh[idx];
    proc[idx] = 1;
    for (int e = head[idx]; e != -1; e = conn[e].nextIdx) {
        int nb = conn[e].target;
        degIn[nb]--;
        state[nb] += state[idx] * conn[e].weight;
    }
}

int main() {
    memset(head, -1, sizeof(head));
    cin >> netSize >> linkCnt;
    for (int i = 0; i < netSize; i++) {
        cin >> state[i] >> thresh[i];
        if (state[i] > 0) thresh[i] = 0;
    }
    for (int i = 0; i < linkCnt; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        attachEdge(s - 1, t - 1, w);
    }
    bool updated = true;
    while (updated) {
        updated = false;
        for (int i = 0; i < netSize; i++) {
            if (degIn[i] == 0 && state[i] - thresh[i] > 0 && !proc[i]) {
                fireNeuron(i);
                updated = true;
            }
        }
    }
    bool found = false;
    for (int i = 0; i < netSize; i++) {
        if (head[i] == -1 && state[i] > 0) {
            cout << i + 1 << " " << state[i] << "\n";
            found = true;
        }
    }
    if (!found) cout << "NULL\n";
    return 0;
}

---

T2 Logical Deduction Game

Given M participants, exactly N always lie, rest always tell truth. Statements:

• I am guilty. / I am not guilty.
• NAME is guilty. / NAME is not guilty.
• Today is WEEKDAY. Other phrases ignored.

Determine guilty party, or output Cannot Determine / Impossible.

Input

• First line: M N P
• Next M lines: participant names
• Next P lines: NAME: statement

Output

Single guilty name, or ambiguity indicator.

Aprpoach

Enumerate each person as culprit and each weekday. Classify statements into categories, track truthfulness per speaker, insure liars count matches N.

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

const int MAXP = 25, MAXST = 105;
char names[MAXP][35];
int guiltyID[MAXST], weekID[MAXST];
int guiltyCnt, weekCnt;
char guiltyPh[] = "is guilty.", notGuiltyPh[] = "is not guilty.";
char selfG[] = "I am guilty.", selfNG[] = "I am not guilty.";
char weekPh[] = "Today is ";
char days[7][12] = {"Monday.","Tuesday.","Wednesday.","Thursday.","Friday.","Saturday.","Sunday."};
int eval[MAXP], ans[MAXP];

bool validScenario(int suspect, int dayIdx) {
    memset(eval, 0, sizeof(eval));
    for (int i = 0; i < guiltyCnt; i++) {
        int spk = guiltyID[i] / 2, tgt = guiltyID[i] % 2;
        if (tgt == suspect) {
            if (eval[spk] == 0 || eval[spk] == 1) eval[spk] = 1;
            else return false;
        } else {
            if (eval[spk] == 0 || eval[spk] == 2) eval[spk] = 2;
            else return false;
        }
    }
    for (int i = 0; i < weekCnt; i++) {
        int spk = weekID[i] / 2, d = weekID[i] % 2;
        if (d == dayIdx) {
            if (eval[spk] == 0 || eval[spk] == 1) eval[spk] = 1;
            else return false;
        } else {
            if (eval[spk] == 0 || eval[spk] == 2) eval[spk] = 2;
            else return false;
        }
    }
    int trues = 0, unknowns = 0;
    for (int i = 0; i < MAXP; i++) {
        if (eval[i] == 2) trues++;
        if (eval[i] == 0) unknowns++;
    }
    return (MAXST - trues <= unknowns && trues <= MAXST);
}

int main() {
    int M, N, P;
    cin >> M >> N >> P;
    for (int i = 0; i < M; i++) cin >> names[i];
    string line;
    getline(cin, line);
    for (int i = 0; i < P; i++) {
        getline(cin, line);
        int spkIdx = -1;
        for (int j = 0; j < M; j++) {
            if (line.find(names[j]) == 0) {
                spkIdx = j;
                break;
            }
        }
        size_t colPos = line.find(':');
        string stmt = line.substr(colPos + 2);
        if (stmt == selfG) {
            guiltyID[guiltyCnt++] = spkIdx * 2 + spkIdx;
        } else if (stmt == selfNG) {
            guiltyID[guiltyCnt++] = spkIdx * 2 + spkIdx;
        } else if (stmt.compare(0, strlen(weekPh), weekPh) == 0) {
            string dayStr = stmt.substr(strlen(weekPh));
            for (int d = 0; d < 7; d++) {
                if (dayStr == days[d]) {
                    weekID[weekCnt++] = spkIdx * 2 + d;
                    break;
                }
            }
        } else {
            for (int t = 0; t < M; t++) {
                if (stmt.find(names[t]) == 0) {
                    string tail = stmt.substr(strlen(names[t]));
                    if (tail == string(guiltyPh)) {
                        guiltyID[guiltyCnt++] = spkIdx * 2 + t;
                    } else if (tail == string(notGuiltyPh)) {
                        guiltyID[guiltyCnt++] = spkIdx * 2 + t;
                    }
                    break;
                }
            }
        }
    }
    int candidates = 0, who = -1;
    for (int g = 0; g < M; g++) {
        for (int d = 0; d < 7; d++) {
            if (validScenario(g, d)) {
                ans[g] = 1;
                candidates++;
                who = g;
            }
        }
    }
    if (candidates == 0) cout << "Impossible\n";
    else if (candidates > 1) cout << "Cannot Determine\n";
    else cout << names[who] << "\n";
    return 0;
}

---

T3 Maximum Score Binary Tree with Inorder 1..n

Given scores for nodes 1..n, build binary tree with inorder = 1..n to maximize:

score(subtree) = score(left) * score(right) + root_score

Empty subtree score = 1. Output max total score and preorder traversal.

Input

• n
• n scores

Output

Max score and preorder sequence.

Approach

Interval DP: dp[l][r] = max score for inorder segment [l, r]. Track root for reconstruction.

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

typedef long long ll;
const int MAXN = 35;
ll score[MAXN], best[MAXN][MAXN];
int rootIdx[MAXN][MAXN];

void preorder(int left, int right) {
    if (left > right) return;
    int rt = rootIdx[left][right];
    cout << rt + 1 << " ";
    preorder(left, rt - 1);
    preorder(rt + 1, right);
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> score[i];
    for (int i = 0; i < n; i++) {
        best[i][i] = score[i];
        rootIdx[i][i] = i;
    }
    for (int len = 1; len < n; len++) {
        for (int l = 0; l + len < n; l++) {
            int r = l + len;
            for (int k = l; k <= r; k++) {
                ll leftSc = (k > l) ? best[l][k - 1] : 1;
                ll rightSc = (k < r) ? best[k + 1][r] : 1;
                ll cand = leftSc * rightSc + score[k];
                if (cand > best[l][r]) {
                    best[l][r] = cand;
                    rootIdx[l][r] = k;
                }
            }
        }
    }
    cout << best[0][n - 1] << "\n";
    preorder(0, n - 1);
    return 0;
}

---

T4 Infection Containment on a Tree

Tree represents infection paths. Node 1 initially infected. Each cycle, only one edge can be cut. Minimize total infected.

Input

• n p
• p edges

Output

Min infected count.

Approach

Search over cutting sequences. Simulate spread given one edge removal per step.

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

const int MAXN = 305;
vector<int> graph[MAXN];
int parent[MAXN], infected[MAXN], minInfected;

void buildParent(int cur, int par) {
    parent[cur] = par;
    for (int nb : graph[cur]) {
        if (nb != par) buildParent(nb, cur);
    }
}

void simulate(int depth, int totalNodes) {
    if (depth >= minInfected) return;
    int snapshot[MAXN];
    copy(infected, infected + totalNodes, snapshot);
    vector<int> newInf;
    for (int i = 0; i < totalNodes; i++) {
        if (infected[i] == 1) infected[i] = 2;
    }
    for (int i = 0; i < totalNodes; i++) {
        if (infected[i] == 2) {
            for (int nb : graph[i]) {
                if (nb != parent[i] && infected[nb] == 0) {
                    infected[nb] = 1;
                    newInf.push_back(nb);
                }
            }
        }
    }
    bool canStop = true;
    for (int i = 0; i < totalNodes; i++) {
        if (infected[i] == 2) {
            for (int nb : graph[i]) {
                if (nb != parent[i] && infected[nb] == 1) {
                    canStop = false;
                    infected[nb] = 3;
                    simulate(depth + newInf.size() - 1, totalNodes);
                    infected[nb] = 1;
                }
            }
        }
    }
    copy(snapshot, snapshot + totalNodes, infected);
    if (canStop) {
        minInfected = min(minInfected, depth);
    }
}

int main() {
    int n, p;
    cin >> n >> p;
    for (int i = 0; i < p; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    buildParent(0, -1);
    infected[0] = 1;
    minInfected = n;
    simulate(1, n);
    cout << minInfected << "\n";
    return 0;
}