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.
Forget the queries for a second. Let be the largest target, and build cnt[v] for every expression value . Then every query is just an array lookup.
Every non-single-cell expression is exactly: choose a digit cell, choose one of 8 directions, then walk forward. Count one-cell digit expressions separately once, because a cell by itself has no direction.
Do not parse substrings from scratch. While walking, maintain sum for completed + terms, prod for the current multiplication term, and factor for the current number being typed.
When a digit extends the current number, replace that number inside prod: base = prod / factor, factor = factor * 10 + d, prod = base * factor. That is the whole multiplication-precedence trick.
Once a valid prefix has value bigger than , stop this ray. All numbers are positive and there is no digit 0, so extending with digits, +, or * can never decrease the value. Consecutive operators are also permanently dead, so break there too.
The problem looks like it wants a tiny expression parser for every substring. That would be pain, and worse, unnecessary pain.
The actual constraints are screaming the intended approach: the grid has at most cells, and every row/column/diagonal ray has length at most . So we can enumerate directed segments, as long as extending a segment costs instead of reparsing the whole string like a caveman with a compiler textbook.
Let be the largest queried value. We only care about expression values .
A length-at-least-2 expression is determined by:
So for every digit cell, try all 8 directions and walk forward.
Single-cell expressions are the annoying little edge case: start and end are the same cell, so there is no direction. Count each digit cell exactly once before doing the 8-direction walks. If you count it inside every direction, you overcount by 8, which is extremely cursed and also wrong.
For a valid expression prefix ending in a digit, store:
sum: the total of multiplication terms already closed by +,prod: the current multiplication term,factor: the current number at the end of the expression.Then the current expression value is always:
sum + prod
This handles normal precedence because multiplication stays inside prod, and addition moves the old prod into sum.
Now process the next character.
If it is a digit d and the previous character was also a digit, we are extending the current number. Example: 12*3 becomes 12*34. The old factor was 3; the new factor is 34. Since prod contains the old factor, replace it:
base = prod / factor
factor = factor * 10 + d
prod = base * factor
The division is exact because factor is literally one factor of prod.
If it is a digit after +, start a new multiplication term:
prod = d, factor = d
If it is a digit after *, multiply into the current term:
prod *= d, factor = d
If it is +, the current expression must have ended in a digit. Close the current multiplication term:
sum += prod
Then wait for the next number.
If it is *, again the previous character must be a digit. Keep prod as-is and wait for the next factor.
If we ever see two operators in a row, break. No future characters can repair something like 2**5; the substring is already toast.
All digits are from 1 to 9. There are no zeroes. This matters a lot.
Once a valid prefix has value bigger than :
+ num increases the value,* num multiplies part of the expression by at least 1, so it never decreases.So future valid extensions cannot come back down to a queried value. Stop walking that ray immediately.
This is the key monotonicity assumption. If zero existed, this would be false because 100*0 could drop. But kindergarten gave us digits 1..9, so we take the win.
Let and .
We walk from digit cells in 8 directions, doing work per visited cell, with early stops when values exceed or syntax becomes impossible.
Time complexity: as a loose bound.
Memory complexity: for the answer counts.
That fits comfortably: the constants are tiny, and queries become instant lookups.
#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 n, m, q;
cin >> n >> m >> q;
vector<string> g(n);
for (string &row : g) cin >> row;
vector<int> query(q);
for (int &x : query) cin >> x;
int limit = *max_element(query.begin(), query.end());
vector<ll> cnt(limit + 1, 0);
auto isDigit = [](char c) {
return '1' <= c && c <= '9';
};
// Single-cell expressions are not directional.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (isDigit(g[i][j])) {
int v = g[i][j] - '0';
if (v <= limit) cnt[v]++;
}
}
}
const int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
for (int si = 0; si < n; si++) {
for (int sj = 0; sj < m; sj++) {
if (!isDigit(g[si][sj])) continue;
int first = g[si][sj] - '0';
if (first > limit) continue;
for (int dir = 0; dir < 8; dir++) {
ll sum = 0;
ll prod = first;
ll factor = first;
bool lastDigit = true;
char pending = 0;
int x = si + dx[dir];
int y = sj + dy[dir];
while (0 <= x && x < n && 0 <= y && y < m) {
char c = g[x][y];
if (isDigit(c)) {
int d = c - '0';
if (lastDigit) {
ll newFactor = factor * 10 + d;
ll base = prod / factor;
prod = base * newFactor;
factor = newFactor;
} else {
factor = d;
if (pending == '+') prod = d;
else prod *= d;
}
lastDigit = true;
ll value = sum + prod;
if (value > limit) break;
cnt[(int)value]++;
} else {
if (!lastDigit) break;
if (c == '+') {
sum += prod;
if (sum > limit) break;
prod = 0;
factor = 0;
pending = '+';
} else {
pending = '*';
factor = 0;
}
lastDigit = false;
}
x += dx[dir];
y += dy[dir];
}
}
}
}
for (int x : query) {
cout << cnt[x] << '\n';
}
}#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 n, m, q;
cin >> n >> m >> q;
vector<string> g(n);
for (string &row : g) cin >> row;
vector<int> query(q);
for (int &x : query) cin >> x;
int limit = *max_element(query.begin(), query.end());
vector<ll> cnt(limit + 1, 0);
auto isDigit = [](char c) {
return '1' <= c && c <= '9';
};
// Single-cell expressions are not directional.
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (isDigit(g[i][j])) {
int v = g[i][j] - '0';
if (v <= limit) cnt[v]++;
}
}
}
const int dx[8] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dy[8] = {0, 0, 1, -1, 1, -1, -1, 1};
for (int si = 0; si < n; si++) {
for (int sj = 0; sj < m; sj++) {
if (!isDigit(g[si][sj])) continue;
int first = g[si][sj] - '0';
if (first > limit) continue;
for (int dir = 0; dir < 8; dir++) {
ll sum = 0;
ll prod = first;
ll factor = first;
bool lastDigit = true;
char pending = 0;
int x = si + dx[dir];
int y = sj + dy[dir];
while (0 <= x && x < n && 0 <= y && y < m) {
char c = g[x][y];
if (isDigit(c)) {
int d = c - '0';
if (lastDigit) {
ll newFactor = factor * 10 + d;
ll base = prod / factor;
prod = base * newFactor;
factor = newFactor;
} else {
factor = d;
if (pending == '+') prod = d;
else prod *= d;
}
lastDigit = true;
ll value = sum + prod;
if (value > limit) break;
cnt[(int)value]++;
} else {
if (!lastDigit) break;
if (c == '+') {
sum += prod;
if (sum > limit) break;
prod = 0;
factor = 0;
pending = '+';
} else {
pending = '*';
factor = 0;
}
lastDigit = false;
}
x += dx[dir];
y += dy[dir];
}
}
}
}
for (int x : query) {
cout << cnt[x] << '\n';
}
}