T1 - Meteor Shower Era
Approach
Follow a direct simulation logic:
- Determine the first year the observer sees a meteor:
(E + B) % 50. - If this age exceeds the lifespan
L, output 0. - Otherwise, calculate the remaining years
L - first_yearand divide by the cycle length 50, adding 1 for the first sighting.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int countShowers(int birth, int life, int startYear) {
int firstSighting = (birth + startYear) % 50;
if (firstSighting > life) return 0;
int remaining = life - firstSighting;
return remaining / 50 + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int b, l, e;
cin >> b >> l >> e;
cout << countShowers(b, l, e) << '\n';
}
return 0;
}
Python Implementation
T = int(input())
for _ in range(T):
b, l, e = map(int, input().split())
first = (b + e) % 50
if first > l:
print(0)
else:
rest = l - first
print(rest // 50 + 1)
T2 - String Concatenation
Approach
Check for the longest suffix of "marco" that matches a prefix of the input string S. If a match exists, prepend "MARCO" to the remaining part of S.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
string process(const string& s) {
string pattern = "marco";
int maxMatch = 0;
for (int k = 1; k <= min(5, (int)s.size()); ++k) {
if (pattern.substr(5 - k) == s.substr(0, k))
maxMatch = k;
}
if (maxMatch == 0) return s;
return "MARCO" + s.substr(maxMatch);
}
int main() {
int t; cin >> t;
while (t--) {
string s; cin >> s;
cout << process(s) << '\n';
}
return 0;
}
Python Implementation
def solve_case(s: str) -> str:
prefix = "marco"
matched = 0
for i in range(1, 6):
if s[:i] == prefix[-i:]:
matched = i
return "MARCO" + s[matched:] if matched else s
T = int(input())
for _ in range(T):
print(solve_case(input()))
T3 - TNT Relay
Approach
Use a sliding window of size K+1. Maintain a counter cur for empty blocks ('-') within the window. Track the maximum mx of cur. If K >= N, output -1. Otherwise, the minimum TNT required is (K + 1) - mx.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int minTNT(int n, int k, string blocks) {
if (k >= n) return -1;
int window = k + 1, cur = 0, mx = 0;
for (int i = 0; i < n; ++i) {
if (blocks[i] == '-') cur++;
if (i - window >= 0 && blocks[i - window] == '-') cur--;
mx = max(mx, cur);
}
return window - mx;
}
int main() {
int t; cin >> t;
while (t--) {
int n, k; string s;
cin >> n >> k >> s;
cout << minTNT(n, k, s) << '\n';
}
return 0;
}
Python Implementation
def min_tnt(n, k, s):
if k >= n: return -1
win, cur, mx = k + 1, 0, 0
for i in range(n):
if s[i] == '-': cur += 1
if i - win >= 0 and s[i - win] == '-': cur -= 1
mx = max(mx, cur)
return win - mx
T = int(input())
for _ in range(T):
n, k = map(int, input().split())
s = input()
print(min_tnt(n, k, s))
T4 - Poker Hand Evaluation
Approach
Read 5 cards. Map ranks to numbers (2-14). Sort by rank. Count ranks to find pairs, triples, etc. Check for Flush (same suit) and Straight (consecutive ranks). Evaluate hand strength based on priority rules.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int getVal(string r) {
if (r == "A") return 14;
if (r == "K") return 13;
if (r == "Q") return 12;
if (r == "J") return 11;
return stoi(r);
}
int main() {
int t; cin >> t;
while (t--) {
vector<pair<int, string>> hand(5);
for (int i = 0; i < 5; ++i) {
string r, s; cin >> r >> s;
hand[i] = {getVal(r), s};
}
sort(hand.begin(), hand.end());
map<int, int> freq;
bool flush = true, straight = true;
for (int i = 0; i < 5; ++i) {
freq[hand[i].first]++;
if (i > 0) {
if (hand[i].second != hand[i-1].second) flush = false;
if (hand[i].first != hand[i-1].first + 1) straight = false;
}
}
int pairs = 0, maxFreq = 0;
for (auto& p : freq) {
if (p.second == 2) pairs++;
maxFreq = max(maxFreq, p.second);
}
if (straight && flush) {
if (hand[4].first == 14) cout << "Royal Flush\n";
else cout << "Straight Flush\n";
} else if (maxFreq == 4) cout << "Four of a Kind\n";
else if (maxFreq == 3 && pairs == 1) cout << "Full House\n";
else if (flush) cout << "Flush\n";
else if (straight) cout << "Straight\n";
else if (maxFreq == 3) cout << "Three of a Kind\n";
else if (pairs == 2) cout << "Two Pairs\n";
else if (pairs == 1) cout << "One Pair\n";
else cout << "High Card\n";
}
return 0;
}
T5 - Vertex Verse
Approach
Given a grid graph, process pairs of edges. For each pair, check if they form a 4-cycle with adjacent rows or columns. Use sets to store edges and check for the existence of the 4 required edges to complete a square.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, q;
cin >> n >> m >> q;
map<pair<pair<int,int>, pair<int,int>>, int> edges;
vector<int> score(2, 0);
for (int i = 0; i < 2 * q; ++i) {
int a, b, c, d;
cin >> a >> b >> c >> d;
pair<int,int> p1 = {a, b}, p2 = {c, d};
if (p1 > p2) swap(p1, p2);
edges[{p1, p2}]++;
if (edges[{p1, p2}] == 1) {
if (a == c) { // Same row
pair<int,int> p3 = {a+1, b}, p4 = {c+1, d};
if (p1 < p3 && p2 < p4 && edges.count({p1, p3}) && edges.count({p1, p2}) && edges.count({p3, p4}) && edges.count({p2, p4}))
score[i%2]++;
p3 = {a-1, b}; p4 = {c-1, d};
if (p3 < p1 && p4 < p2 && edges.count({p3, p1}) && edges.count({p3, p4}) && edges.count({p1, p2}) && edges.count({p4, p2}))
score[i%2]++;
} else { // Same column
pair<int,int> p3 = {a, b+1}, p4 = {c, d+1};
if (p1 < p3 && p2 < p4 && edges.count({p1, p3}) && edges.count({p1, p2}) && edges.count({p3, p4}) && edges.count({p2, p4}))
score[i%2]++;
p3 = {a, b-1}; p4 = {c, d-1};
if (p3 < p1 && p4 < p2 && edges.count({p3, p1}) && edges.count({p3, p4}) && edges.count({p1, p2}) && edges.count({p4, p2}))
score[i%2]++;
}
}
}
cout << score[0] << " " << score[1] << endl;
return 0;
}
T6 - Government Building Location
Approach
Method 1: Simulated Annealing Randomly search for the point minimizing the weighted Menhattan distance sum.
#include <bits/stdc++.h>
using namespace std;
struct Loc { double x, y; };
int n; double w[10005], ansx, ansy, bestDist = 1e18;
Loc pts[10005];
double calcDist(double x, double y) {
double sum = 0;
for (int i = 0; i < n; ++i)
sum += (abs(x - pts[i].x) + abs(y - pts[i].y)) * w[i];
return sum;
}
void simulate() {
double temp = 3000, delta = 0.999;
while (temp > 1e-20) {
double nx = ansx + (rand()*2.0 - RAND_MAX) * temp;
double ny = ansy + (rand()*2.0 - RAND_MAX) * temp;
double nd = calcDist(nx, ny);
if (nd < bestDist) { ansx = nx; ansy = ny; bestDist = nd; }
else if (exp(-(nd-bestDist)/temp) * RAND_MAX > rand()) {
ansx = nx; ansy = ny;
}
temp *= delta;
}
}
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> w[i];
for (int i = 0; i < n; ++i) { cin >> pts[i].x >> pts[i].y; ansx += pts[i].x; ansy += pts[i].y; }
ansx /= n; ansy /= n; bestDist = calcDist(ansx, ansy);
simulate();
printf("%.5lf\n", bestDist);
return 0;
}
Method 2: Weighted Median Since Manhattan distance is separable, find the weighted median for X and Y coordinates independently.
#include <bits/stdc++.h>
using namespace std;
double findMedian(vector<double>& a, vector<int>& w) {
double lo = -1e3, hi = 1e3;
while (hi - lo > 1e-6) {
double mid = (lo + hi) / 2;
auto f = [&](double x) {
double s = 0; for (int i = 0; i < a.size(); ++i) s += fabs(x - a[i]) * w[i];
return s;
};
if (f(mid - 1e-6) > f(mid) && f(mid) > f(mid + 1e-6)) lo = mid;
else hi = mid;
}
return lo;
}
int main() {
int n; cin >> n;
vector<int> w(n);
for (int& x : w) cin >> x;
vector<double> xs(n), ys(n);
for (int i = 0; i < n; ++i) cin >> xs[i] >> ys[i];
double mx = findMedian(xs, w), my = findMedian(ys, w);
double res = 0;
for (int i = 0; i < n; ++i) res += (fabs(mx - xs[i]) + fabs(my - ys[i])) * w[i];
cout << fixed << setprecision(6) << res << '\n';
return 0;
}
T7 - Turtle Farm
Approach
Use Bitmask Dynamic Programming. dp[i][mask] = number of ways to place turtles up to row i with row i configuration mask. Precompute valid row masks (no adjacent 1s and fits terrain). Transition: dp[i][curr] += dp[i-1][prev] if curr and prev don't overlap.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int main() {
int n, m; cin >> n >> m;
vector<int> terrain(n+1, 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
int cell; cin >> cell;
terrain[i] = (terrain[i] << 1) | (cell == 0);
}
vector<int> valid;
for (int msk = 0; msk < (1<<m); ++msk)
if (!((msk << 1) & msk) && !((msk >> 1) & msk))
valid.push_back(msk);
vector<vector<int>> dp(n+1, vector<int>(1<<m, 0));
dp[0][0] = 1;
for (int i = 1; i <= n; ++i) {
for (int cur : valid) {
if (cur & terrain[i]) continue;
for (int prev : valid) {
if (prev & terrain[i-1]) continue;
if (cur & prev) continue;
dp[i][cur] = (dp[i][cur] + dp[i-1][prev]) % MOD;
}
}
}
int ans = 0;
for (int msk : valid) ans = (ans + dp[n][msk]) % MOD;
cout << ans - 1 << endl; // Exclude empty case
return 0;
}
Python Implementation
MOD = 10**9 + 7
n, m = map(int, input().split())
terrain = [0] * (n + 1)
for i in range(1, n + 1):
row = list(map(int, input().split()))
for val in row:
terrain[i] = (terrain[i] << 1) | (0 if val else 1)
valid = []
for msk in range(1 << m):
if not ((msk << 1) & msk) and not ((msk >> 1) & msk):
valid.append(msk)
dp = [[0] * (1 << m) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
for cur in valid:
if cur & terrain[i]: continue
for prev in valid:
if prev & terrain[i-1]: continue
if cur & prev: continue
dp[i][cur] = (dp[i][cur] + dp[i-1][prev]) % MOD
ans = 0
for msk in valid:
ans = (ans + dp[n][msk]) % MOD
print(ans - 1)
T8 - Data Center Power Usage
Approach
Use a Segment Tree to maintain three values for each interval: sum (S1), square sum (S2), and cube sum (S3). When addding a value v to an interval, update using:
- New S1 = Old S1 + len * v
- New S2 = Old S2 + 2vOld S1 + lenvv
- New S3 = Old S3 + 3vOld S2 + 3vvOld S1 + lenvvv
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, N = 1e5+5;
#define lc (id<<1)
#define rc (id<<1|1)
struct Node { long long s1, s2, s3, lazy; } tree[N<<2];
void merge(int id) {
tree[id].s1 = (tree[lc].s1 + tree[rc].s1) % MOD;
tree[id].s2 = (tree[lc].s2 + tree[rc].s2) % MOD;
tree[id].s3 = (tree[lc].s3 + tree[rc].s3) % MOD;
}
void apply(int id, int l, int r, int v) {
int len = r - l + 1;
long long vl = v % MOD;
tree[id].s3 = (tree[id].s3 + 3*vl*tree[id].s2 % MOD + 3*vl*vl%MOD*tree[id].s1 % MOD + len*vl%MOD*vl%MOD*vl % MOD) % MOD;
tree[id].s2 = (tree[id].s2 + 2*vl*tree[id].s1 % MOD + len*vl%MOD*vl % MOD) % MOD;
tree[id].s1 = (tree[id].s1 + len*vl % MOD) % MOD;
tree[id].lazy = (tree[id].lazy + vl) % MOD;
}
void push(int id, int l, int r) {
if (tree[id].lazy) {
int mid = (l+r)>>1;
apply(lc, l, mid, tree[id].lazy);
apply(rc, mid+1, r, tree[id].lazy);
tree[id].lazy = 0;
}
}
void build(int id, int l, int r) {
if (l == r) {
int x; cin >> x;
x %= MOD;
tree[id].s1 = x;
tree[id].s2 = x*x % MOD;
tree[id].s3 = x*x%MOD*x % MOD;
return;
}
int mid = (l+r)>>1;
build(lc, l, mid); build(rc, mid+1, r);
merge(id);
}
void update(int id, int l, int r, int ul, int ur, int v) {
if (ul <= l && r <= ur) { apply(id, l, r, v); return; }
push(id, l, r);
int mid = (l+r)>>1;
if (ul <= mid) update(lc, l, mid, ul, ur, v);
if (ur > mid) update(rc, mid+1, r, ul, ur, v);
merge(id);
}
long long query(int id, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[id].s3;
push(id, l, r);
int mid = (l+r)>>1; long long res = 0;
if (ql <= mid) res = (res + query(lc, l, mid, ql, qr)) % MOD;
if (qr > mid) res = (res + query(rc, mid+1, r, ql, qr)) % MOD;
return res;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m; cin >> n >> m;
build(1, 1, n);
while (m--) {
int op, x, y, v;
cin >> op >> x >> y;
if (op == 1) { cin >> v; update(1, 1, n, x, y, v); }
else cout << (query(1, 1, n, x, y) + MOD) % MOD << '\n';
}
return 0;
}