logoChat01.ai

Реши на с++

Создано: 24 октября 2025 г.

Отвечено с использованием GPT-5 Thinking от Chat01

Вопрос

image.pngimage.png
image.pngimage.png

Реши на с++

Python

python
from collections import deque
def solve_comp(h, l1, r1, l2, r2):
    n=len(h)
    S=[0]
    for x in h: S.append(S[-1]+x)
    import bisect
    def calc(limit):
        nxt=[0]*(n+1)
        for i in range(n+1):
            j=bisect.bisect_right(S, S[i]+limit)-1
            if j< i: j= i
            nxt[i]=j
        return nxt
    nl1=calc(l1); nr1=calc(r1); nl2=calc(l2); nr2=calc(r2)
    INF=10**15
    dist=[[INF]*(n+1) for _ in range(3)] # 0 same,1 HL(left higher),2 HR
    dq=deque()
    dist[0][0]=0
    dq.append((0,0))
    while dq:
        s,i = dq.popleft()
        d=dist[s][i]
        if s==0:
            j=nl1[i]


(True, (True, None))

Мысль

Validating the BFS solution

The compressed BFS solution seems to match the brute force approach for small random tests, which is great! It's performing well. Now, I need to move to the C++ implementation:

  • I'll read the input values and compute the prefix sum array.
  • A helper function calcNext will return appropriate next steps.
  • Then, I’ll implement BFS using a deque to store state transitions and process the steps using the distances.

Thought for 7m 22s

Ответ

Вот корректное и быстрое решение на C++ (O(n log n)).
Идея: храним только номер «верхней» ступеньки и состояние ног: SAME (обе на одной), HIGH_L (левая выше), HIGH_R (правая выше).
Переходы:

  • SAME i → сделать шаг левой: на самую дальнюю j, где sum(i+1..j) ≤ l1 → HIGH_L j
  • SAME i → сделать шаг правой: самая дальняя j, где sum(i+1..j) ≤ r1 → HIGH_R j
  • HIGH_L i → «подтянуть» правую к левой (действие 3) → SAME i
  • HIGH_L i → шаг правой поверх левой: самая дальняя j, где sum(i+1..j) ≤ r2 → HIGH_R j
  • HIGH_R i симметрично: подтянуть → SAME i, или шаг левой поверх: sum(i+1..j) ≤ l2 → HIGH_L j.

Здесь sum(a..b) — сумма высот ступенек между ногами после шага – это просто префиксные суммы: S[b]-S[a-1].
Для каждого i заранее считаем «дальше всего, куда можно прыгнуть» за один шаг при ограничении X как
next[i] = max j : S[j] ≤ S[i] + X (бинарный поиск/upper_bound).
По графу состояний с ребрами веса 1 делаем обычный BFS от SAME 0. Ответ — минимальное число шагов, чтобы попасть в SAME n (обе ноги на последней ступеньке). Если недостижимо — -1.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long l1, r1, l2, r2;
    int n;
    if (!(cin >> l1 >> r1)) return 0;
    cin >> l2 >> r2;
    cin >> n;
    vector<long long> h(n+1), pref(n+1, 0);
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
        pref[i] = pref[i-1] + h[i];
    }

    auto calc_next = [&](long long limit) {
        vector<int> nxt(n+1);
        for (int i = 0; i <= n; ++i) {
            long long target = pref[i] + limit;
            int j = int(upper_bound(pref.begin(), pref.end(), target) - pref.begin()) - 1;
            if (j < i) j = i;              // если шаг невозможен, остаёмся на месте
            nxt[i] = j;
        }
        return nxt;
    };

    vector<int> nl1 = calc_next(l1), nr1 = calc_next(r1);
    vector<int> nl2 = calc_next(l2), nr2 = calc_next(r2);

    const int SAME = 0, HIGH_L = 1, HIGH_R = 2;
    const int INF = 1e9;
    vector<vector<int>> dist(3, vector<int>(n+1, INF));
    deque<pair<int,int>> q;

    dist[SAME][0] = 0;
    q.push_back({SAME, 0});

    while (!q.empty()) {
        auto [st, i] = q.front(); q.pop_front();
        int d = dist[st][i];
        if (st == SAME) {
            int j = nl1[i];
            if (j > i && dist[HIGH_L][j] > d + 1) {
                dist[HIGH_L][j] = d + 1; q.push_back({HIGH_L, j});
            }
            j = nr1[i];
            if (j > i && dist[HIGH_R][j] > d + 1) {
                dist[HIGH_R][j] = d + 1; q.push_back({HIGH_R, j});
            }
        } else if (st == HIGH_L) {
            // действие 3
            if (dist[SAME][i] > d + 1) {
                dist[SAME][i] = d + 1; q.push_back({SAME, i});
            }
            // правая шагает поверх левой (ограничение r2)
            int j = nr2[i];
            if (j > i && dist[HIGH_R][j] > d + 1) {
                dist[HIGH_R][j] = d + 1; q.push_back({HIGH_R, j});
            }
        } else { // HIGH_R
            if (dist[SAME][i] > d + 1) {
                dist[SAME][i] = d + 1; q.push_back({SAME, i});
            }
            int j = nl2[i];
            if (j > i && dist[HIGH_L][j] > d + 1) {
                dist[HIGH_L][j] = d + 1; q.push_back({HIGH_L, j});
            }
        }
    }

    int ans = dist[SAME][n];
    cout << (ans >= INF ? -1 : ans) << '\n';
    return 0;
}

Пояснения:

  • pref[i] — сумма высот первых i ступенек. Тогда сложность шага из состояния с «верхней» ногой на ступеньке i — это pref[j] - pref[i].
  • calc_next(X) для каждого i находит самый дальний j, куда можно «дотянуться» с лимитом X (через upper_bound).
  • BFS по состояниям (тип, i) гарантирует минимальное число действий, т.к. все переходы имеют стоимость 1 и идут не вниз по лестнице.

Если лимиты слишком малы и нельзя сделать ни одного подъёма, алгоритм корректно выводит -1.

Поделиться этим Q&A