2024 Nowcoder Winter Algorithm Training Camp 4
A - Lemon Soda
Check if the first value is at least k times the second value.
Complexity: O(1)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int x, y, factor;
cin >> x >> y >> factor;
cout << (x >= factor * y ? "good" : "bad") << '\n';
return 0;
}
B - Left-Right Combat
When the number of even piles is odd, the second player wins.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int total, evenCount = 0;
cin >> total;
vector<int> piles(total);
for (auto &p : piles) {
cin >> p;
if (p % 2 == 0) evenCount++;
}
cout << (evenCount % 2 == 1 ? "gui" : "sweet") << '\n';
return 0;
}
C - Hibernation
With small constraints, direct simulation works.
Complexity: O(n³)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows, cols, startX, startY;
cin >> rows >> cols >> startX >> startY;
vector<string> grid(rows);
for (auto &row : grid) cin >> row;
int opsRow, opsCol;
cin >> opsRow >> opsCol;
vector<pair<int, int>> operations(opsCol);
for (auto &[op, idx] : operations) {
cin >> op >> idx;
idx--;
}
for (int i = 0; i < opsRow; i++) {
for (int j = 0; j < opsCol; j++) {
char buffer;
auto [type, col] = operations[j];
if (type == 1) {
buffer = grid[col][cols - 1];
for (int k = cols - 2; k >= 0; k--)
grid[col][k + 1] = grid[col][k];
grid[col][0] = buffer;
} else {
buffer = grid[rows - 1][col];
for (int k = rows - 2; k >= 0; k--)
grid[k + 1][col] = grid[k][col];
grid[0][col] = buffer;
}
}
}
cout << grid[startX - 1][startY - 1] << '\n';
return 0;
}
D - Conservation
First compute the sum, then count divisors from 1 to average. Special case for single element.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 len, totalSum = 0;
cin >> len;
vector<int> arr(len);
for (auto &v : arr) {
cin >> v;
totalSum += v;
}
if (len == 1) {
cout << 1 << '\n';
return 0;
}
int divisorCount = 0;
for (int i = 1; i <= totalSum / len; i++)
if (totalSum % i == 0) divisorCount++;
cout << divisorCount << '\n';
return 0;
}
E - Beautiful Array
Traverse left to right, selecting valid intervals and updating prefix sum positions.
Complexity: O(n log n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, mod;
cin >> n >> mod;
int sum = 0, lastPos = -1, result = 0;
map<int, int> seen;
seen[0] = -1;
for (int i = 0; i < n; i++) {
int val;
cin >> val;
sum = (sum + val) % mod;
if (seen.count(sum) && seen[sum] >= lastPos) {
result++;
lastPos = i;
}
seen[sum] = i;
}
cout << result << '\n';
return 0;
}
G - Counting Triangles (Easy)
Precompute rightward continuation counts for each asterisk, then check downward triangles.
Complexity: O(n³)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows, cols;
cin >> rows >> cols;
vector<string> grid(rows);
for (auto &row : grid) cin >> row;
vector<vector<int>> right(rows, vector<int>(cols));
for (int i = 0; i < rows; i++) {
for (int j = cols - 1; j >= 0; j--) {
if (grid[i][j] == '*') {
right[i][j] = (j == cols - 1) ? 1 : right[i][j + 1] + 1;
}
}
}
int triangles = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '*') {
int left = j - 1, right2 = j + 1, height = i + 1;
while (height < rows && left >= 0 && right2 < cols &&
grid[height][left] == grid[height][right2] &&
grid[height][left] == '*') {
int width = right2 - left + 1;
if (right[height][left] >= width) triangles++;
left--, right2++, height++;
}
}
}
}
cout << triangles << '\n';
return 0;
}
2024 Nowcoder Winter Algoirthm Training Camp 5
A - Mutsumi's Primes and Composites
1 is neither prime nor composite.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int count, ones = 0;
cin >> count;
vector<int> arr(count);
for (auto &v : arr) {
cin >> v;
if (v == 1) ones++;
}
cout << count - ones << '\n';
return 0;
}
C - Anon's Contraband
Insert zeros between consecutive elements.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len;
cin >> len;
vector<i64> data(len + 2);
for (int i = 1; i <= len; i++) cin >> data[i];
data[0] = data[1], data[len + 1] = data[len];
i64 result = 0;
for (int i = 0; i <= len; i++) {
i64 zeros = min(data[i], data[i + 1]) - 1;
result += zeros;
data[i + 1] -= zeros;
}
cout << result << '\n';
return 0;
}
G / H - Sakiko's Permutation Construction (Easy/Hard)
Observe the pattern: reverse output with in the range from current position to its next prime.
Complexity: O(2n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
vector<bool> sieve(int limit) {
vector<int> phi(limit + 1), primes;
vector<bool> isPrime(limit + 1, true);
isPrime[1] = false, phi[1] = 1;
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
primes.push_back(i);
phi[i] = i - 1;
}
for (int p = 0; p < (int)primes.size() && i * primes[p] <= limit; p++) {
isPrime[i * primes[p]] = false;
if (i % primes[p]) phi[i * primes[p]] = phi[i] * (primes[p] - 1);
else {
phi[i * primes[p]] = phi[i] * primes[p];
break;
}
}
}
return isPrime;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> result(n);
auto primes = sieve(2 * n);
for (int i = n; i > 0; i--) {
int next = i + 1;
while (!primes[next]) next++;
for (int j = next - i - 1; j < i; j++)
result[j] = next - (j + 1);
i = next - i;
}
for (int i = 0; i < n; i++)
cout << result[i] << " \n"[i == n - 1];
return 0;
}
I - Rikki's Shortest Path
Handle same and opposite directions with visibility checks.
Complexity: O(1)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 target, start, vision;
cin >> target >> start >> vision;
if (start * target >= 0) {
start = abs(start), target = abs(target);
if (start <= target) cout << target << '\n';
else cout << target + 2 * (start - target) << '\n';
} else {
start = abs(start), target = abs(target);
if (start <= vision) cout << 2 * start + target << '\n';
else cout << target + 2 * (start + target) << '\n';
}
return 0;
}
L - Anon's Stars
Find unique pair (i, j) where i - j equals target.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, diff, count = 0, first = 0, second = 0;
cin >> n >> diff;
for (int i = 0; i <= n; i++) {
int j = n - i;
if (i - j == diff) {
first = i, second = j;
count++;
}
}
if (count == 1) cout << first << ' ' << second << '\n';
else cout << "-1\n";
return 0;
}
M - Mutsumi's Permutation Connectivity
Special cases for n=1,2. Delete one if adjacent or crossing match exists, otherwise delete two.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int len;
cin >> len;
vector<int> a(len), b(len);
for (int i = 0; i < len; i++) cin >> a[i];
for (int i = 0; i < len; i++) cin >> b[i];
if (len == 1 || (len == 2 && a[0] == b[0])) {
cout << "-1\n";
return;
}
for (int i = 0; i + 1 < len; i++) {
if ((i && a[i] == b[i]) || a[i] == b[i + 1] || b[i] == a[i + 1]) {
cout << "1\n";
return;
}
}
cout << "2\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int cases;
cin >> cases;
while (cases--) solve();
return 0;
}
2024 Nowcoder Winter Algorithm Training Camp 6
A - End of Universe
Sieve primes up to 100, then brute force triple product.
Complexity: O(1)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int L, R;
cin >> L >> R;
auto isPrime = [](int x) {
if (x == 2) return true;
if (x < 2 || x % 2 == 0) return false;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0) return false;
return true;
};
vector<int> primes;
for (int i = 2; i <= 100; i++)
if (isPrime(i)) primes.push_back(i);
for (int i = 0; i < (int)primes.size(); i++) {
for (int j = i + 1; j < (int)primes.size(); j++) {
for (int k = j + 1; k < (int)primes.size(); k++) {
int product = primes[i] * primes[j] * primes[k];
if (product >= L && product <= R) {
cout << product << '\n';
return 0;
}
}
}
}
cout << "-1\n";
return 0;
}
B - Love and Hate
Sort array A, then find closest match for each element in B.
Complexity: O(n log n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int len;
cin >> len;
vector<i64> A(len), B(len);
for (auto &v : A) cin >> v;
for (auto &v : B) cin >> v;
sort(A.begin(), A.end());
i64 minDiff = LLONG_MAX;
int posA = 0, posB = 0;
for (int j = 0; j < len; j++) {
int target = B[j];
auto it = lower_bound(A.begin(), A.end(), target);
if (it == A.end()) it = prev(it);
int diff = abs(target - *it);
if (diff < minDiff) {
posA = it - A.begin();
minDiff = diff;
posB = j;
}
if (it != A.begin()) {
diff = abs(target - *prev(it));
if (diff < minDiff) {
posA = it - A.begin() - 1;
minDiff = diff;
posB = j;
}
}
}
swap(A[posA], A[posB]);
for (auto v : A) cout << v << ' ';
cout << '\n';
return 0;
}
C - Heart's Anatomy
There are only 45 primes under 1e9. Precompute Fibonacci combinations.
Complexity: O(1) for queries
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<i64> fib(46);
fib[0] = 0, fib[1] = 1;
set<i64> valid;
valid.insert(0), valid.insert(1);
for (int i = 2; i <= 45; i++) {
fib[i] = fib[i - 1] + fib[i - 2];
valid.insert(fib[i]);
}
map<i64, vector<i64>> cache;
for (int i = 0; i < 46; i++) {
for (int j = 0; j < 46; j++) {
for (int k = 0; k < 46; k++) {
i64 val = fib[i] + fib[j] + fib[k];
if (cache.count(val)) continue;
cache[val] = {fib[i], fib[j], fib[k]};
}
}
}
int queries;
cin >> queries;
while (queries--) {
i64 n;
cin >> n;
if (cache.count(n)) {
for (auto v : cache[n]) cout << v << ' ';
cout << '\n';
} else {
cout << "-1\n";
}
}
return 0;
}
D - Friendship's Strategy
Two possible endings: either side achieves comeback 3-2.
Complexity: O(1)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
double winProb;
cin >> winProb;
double result = pow(1 - winProb, 2) * pow(winProb, 3) +
pow(winProb, 2) * pow(1 - winProb, 3);
cout << fixed << setprecision(6) << result << '\n';
return 0;
}
E - Future's Prophecy
Simulate the game round by round.
Complexity: O(n)
#include <bits/stdcicio.hpp>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string pattern, sequence;
cin >> pattern >> sequence;
i64 threshold = 0;
for (int i = 2; i < pattern.size(); i++)
threshold = threshold * 10 + (pattern[i] - '0');
i64 pCount = 0, rCount = 0;
for (int i = 0; i < sequence.size(); i++) {
if (sequence[i] == 'P') pCount++;
else rCount++;
if (pCount > threshold / 2) {
cout << "yukari!\n" << i + 1 << '\n';
return 0;
} else if (rCount > threshold / 2) {
cout << "kou!\n" << i + 1 << '\n';
return 0;
}
}
cout << "to be continued.\n" << sequence.size() << '\n';
return 0;
}
F - Fate's Choice
Prime sieve combined with Union-Find. Connect each number with its prime factors.
Complexity: O(n log log n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int MAXN = 1e6 + 5;
vector<int> prime;
bool composite[MAXN];
void sieve() {
for (int i = 2; i <= MAXN; i++) {
if (!composite[i]) prime.push_back(i);
for (int j = 0; j < (int)prime.size(); j++) {
if (prime[j] * i > MAXN) break;
composite[prime[j] * i] = true;
if (i % prime[j] == 0) break;
}
}
}
vector<int> parent(MAXN);
vector<bool> exists(MAXN);
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
sieve();
int queries;
cin >> queries;
while (queries--) {
int n, maxVal = 0, ones = 0;
cin >> n;
fill(exists.begin(), exists.end(), false);
vector<int> data(n);
for (auto &v : data) {
cin >> v;
maxVal = max(maxVal, v);
exists[v] = true;
ones += (v == 1);
}
if (ones == n) {
cout << "-1 -1\n";
continue;
}
if (ones != n && ones) {
cout << ones << ' ' << n - ones << '\n';
for (int i = 1; i <= ones; i++)
cout << 1 << " \n"[i == ones];
for (int i = 0; i < n; i++)
if (data[i] != 1) cout << data[i] << ' ';
cout << '\n';
continue;
}
for (int i = 0; i <= maxVal; i++) parent[i] = i;
for (int p = 0; p < (int)prime.size(); p++) {
if (prime[p] > maxVal) break;
for (int j = 1; j * prime[p] <= maxVal; j++) {
int val = j * prime[p];
if (exists[val]) {
int fx = find(val), fy = find(prime[p]);
if (fx != fy) parent[fx] = fy;
}
}
}
map<int, bool> seen;
vector<int> group1, group2;
int groups = 0, firstGroup = 0;
for (int i = 0; i < n; i++) {
int root = find(data[i]);
if (!seen.count(root)) {
groups++;
if (!firstGroup) firstGroup = root;
seen[root] = true;
}
if (root == firstGroup) group1.push_back(data[i]);
else group2.push_back(data[i]);
}
if (groups == 1) {
cout << "-1 -1\n";
} else {
cout << group1.size() << ' ' << group2.size() << '\n';
for (auto v : group1) cout << v << ' ';
cout << '\n';
for (auto v : group2) cout << v << ' ';
cout << '\n';
}
}
return 0;
}
I - Time-Space Intersection
Prefix sum analysis tracking maximum positive and minimum negative differences.
Complexity: O(n)
#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;
vector<i64> A(n), B(m), prefA(n), prefB(m);
for (auto &v : A) cin >> v;
for (auto &v : B) cin >> v;
prefA[0] = A[0];
for (int i = 1; i < n; i++) prefA[i] = prefA[i - 1] + A[i];
i64 maxPosA = A[0], minPrefA = 0, minEleA = A[0], maxPrefA = 0, minDiffA = A[0];
for (int i = 0; i < n; i++) {
maxPosA = max(maxPosA, prefA[i] - minPrefA);
minPrefA = min(prefA[i], minPrefA);
minEleA = min(minEleA, A[i]);
minDiffA = min(minDiffA, prefA[i] - maxPrefA);
maxPrefA = max(prefA[i], maxPrefA);
}
prefB[0] = B[0];
for (int i = 1; i < m; i++) prefB[i] = prefB[i - 1] + B[i];
i64 maxPosB = B[0], minPrefB = 0, minEleB = B[0], maxPrefB = 0, minDiffB = B[0];
for (int i = 0; i < m; i++) {
maxPosB = max(maxPosB, prefB[i] - minPrefB);
minPrefB = min(prefB[i], minPrefB);
minEleB = min(minEleB, B[i]);
minDiffB = min(minDiffB, prefB[i] - maxPrefB);
maxPrefB = max(prefB[i], maxPrefB);
}
cout << max({maxPosA * maxPosB, minEleB * maxPosA, minEleA * maxPosB, minDiffA * minDiffB}) << '\n';
return 0;
}
J - Wonderful Balance
A red node with no non-red children is unsolvable. Greedy approach: asssign all weights as 1, then adjust based on subtree sums.
Complexity: O(n)
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int nodes;
string color;
cin >> nodes >> color;
vector<int> sum(nodes + 1, 1), answer(nodes + 1, 1);
vector<vector<int>> children(nodes + 1);
map<int, int> redNodes;
for (int i = 0; i < nodes; i++)
if (color[i] == 'R') redNodes[i + 1] = 1;
for (int parent, i = 2; i <= nodes; i++) {
cin >> parent;
children[parent].push_back(i);
}
for (int i = 1; i <= nodes; i++) {
bool hasNonRed = false;
for (auto child : children[i])
if (!redNodes.count(child)) {
hasNonRed = true;
break;
}
if (redNodes.count(i) && !hasNonRed) {
cout << "-1\n";
exit(0);
}
}
function<void(int)> dfs = [&](int u) {
int res = 1;
for (auto v : children[u]) {
dfs(v);
if (!redNodes.count(v)) res += sum[v];
}
if (redNodes.count(u)) {
if (res % 3 == 2) answer[u]++;
else if (res % 3 == 1) {
answer[u]++;
answer[children[u][0]]++;
}
}
sum[u] = res;
};
dfs(1);
for (int i = 1; i <= nodes; i++) cout << answer[i];
cout << '\n';
return 0;
}