Overview

On a triangular board, given a starting position and a fixed number of operations, we need to find the maximum value of \(f\) (the maximum digit sum of any number from 0 up to that cell’s value) across all reachable cells.

Analysis

Identifying Reachable Cells

When the starting cell is \((L, P)\) (the \(P\)-th cell from the left on row \(L\)) and the number of operations is \(T\), we consider the reachable cells.

• To reach row \(r\), at least \(r - L\) downward moves are required (the rest are consumed by “staying”).
• Therefore, the reachable rows are \(L \leq r \leq \min(N, L + T)\).
• When reaching row \(r\), depending on the choice between “directly below” and “diagonally below-right” among the \(r - L\) downward moves, the column ranges from \(P\) to \(P + (r - L)\) (however, since row \(r\) has only \(r\) columns, the upper limit is \(\min(P + (r-L),\ r)\)).

In other words, the reachable columns at each row \(r\) form a contiguous interval \([P,\ \min(P + (r-L),\ r)]\).

Computing \(f(V)\)

To compute \(f(V) = \max_{0 \leq Y \leq V} S(Y)\), for each digit \(i\) in the decimal representation of \(V\), we compare the digit sum of “the number obtained by decreasing that digit by 1 and setting all subsequent digits to 9” as a candidate. For example, when \(V = 523\): - Position 0: \((5-1) + 9 \times 2 = 22\) (i.e., 499) - Position 1: \(5 + (2-1) + 9 \times 1 = 14\) (i.e., 519) - As is: \(5 + 2 + 3 = 10\) (i.e., 523)

The maximum is 22, so \(f(523) = 22\).

Speeding Up Range Maximum Queries

Since we need to find the maximum over a contiguous interval for each row in each query, we build a sparse table for each row to obtain the range maximum in \(O(1)\).

Algorithm

1. Preprocessing: Compute \(f(A_{i,p})\) for all cells \((i, p)\).
2. Sparse Table Construction: Build a sparse table for each row to answer range maximum queries on \(f\) values.
3. Query Processing: For each query \((L, P, T)\):
   • If \(P > L\), output NA.
   • Otherwise, loop over rows \(r = L, L+1, \ldots, \min(N, L+T)\), obtain the maximum \(f\) value in the reachable column interval at each row using the sparse table in \(O(1)\), and output the overall maximum.

Complexity

• Time complexity: Preprocessing \(O(N^2 \log N)\), all queries \(O(NQ)\) (since \(NQ \leq 10^7\) by the constraints)
• Space complexity: \(O(N^2 \log N)\) (for the sparse table)

Implementation Notes

• Computing \(f(V)\): Scan each digit and compare the digit sums of candidates formed by “decreasing that digit by 1 and setting all remaining digits to 9” with “the original number itself”. Digits with \(d = 0\) cannot be decreased, so they are skipped.

• 0-indexed and 1-indexed conversion: The problem statement is 1-indexed, but the internal code is 0-indexed, so we convert by using P-1.

• When \(T\) is very large: \(L + T\) may exceed \(N\), but this is handled without issues by clamping with min(N, L+T).

• __lg(len): A GCC built-in function that efficiently computes \(\lfloor \log_2(\text{len}) \rfloor\), used in sparse table queries.

  Source Code

#include <bits/stdc++.h>
using namespace std;

int compute_f(long long V) {
    if (V <= 0) return 0;
    string s = to_string(V);
    int n = s.size();
    int best = 0;
    int prefix_sum = 0;
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d > 0) {
            int candidate = prefix_sum + (d - 1) + 9 * (n - 1 - i);
            best = max(best, candidate);
        }
        prefix_sum += d;
    }
    best = max(best, prefix_sum);
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<vector<int>> fval(N);
    // Sparse table for each row
    vector<vector<vector<int>>> sparse(N);
    
    for (int i = 0; i < N; i++) {
        fval[i].resize(i + 1);
        for (int p = 0; p <= i; p++) {
            long long a;
            cin >> a;
            fval[i][p] = compute_f(a);
        }
        int len = i + 1;
        int LOG = 1;
        while ((1 << LOG) <= len) LOG++;
        sparse[i].resize(LOG);
        sparse[i][0] = fval[i];
        for (int k = 1; k < LOG; k++) {
            int sz = len - (1 << k) + 1;
            if (sz <= 0) break;
            sparse[i][k].resize(sz);
            for (int j = 0; j < sz; j++) {
                sparse[i][k][j] = max(sparse[i][k-1][j], sparse[i][k-1][j + (1 << (k-1))]);
            }
        }
    }
    
    auto query_max = [&](int row, int l, int r) -> int {
        // range [l, r] inclusive, 0-indexed
        if (l > r) return 0;
        int len = r - l + 1;
        int k = __lg(len);
        return max(sparse[row][k][l], sparse[row][k][r - (1 << k) + 1]);
    };
    
    for (int q = 0; q < Q; q++) {
        int L, P;
        long long T;
        cin >> L >> P >> T;
        if (P > L) {
            cout << "NA\n";
            continue;
        }
        long long max_row_ll = min((long long)N, (long long)L + T);
        int max_row = (int)max_row_ll;
        int ans = 0;
        for (int r = L; r <= max_row; r++) {
            int cs = P - 1; // 0-indexed left
            int ce = P - 1 + (r - L); // 0-indexed right
            // row r (1-indexed) has r columns, 0-indexed: 0 to r-1
            if (ce >= r) ce = r - 1;
            int row_idx = r - 1;
            int rm = query_max(row_idx, cs, ce);
            ans = max(ans, rm);
        }
        cout << ans << "\n";
    }
    
    return 0;
}

---

This editorial was generated by claude4.6opus-thinking.