7-1 Important Words Repeated Thrice
Print the given phrase three times.
I'm gonna WIN!
I'm gonna WIN!
I'm gonna WIN!
7-2 Learning C in Two Hours
Given total pages n, pages learned per hour k, and hours m, compute remaining pages. The result cannot be negative.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k, m;
cin >> n >> k >> m;
cout << max(n - k * m, 0) << '\n';
return 0;
}
7-3 Saving the Alien
Compute the factorial of (a + b).
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, ans = 1;
cin >> a >> b;
for (int i = 1; i <= a + b; ++i)
ans *= i;
cout << ans << '\n';
return 0;
}
7-4 Library Access Rules
Given age limits a (person 1) and b (person 2), and ages c (person 1) and d (person 2). Output access status based on conditions.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a, b, c, d;
cin >> a >> b >> c >> d;
if (d >= b && c < a) {
printf("%d-Y %d-Y\nqing 2 zhao gu hao 1", c, d);
} else if (c >= b && d < a) {
printf("%d-Y %d-Y\nqing 1 zhao gu hao 2", c, d);
} else if (c >= a && d >= a) {
printf("%d-Y %d-Y\nhuan ying ru guan", c, d);
} else if (c < a && d < a) {
printf("%d-N %d-N\nzhang da zai lai ba", c, d);
} else if (c >= a) {
printf("%d-Y %d-N\n1: huan ying ru guan", c, d);
} else {
printf("%d-N %d-Y\n2: huan ying ru guan", c, d);
}
return 0;
}
7-5 Try Your Luck
For each of six dice, output the n-th possible value starting from 6 downward, skipping the initial value.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
vector<int> a(6);
for (auto &x : a) cin >> x;
cin >> n;
for (int i = 0; i < 6; ++i) {
int cnt = 0;
for (int j = 6; j >= 1 && cnt < n; --j) {
if (j == a[i]) continue;
++cnt;
if (cnt == n) cout << j << " \n"[i == 5];
}
}
return 0;
}
7-6 ID Card Verification
Check 18-digit ID numbers: validate first 17 digits and check checksum against the 18th character.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int w[] = {7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2};
const char M[] = {'1', '0', 'X', '9', '8', '7', '6', '5', '4', '3', '2'};
vector<string> invalid;
while (n--) {
string s;
cin >> s;
int sum = 0;
bool bad = false;
for (int i = 0; i < 17; ++i) {
if (!isdigit(s[i])) {
bad = true;
break;
}
sum += (s[i] - '0') * w[i];
}
if (bad || M[sum % 11] != s.back()) {
invalid.push_back(s);
}
}
if (invalid.empty()) cout << "All passed\n";
else for (auto &s : invalid) cout << s << '\n';
return 0;
}
7-8 Consecutive Factors
Find the longest sequence of consecutive positive integers whose product divides the given number n.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n;
cin >> n;
auto isPrime = [](i64 x) -> bool {
if (x < 2) return false;
if (x == 2) return true;
for (i64 i = 2; i * i <= x; ++i)
if (x % i == 0) return false;
return true;
};
if (isPrime(n)) {
cout << 1 << '\n' << n << '\n';
return 0;
}
i64 prod = 1, start = 2, len = 0;
vector<i64> best;
i64 limit = 2 * sqrt(n);
for (i64 i = 2; i <= limit; ++i) {
prod *= i;
++len;
while (prod > n) {
prod /= start;
++start;
--len;
}
if (n % prod == 0 && len > (i64)best.size()) {
best.clear();
for (i64 j = start; j <= i; ++j)
best.push_back(j);
}
}
cout << best.size() << '\n';
for (size_t i = 0; i < best.size(); ++i) {
cout << best[i] << "*\n"[i == best.size() - 1];
}
return 0;
}
7-8 Rent
Given an 11-digit phone number, extract unique digits in descending order as arr, then output arr and for each digit of the phone number, its index in arr.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
vector<int> arr, seen(10, 0), idx(10);
for (char ch : s) {
int d = ch - '0';
if (!seen[d]) {
seen[d] = 1;
arr.push_back(d);
}
}
sort(arr.begin(), arr.end(), greater<int>());
for (int i = 0; i < (int)arr.size(); ++i)
idx[arr[i]] = i;
cout << "int[] arr = new int[]{";
for (int i = 0; i < (int)arr.size(); ++i) {
cout << arr[i];
if (i + 1 < (int)arr.size()) cout << ',';
}
cout << "};\n";
cout << "int[] index = new int[]{";
for (int i = 0; i < 11; ++i) {
cout << idx[s[i] - '0'];
if (i < 10) cout << ',';
}
cout << "};\n";
return 0;
}
7-9 Harry Potter's Exam
Use Floyd-Warshall to compute all-pairs shortest paths. For each animal, find the maximum distance to any other animal. Choose the animal with the smallest such maximum; if none can reach all, output 0.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
const i64 INF = 1e18;
vector dis(n + 1, vector<i64>(n + 1, INF));
for (int i = 1; i <= n; ++i) dis[i][i] = 0;
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
dis[u][v] = w;
dis[v][u] = w;
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][k] + dis[k][j] < dis[i][j])
dis[i][j] = dis[i][k] + dis[k][j];
i64 bestMax = INF;
int bestAnimal = 0;
for (int i = 1; i <= n; ++i) {
i64 curMax = 0;
bool ok = true;
for (int j = 1; j <= n; ++j) {
if (dis[i][j] == INF) { ok = false; break; }
curMax = max(curMax, dis[i][j]);
}
if (ok && curMax < bestMax) {
bestMax = curMax;
bestAnimal = i;
}
}
if (bestAnimal) cout << bestAnimal << ' ' << bestMax << '\n';
else cout << 0 << '\n';
return 0;
}
7-10 Train Carriage Dispatching
Simulate using a stack (track 3) to reorder carriages from track 1 to track 2.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s1, s2;
cin >> s1 >> s2;
reverse(s1.begin(), s1.end());
stack<char> st; // track 3
vector<string> moves;
int idx = 0;
for (char target : s2) {
if (!st.empty() && st.top() == target) {
moves.push_back("3->2");
st.pop();
continue;
}
while (idx < (int)s1.size() && s1[idx] != target) {
st.push(s1[idx]);
moves.push_back("1->3");
++idx;
}
if (idx < (int)s1.size() && s1[idx] == target) {
moves.push_back("1->2");
++idx;
} else {
cout << "Are you kidding me?\n";
return 0;
}
}
for (auto &move : moves) cout << move << '\n';
return 0;
}
7-11 File Transfer
Maintain a union-find structure to connect computers. Answer quereis whether two computers are connected, and at the end output the number of components.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DSU {
vector<int> parent;
DSU(int n) {
parent.resize(n + 1);
for (int i = 0; i <= n; ++i) parent[i] = i;
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int a, int b) {
a = find(a); b = find(b);
if (a != b) parent[a] = b;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
DSU dsu(n);
char op;
int a, b;
while (cin >> op) {
if (op == 'S') break;
cin >> a >> b;
if (op == 'C') {
cout << (dsu.find(a) == dsu.find(b) ? "yes\n" : "no\n");
} else {
dsu.unite(a, b);
}
}
int comp = 0;
for (int i = 1; i <= n; ++i)
if (dsu.find(i) == i) ++comp;
if (comp == 1) cout << "The network is connected.\n";
else cout << "There are " << comp << " components.\n";
return 0;
}
7-12 Virus Origin Tracing
Find the tree root (node without parent). DFS to compute max depth. Sort children of each node lexicographically. Then find the path with max depth; due to sorting, the first found path is the lexicographically smallest.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<vector<int>> g(n);
vector<int> parent(n, -1);
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
g[i].resize(k);
for (int j = 0; j < k; ++j) {
cin >> g[i][j];
parent[g[i][j]] = i;
}
}
int root = 0;
while (parent[root] != -1) root = parent[root];
for (int i = 0; i < n; ++i)
sort(g[i].begin(), g[i].end());
int maxDepth = 0;
function<void(int, int)> dfs1 = [&](int u, int d) {
maxDepth = max(maxDepth, d);
for (int v : g[u])
dfs1(v, d + 1);
};
dfs1(root, 1);
vector<int> path;
path.push_back(root);
function<void(int, int)> dfs2 = [&](int u, int d) {
if (d == maxDepth) {
cout << maxDepth << '\n';
for (size_t i = 0; i < path.size(); ++i) {
cout << path[i] << " \n"[i + 1 == path.size()];
}
exit(0);
}
for (int v : g[u]) {
path.push_back(v);
dfs2(v, d + 1);
path.pop_back();
}
};
dfs2(root, 1);
return 0;
}
7-14 Ladder Map
Run Dijkstra twice: once minimizing time (secondary: minimize distance), once minimizing distance (secondary: minimize number of edges). Track paths and compare them.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Dijkstra {
using P = pair<i64, i64>;
vector<i64> dist, nodeCnt, parent;
vector<vector<array<i64, 3>>> g;
int n;
Dijkstra(int _n) : n(_n) {
dist.assign(n + 1, LLONG_MAX);
nodeCnt.assign(n + 1, 1);
parent.assign(n + 1, -1);
g.resize(n + 1);
}
void addEdge(int u, int v, i64 w, i64 val) {
g[u].push_back({v, w, val});
}
void run(int s) {
priority_queue<P, vector<P>, greater<P>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [curDist, u] = pq.top(); pq.pop();
if (curDist > dist[u]) continue;
for (auto &e : g[u]) {
int v = e[0]; i64 w = e[1], val = e[2];
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
nodeCnt[v] = nodeCnt[u] + val;
parent[v] = u;
pq.push({dist[v], v});
} else if (dist[v] == dist[u] + w && nodeCnt[v] > nodeCnt[u] + val) {
nodeCnt[v] = nodeCnt[u] + val;
parent[v] = u;
}
}
}
}
vector<int> getPath(int t) {
vector<int> path;
for (int cur = t; cur != -1; cur = parent[cur])
path.push_back(cur);
reverse(path.begin(), path.end());
return path;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
Dijkstra timeD(n), distD(n);
while (m--) {
int u, v, oneway, len, t;
cin >> u >> v >> oneway >> len >> t;
timeD.addEdge(u, v, t, len);
distD.addEdge(u, v, len, 1);
if (!oneway) {
timeD.addEdge(v, u, t, len);
distD.addEdge(v, u, len, 1);
}
}
int s, d;
cin >> s >> d;
timeD.run(s);
distD.run(s);
auto pathT = timeD.getPath(d);
auto pathD = distD.getPath(d);
if (pathT == pathD) {
cout << "Time = " << timeD.dist[d] << "; ";
cout << "Distance = " << distD.dist[d] << ": ";
for (size_t i = 0; i < pathD.size(); ++i) {
cout << pathD[i] << (i + 1 == pathD.size() ? "\n" : " => ");
}
} else {
cout << "Time = " << timeD.dist[d] << ": ";
for (size_t i = 0; i < pathT.size(); ++i) {
cout << pathT[i] << (i + 1 == pathT.size() ? "\n" : " => ");
}
cout << "Distance = " << distD.dist[d] << ": ";
for (size_t i = 0; i < pathD.size(); ++i) {
cout << pathD[i] << (i + 1 == pathD.size() ? "\n" : " => ");
}
}
return 0;
}