C. Chaotic Construction
When the circular track is unwrapped into a linear sequence from 1 to 2n, placing a barrier at position D corresponds to having barriers at both D and D+n on this line. For any query (x, y), we check whether any barrier falls between x and y, or between x and y+n. We maintain a booolean array to track which positions are currently blocked, and use an ordered set to efficiently query for barriers in specific ranges. Initially, no barriers exist so all queries are answerable. For each query, we perform two range checks: one from x to y, and another from x to y+n. If both ranges contain a barrier, the movement becomes impossible in both directions.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
unordered_map<int, int> blocked;
cin >> n >> q;
set<i64> barrier;
barrier.insert(0);
for (int i = 0; i < q; i++) {
char op;
int pos1, pos2;
cin >> op >> pos1;
if (op == '?') {
cin >> pos2;
if (pos1 > pos2) swap(pos1, pos2);
if (blocked[pos1] || blocked[pos2]) {
cout << "impossible\n";
continue;
}
int obstructionCount = 0;
auto it1 = barrier.lower_bound(pos1);
auto it2 = barrier.lower_bound(pos2);
if (it1 != it2) obstructionCount++;
auto it3 = barrier.lower_bound(pos1 + n);
if (it3 != it2) obstructionCount++;
cout << (obstructionCount > 1 ? "impossible\n" : "possible\n");
} else {
if (op == '-') {
blocked[pos1] = 1;
barrier.insert(pos1);
barrier.insert(pos1 + n);
} else {
blocked[pos1] = 0;
barrier.erase(pos1);
barrier.erase(pos1 + n);
}
}
}
return 0;
}
D. Diabolic Doefenshmirtz
Since 1e12 is less than 2^42, we can employ exponential search (doubling) to locate the cycle length. Starting from position 1, we query the system with positions doubling each time: 1, 2, 4, 8, ..., up to 2^41. We maintain the length of the previous response. When the current response length becomes less than or equal to the previous response length, we know we have completed at least one full cycle. At this point, the position now minus the current response length x gives us the circumference of the cycle.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 currentPos = 1;
i64 prevLength = 0;
for (int step = 1; step <= 42; step++) {
cout << "? " << currentPos << endl;
i64 responseLen;
cin >> responseLen;
if (responseLen <= prevLength) {
cout << "! " << currentPos - responseLen << endl;
break;
}
prevLength = responseLen;
currentPos *= 2;
}
return 0;
}
E. Enjoyable Entree
This is a pattern recognition problem. When examining the results for small values of n and observing the convergence behavior, we discover that for n greater than 30, both ratios stabilize at approximately 33.333333 and 66.666667. For small values, we need to compute directly, but for larger values, we can output the converged constants directly. The pattern emerges from a recurrence relation where each value depends on the previous two values in a specific weighted manner.
#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;
if (n == 1) {
cout << "100 0\n";
} else if (n == 2) {
cout << "0 100\n";
} else {
if (n > 30) {
cout << "33.333333 66.666667\n";
} else {
double firstTerm = 50, secondTerm = 50, currentTerm;
for (int idx = 5; idx <= n; idx++) {
currentTerm = firstTerm / 2 + secondTerm / 2;
firstTerm = secondTerm;
secondTerm = currentTerm;
}
if (n == 3)
cout << "50 50\n";
else if (n == 4)
cout << "25 75\n";
else
printf("%.6lf %.6lf\n", secondTerm, 100 - secondTerm);
}
}
return 0;
}
I. Improving IT
This dynamic programming problem tracks monthly earnings from CPU trading. Let dp[i] represent the maximum profit achievable at the beginning of month i. Initially, dp[1] equals 0 since we haven't purchased anything yet. Each month, we subtract the purchase cost a from dp[i]. For each possible holding period j (where j ranges from 1 to the minimum of m and remaining months), we consider selling the CPU at price b, updating dp[i+j] with the maximum value between its current state and dp[i] + b. The final answer is the negative of dp[n+1], representing the minimum cost needed to complete the sequence.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int totalMonths, maxHold;
cin >> totalMonths >> maxHold;
vector<i64> dp(totalMonths + 2, LLONG_MIN);
dp[1] = 0;
for (int month = 1; month <= totalMonths; month++) {
int purchaseCost;
cin >> purchaseCost;
dp[month] -= purchaseCost;
int upperBound = min(maxHold, totalMonths - month + 1);
for (int offset = 1; offset <= upperBound; offset++) {
int sellPrice;
cin >> sellPrice;
dp[month + offset] = max(dp[month + offset], dp[month] + sellPrice);
}
}
cout << -dp[totalMonths + 1] << '\n';
return 0;
}
K. K.O. Kids
This simulation problem involves matching children's stepping patterns with expected directions. We maintain a boolean flag indicating whether the next step should be with the left foot (true) or right foot (false). When the flag is true and a child doesn't step left, or when the flag is false and a child doesn't step right, that child is eliminated. Otherwise, we flip the flag to alternate the next expected foot. The answer is the maximum of zero and the remaining count after processing all input.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int children, threshold;
string sequence;
cin >> children >> threshold >> sequence;
bool nextLeft = true;
int remaining = threshold;
for (int i = 0; i < children; i++) {
if (nextLeft && sequence[i] != 'L')
remaining--;
else if (!nextLeft && sequence[i] != 'R')
remaining--;
else
nextLeft = !nextLeft;
}
cout << max(0, remaining) << '\n';
return 0;
}
L. Lots of Land
First, we check if the total area of the rectangle can be evenly divided by n. If not, it's impossible to partition into equal-area smaller rectangles. Otherwise, let k equal the area of each small rectangle (total area divided by n). To find appropriate dimensions, we compute the greatest common divisor between k and the length L, yielding the smaller dimension. The other dimension becomes k divided by this GCD. We then fill the grid by iterating through rows and columns, assigning labels that increment whenever we cross a boundary between small rectangles.
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rectHeight, rectWidth, partitionCount;
cin >> rectHeight >> rectWidth >> partitionCount;
vector<string> grid(rectHeight, string(rectWidth, 'A'));
if ((rectHeight * rectWidth) % partitionCount != 0) {
cout << "IMPOSSIBLE\n";
} else {
int cellArea = rectHeight * rectWidth / partitionCount;
char currentLabel = 'A';
int dim1 = gcd(cellArea, rectHeight);
int dim2 = cellArea / dim1;
for (int row = 0; row < rectHeight; row++) {
int segmentIndex = 0;
for (int col = 0; col < rectWidth; col++) {
if (col && col % dim2 == 0) segmentIndex++;
grid[row][col] = currentLabel + segmentIndex;
}
if ((row + 1) % dim1 == 0)
currentLabel = currentLabel + segmentIndex + 1;
}
for (const auto& line : grid)
cout << line << '\n';
}
return 0;
}