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.
Don’t simulate the grid. The coordinates go up to , so drawing the blob is a fast ticket to TLE city.
Think of each operation as choosing one move from a set. A 4 operation lets you add . An 8 operation lets you add any with .
The order of the operations does not matter. You are only adding possible movement vectors, and vector addition commutes. So only the number of 4s and 8s matters.
If there are operations of type 8, they can cover any point inside the square . After that, the operations of type 4 can cover Manhattan distance at most .
For target , take absolute values. The part not already covered by the 8 square is . The answer is YES iff this is at most the number of 4 operations.
Let be the number of 4 operations and be the number of 8 operations.
The key point: the order of the string is irrelevant. That feels suspicious at first, but it is exactly what the operation does.
Each expansion operation says: from every black cell, add some neighboring cells. Since black cells never become white, after all operations a cell is black iff you can start at and, during each operation, either stay still or move in one of the allowed directions.
For a 4 operation, the allowed movement is:
So one 4 operation increases reachable Manhattan distance by at most .
For an 8 operation, the allowed movement is any:
So one 8 operation can move one step independently in both coordinates.
Because the final position is just the sum of all chosen movement vectors, the order of those vectors does not matter. Addition does not care whether the string says 4884 or 8844; same ingredients, same soup.
Shape after the 8 operations
With 8 operations, you can reach exactly every cell satisfying:
That is a square centered at the origin.
Then use the 4 operations
With 4 operations, you can move Manhattan distance at most from that square.
So for a target , first take absolute values because the whole process is symmetric:
The 8 operations can already cover up to in each coordinate. Anything beyond that must be paid for using 4 operations.
The leftover distance is:
Why sum them? Because after escaping the square, 4 moves are cardinal moves, so fixing extra and extra distance costs Manhattan distance.
Therefore the target is black iff:
That is the entire problem. Count characters, plug into formula, print the answer. No grid, no BFS, no nonsense.
Complexity
For each test case, we scan the string once.
Across all test cases, this is , which fits easily.
#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;
ll x, y;
cin >> n >> x >> y;
string s;
cin >> s;
ll four = 0, eight = 0;
for (char c : s) {
if (c == '4') four++;
else eight++;
}
x = llabs(x);
y = llabs(y);
ll need = max(0LL, x - eight) + max(0LL, y - eight);
cout << (need <= four ? "YES" : "NO") << '\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;
ll x, y;
cin >> n >> x >> y;
string s;
cin >> s;
ll four = 0, eight = 0;
for (char c : s) {
if (c == '4') four++;
else eight++;
}
x = llabs(x);
y = llabs(y);
ll need = max(0LL, x - eight) + max(0LL, y - eight);
cout << (need <= four ? "YES" : "NO") << '\n';
}
return 0;
}