logoChat01.ai

[B’-B] Как работают догонялки? Объясняю на котятах...

تم الإنشاء في: ١٠ سبتمبر ٢٠٢٥

تمت الإجابة باستخدام GPT-5 Thinking بواسطة Chat01

سؤال

[B’-B] Как работают догонялки? Объясняю на котятах
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Кися и Котя играют в догонялки на числовой прямой.
Котя изначально находится в точке T, а Кися в точке S.
Кися пытается убежать от Коти. Каждую секунду Кися перемещается вправо по числовой прямой. Через одну секунду Кися будет в точке S + 1, через две S + 1 + 2, через три S + 1 + 2 + 3, и
так далее.
Если Котя находится в точке X, у него есть три возможных перемещения за одну секунду:
• Переместиться на один вправо и оказаться в точке X + 1
• Переместиться на один влево и оказаться в точке X − 1
• Магически телепортироваться в точку 2 · X
Помогите Коте — скажите, за какое минимальное время он сможет поймать Кисю.
Учтите, что Котя может ловить Кисю только на неотрицательных координатах, не превышающих 500, 000, то есть координата Коти не должна превышать 500, 000 в любой момент времени.
Если Кися успела убежать за допустимую для Коти зону, мы считаем, что она победила.
Формат входных данных
В единственной строке вводится два целых числа 0 6 T, S 6 500, 000 — изначальные координаты
Коти и Киси.
Формат выходных данных
Выведите одно число — минимальное количество секунд, которое понадобится Коте, чтобы поймать Кисю. Если это невозможно, выведите −1.
Примеры
стандартный ввод стандартный вывод
4 13 2
13 4 3
1 499957 -1

الفكرة

Explaining the problem

This seems like a variation of “Hide-and-seek,” with a cat moving in increasing steps, while Kotya can move by certain operations. We need to find the minimum time required for Kotya to catch Kiся, considering their movements and maximum position constraints. If Kiся exceeds the zone, she wins.

Solving using BFS

The problem seems like it requires a BFS approach to calculate the shortest times Kotya needs to catch Kiся. Each second, Kiся's position increases based on a sum formula. We should calculate Kotya’s reachable times for each position considering alternating parities (t % 2). We’ll check if Kotya can land on Kiся’s position at the same time. If not, return -1. Let’s implement this in Python or C++.

Refining the approach for BFS

We set a boundary of 500,000 for movement states, but may extend it a bit to avoid overflow. The BFS needs to track each position and its parity (even or odd) to ensure minimal time for Kotya to catch Kiся. I’ll handle edge cases carefully, like when Kotya is immediately at the same position. BFS will explore positions up to the limit.

Optimizing BFS with time limit

To optimize, I’ll set a limit on the time based on when Kiся crosses the boundary (t_max), so the BFS won’t expand beyond that. By keeping track of positions and times, I can stop early if further exploration is unnecessary. This ensures we don’t go past the maximum allowable time or explore unnecessary nodes.

Optimizing BFS for time limits

To avoid exploring beyond necessary points, I'll implement BFS that stores positions with their earliest times. I'll respect the time limit, t_max, when moving through the queue, thus ensuring efficient exploration. After calculating the t_max boundary for each iteration, BFS will halt if this time limit is exceeded.

Thought for 48s

الإجابة

Вот краткое решение через BFS по Коте с учётом чётности времени.
Идея: запоминаем для каждой координаты минимальное время достижения с чётностью t % 2. На шаге t Кися стоит в S + t(t+1)/2. Как только для какого-то t выполняется dist[t % 2][S + t(t+1)/2] ≤ t, — Котя может там оказаться вовремя, значит ответ найден.
Если Кися успевает уйти правее 500 000 раньше, чем это случится, ответа нет.

C++ (17)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    const int MAXX = 500000;

    int T, S;
    if (!(cin >> T >> S)) return 0;

    if (T == S) { cout << 0 << '\n'; return 0; }

    // dist[parity][x] = минимальное время добраться до x с такой чётностью времени
    vector<int> dist0(MAXX + 1, -1), dist1(MAXX + 1, -1);
    deque<pair<int,int>> q;
    dist0[T] = 0;
    q.push_back({T, 0});

    // Полный BFS по состояниям Коти в границах [0..MAXX]
    while (!q.empty()) {
        auto [x, t] = q.front(); q.pop_front();
        int nt = t + 1;

        auto relax = [&](int nx) {
            if (nx < 0 || nx > MAXX) return;
            if (nt % 2 == 0) {
                if (dist0[nx] == -1) { dist0[nx] = nt; q.push_back({nx, nt}); }
            } else {
                if (dist1[nx] == -1) { dist1[nx] = nt; q.push_back({nx, nt}); }
            }
        };

        relax(x - 1);
        relax(x + 1);
        if ((long long)x * 2 <= MAXX) relax(x * 2);
    }

    // Перебираем моменты времени, пока Кися не убежит за пределы
    long long t = 0;
    while (true) {
        long long pos = (long long)S + t * (t + 1) / 2;
        if (pos > MAXX) break; // Кися убежала в запрещённую зону
        int p = (int)(t & 1);
        int best = (p == 0 ? dist0[(int)pos] : dist1[(int)pos]);
        if (best != -1 && best <= t) {
            cout << t << '\n';
            return 0;
        }
        ++t;
    }

    cout << -1 << '\n';
    return 0;
}

Пояснения

  • Состояния ограничиваем диапазоном [0, 500000] (по условию Котя не может выходить за него).
  • Память: два массива по 500001 целых.
  • Время: один BFS по графу на ~500 000 вершинах и 3 рёбрах из каждой + линейный перебор t до момента, когда Кися покинет зону (порядка 1000 шагов в худшем случае). Это проходит за лимиты.

مشاركة هذا السؤال والجواب