Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Ignore all walls except the closest wall to Hamid on the left and the closest wall on the right. Anything farther away cannot be touched before the closer one is destroyed.
Hamid always has a boring but powerful fallback: pick one direction forever. Mani can slow that to one cell per day, so escaping left takes at most days and escaping right takes at most days.
If Mani builds on Hamid's left on the first day, Hamid can still choose right. Then the first wall he can hit on the right is the original closest right wall , so that route takes at most days total.
Similarly, if Mani builds on Hamid's right first, Hamid can still choose left, hit the closest left wall , and then escape left in at most days total.
So Mani chooses which side to block first. The answer is
where if there is no wall left of , and if there is no wall right of .
Let be the closest wall strictly to the left of Hamid, and be the closest wall strictly to the right.
Use sentinels:
These two walls are the only initial walls that matter. Hamid can only move to the nearest wall in his chosen direction, so deeper walls are stuck waiting in line like everyone else.
Two basic escape routes
Hamid can always force progress by repeatedly choosing the same direction.
If he keeps choosing left, then each non-escape day he moves at least one cell left. Mani can make this as annoying as possible by putting a wall immediately to the left whenever possible, but that still only delays Hamid to exactly one cell per day. So escaping left takes at most days.
Similarly, escaping right takes at most days.
Now look at the first day, because Mani gets exactly one new wall before Hamid moves.
Case 1: Mani blocks the left side
Suppose Mani builds a wall somewhere to Hamid's left. Best for Mani is effectively making the left move slow, so Hamid's left route costs at most days.
But Hamid can instead go right. The closest original wall to the right is at . If , there is no wall and Hamid escapes immediately, which is day. Otherwise, he destroys the wall at on day , lands there, and then can keep going right. From position , escaping right takes at most more days, so this route costs
Therefore, if Mani blocks left, Hamid can guarantee
days.
Case 2: Mani blocks the right side
Symmetric idea. If Mani blocks right, Hamid's right route costs at most days.
Or Hamid can go left, destroy the closest original left wall at , and then continue escaping left. If , that means no wall existed and he escapes immediately, counted as . Otherwise the total is
So if Mani blocks right, Hamid can guarantee
Mani chooses the less bad option
Mani wants the answer as large as possible, so he chooses whether to block left or right first. That gives
That is the whole game. No DP, no simulation, no cursed minimax tree. Just nearest walls and two greedy choices.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n, x;
string s;
cin >> n >> x >> s;
int l = 0, r = n + 1;
for (int i = x - 2; i >= 0; --i) {
if (s[i] == '#') {
l = i + 1;
break;
}
}
for (int i = x; i < n; ++i) {
if (s[i] == '#') {
r = i + 1;
break;
}
}
int blockLeft = min(x, n - r + 2);
int blockRight = min(l + 1, n - x + 1);
cout << max(blockLeft, blockRight) << '\n';
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
int main() {
setIO();
int t;
cin >> t;
while (t--) {
int n, x;
string s;
cin >> n >> x >> s;
int l = 0, r = n + 1;
for (int i = x - 2; i >= 0; --i) {
if (s[i] == '#') {
l = i + 1;
break;
}
}
for (int i = x; i < n; ++i) {
if (s[i] == '#') {
r = i + 1;
break;
}
}
int blockLeft = min(x, n - r + 2);
int blockRight = min(l + 1, n - x + 1);
cout << max(blockLeft, blockRight) << '\n';
}
return 0;
}