形式化题目

$n$ 个车站排成一圈，第 $i$ 站存油 $p_i$，沿顺时针从第 $i$ 站到下一站的距离为 $d_i$，每升油行驶单位距离。汽车初始油量为 0，每到一站（含起点）立即带走该站全部油，行驶途中油量不得为负。对每个起点 $i$，判断始终沿顺时针、或始终沿逆时针走完一整圈回到起点是否可行；任一方向可行输出 TAK，否则 NIE。

把每站的收入与出边支出相减得到差额——顺时针 $a_i = p_i - d_i$，逆时针 $b_i = p_i - d_{i-1}$（逆时针的出边是上一站到本站的距离，$b_1$ 用 $d_n$）。样例的差额如下：

换到差额语言后，题目与油量、距离的具体数值再无关系：从起点出发的途中油量恰是差额的环形前缀和，“不缺油"就是"环形前缀和全部非负”。样例答案为 TAK / NIE / TAK / NIE / TAK：第 1、3、5 站顺时针可行，第 3、5 站逆时针也可行，取并集后第 2、4 站两个方向都不行。

正解

思路

1. 朴素做法：枚举起点模拟

对每个起点沿选定方向模拟一圈，途中维护油量非负：一个起点 $O(n)$，$n$ 个起点 $O(n^2)$，$n = 10^6$ 时约 $10^{12}$ 次操作不可行，两个方向还要再来一遍。瓶颈在于相邻起点只错开一站，却把几乎整圈从头重算。而判定只关心每个起点整圈前缀的最小值，所以关键在于：起点 $i$ 与起点 $i+1$ 的"整圈最小前缀"能不能互相增量推出。

直接递推并不成立——窗口首尾各挪一位，最小值可能两端同时变化，这正是"滑动窗口最小值"问题。标准解法是把差额倍长成 $2n$ 后用单调队列维护；下面的两段拆解利用环的衔接点固定这一点，把窗口拆开，省掉倍长数组和队列。

2. 环形前缀的两段拆解

起点 $i$ 的途中油量是差额从 $i$ 起的环形前缀，按是否绕过环的衔接点（第 $n$ 站与第 1 站之间）恰好分成两段：

• 不绕回段：位置 $i \dots n$，就是普通的段内前缀和，其最小值记为 $L(i)$；
• 绕回段：先背上余量 $\mathrm{suffix}(i) = a_i + a_{i+1} + \dots + a_n$（走完不绕回段后车上剩的油），再依次累加 $a_1, \dots, a_{i-1}$，其最小值恰为 $\mathrm{suffix}(i) + U(i-1)$，其中 $U(j)$ 是 $a_1 \dots a_j$ 的前缀最小值，$U(0) = 0$。

两段不重不漏地覆盖起点 $i$ 的全部 $n$ 个前缀，于是整圈最小前缀

$i = 1$ 时绕回段为空：$\mathrm{suffix}(1) + 0$ 就是整圈和，而 $L(1)$ 已包含整圈和，取 min 不改变结果，公式仍然成立。（实现里 $L(i)$、$\mathrm{suffix}(i)$、$U(i-1)$ 依次对应代码中的 tail、suffix、wrap。）

三个量都能滚动：$\mathrm{suffix}(i) = \mathrm{suffix}(i+1) + a_i$ 显然；$L(i) = \min(a_i,\ a_i + L(i+1))$ 是因为把首项 $a_i$ 提出来后，括号里恰好是 $L(i+1)$ 的全部候选；两者都从最后一站倒着推、每步 $O(1)$；$U(i-1)$ 就是正向扫描的上一步结果。一个倒序循环同时维护 $L$ 与 $\mathrm{suffix}$，每个起点 $O(1)$，总复杂度从 $O(n^2)$ 降到 $O(n)$。

顺时针方向的判定过程（正向预处理 $U(0..5) = [0, 2, 1, 1, 1, 1]$，$L$ 与 $\mathrm{suffix}$ 从最后一站倒着滚动）：

$m(i) \geqslant 0$ 的站 1、3、5 顺时针可行，正与样例一致。站 2、4 的不绕回段首项就是负数（$a_2 = -1$、$a_4 = -1$），直接出局；再看 $L(i)$ 一列从右往左只依赖上一行，这正是倒序滚动可行的原因。

3. 逆时针与两个方向的合并

逆时针差额 $b_i = p_i - d_{i-1}$。把 $b$ 倒序存放为 $c_k = b_{n-k}$ 后，从第 $i$ 站逆时针走依次经过 $b_i, b_{i-1}, \dots, b_1, b_n, \dots, b_{i+1}$，恰是 $c$ 从下标 $n-1-i$ 开始正向走——于是完全复用同一个判定函数。读入时 $b_i$ 只依赖上一站的出边 $d_{i-1}$，可以边读边填进倒序下标；只有 $b_1 = p_1 - d_n$ 要等最后一站读完，用 p_first 暂存起点油量后补。

最终两个方向按位或：任一方向可行即 TAK。两个方向的结论并不总一致（样例中第 1 站只有顺时针可行，第 3、5 站两方向都可行），所以必须各算一遍再取或。

顺带一提，另一种同阶 $O(n)$ 写法是把差额倍长成 $2n$ 数组、用单调队列维护长度为 $n$ 的滑动窗口最小值；两段拆解相当于把该窗口按固定衔接点拆成"段内 + 绕回段"，代价更低。

代码

Python 版：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 21:03
# update_at: 2026-09-30 21:11

import sys


def ok_each_start(gain: list[int]) -> list[bool]:
    """环形差额序列：判断以每个下标为起点顺推一圈，累计值是否始终不为负。

    起点 i 的整圈前缀分两段：不绕回段 gain[i..n-1] 的前缀最小值 tail（倒序滚动），
    以及绕回段 gain[0..i-1] 的前缀最小值 wrap（正向预处理），绕回段还要先补上
    余量 suffix = gain[i..n-1] 之和；两段更小者就是该起点整圈的最小前缀。
    """
    n = len(gain)
    wrap_min: list[int] = []  # wrap_min[i] = gain[0..i] 的前缀最小值
    run = 0
    for x in gain:
        run += x
        wrap_min.append(run if not wrap_min else min(run, wrap_min[-1]))

    ok = [False] * n
    tail = 0    # 不绕回段的前缀最小值；初值 0 让首项算出 min(x, x+0) = x
    suffix = 0  # 绕回段要接着用的余量 gain[i..n-1] 之和
    for i in range(n - 1, -1, -1):
        x = gain[i]
        tail = min(x, x + tail)               # 从右往左滚动的段内最小前缀
        suffix += x
        wrap = wrap_min[i - 1] if i else 0    # 绕回段 gain[0..i-1] 的最小前缀
        ok[i] = min(tail, suffix + wrap) >= 0
    return ok


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    cw: list[int] = [0] * n   # 顺时针差额 a_i = p_i - d_i
    ccw: list[int] = [0] * n  # 逆时针差额 p_i - d_{i-1}，倒序存放以复用同一判定
    p_first = prev_d = 0
    for i in range(n):
        p, d = next(data), next(data)
        cw[i] = p - d
        if i:
            # 第 i 站的逆时针差额放到倒序下标 n-1-i：只需要上一站的出边 d_{i-1}
            ccw[n - 1 - i] = p - prev_d
        else:
            p_first = p  # b_0 = p_0 - d_{n-1} 要等最后一站的出边读完
        prev_d = d
    ccw[n - 1] = p_first - prev_d

    ok_cw = ok_each_start(cw)
    ok_ccw = ok_each_start(ccw)
    # 原第 i 站逆时针可行 = 倒序数组从下标 n-1-i 出发正推一圈可行
    out = "\n".join(
        "TAK" if ok_cw[i] or ok_ccw[n - 1 - i] else "NIE" for i in range(n)
    )
    sys.stdout.write(out + "\n")


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 12:00
 * update_at: 2026-10-05 12:00
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 1000005;

int n; // 车站数

ll cw[MAXN];  // 顺时针差额 cw[i] = p_i - d_i，下标 1..n
ll ccw[MAXN]; // 逆时针差额 b_i = p_i - d_{i-1}，倒序存放：ccw[n+1-i] = b_i
ll wrap_min[MAXN]; // wrap_min[i] = 差额序列前 i 项的前缀最小值
char ok_cw[MAXN];  // ok_cw[i] = 从第 i 站顺时针能否走通
char ok_ccw[MAXN]; // ok_ccw[k] = 倒序差额序列从下标 k 出发能否走通

// 环形差额序列 gain[1..n]：判断以每个位置为起点顺推一圈，累计值是否始终非负。
// 起点 i 的整圈前缀按环的衔接点拆成两段：
//   不绕回段 gain[i..n]，其前缀最小值 tail 从右往左滚动；
//   绕回段 gain[1..i-1]，其前缀最小值是 wrap_min[i-1]，前面还要先补余量 suffix。
void check_each_start(ll gain[], char ok[]) {
    ll run = 0;
    for (int i = 1; i <= n; i++) {
        run += gain[i];
        bool first = (i == 1);
        wrap_min[i] = first ? run : min(run, wrap_min[i - 1]);
    }

    ll tail = 0;   // 不绕回段的前缀最小值，初值 0 使首项算出 min(x, x+0) = x
    ll suffix = 0; // 绕回段要接着用的余量 gain[i..n] 之和
    for (int i = n; i >= 1; i--) {
        ll x = gain[i];
        tail = min(x, x + tail);
        suffix += x;
        ll wrap = (i == 1) ? 0 : wrap_min[i - 1];
        ok[i] = (min(tail, suffix + wrap) >= 0) ? 1 : 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    ll p_first = 0; // 第 1 站的存油，等读到最后一站的出边 d_n 后补 b_1
    ll prev_d = 0;  // 上一站的出边 d_{i-1}
    for (int i = 1; i <= n; i++) {
        ll p, d;
        cin >> p >> d;
        cw[i] = p - d;

        int k = n + 1 - i; // 第 i 站的逆时针差额放到倒序下标
        if (i == 1) {
            p_first = p; // b_1 = p_1 - d_n，d_n 要等最后一站读完
        } else {
            ccw[k] = p - prev_d; // 逆时针出边是上一站到本站的距离
        }
        prev_d = d;
    }
    ccw[n] = p_first - prev_d;

    check_each_start(cw, ok_cw);
    check_each_start(ccw, ok_ccw);

    for (int i = 1; i <= n; i++) {
        // 原第 i 站逆时针可行 = 倒序数组从下标 n+1-i 出发顺推一圈可行
        int k = n + 1 - i;
        if (ok_cw[i] || ok_ccw[k]) {
            cout << "TAK\n";
        } else {
            cout << "NIE\n";
        }
    }
    return 0;
}

复杂度

• 时间复杂度：$O(n)$。每方向正向一趟预处理 $U$、倒序一趟滚动判定，两个方向共 4 趟线性扫描，外加读入、输出各 $O(n)$；与倍长 + 单调队列的正解同阶。
• 空间复杂度：$O(n)$。cw、ccw 两个差额数组与 wrap_min 各 $n$ 个整数，外加两个长度 $n$ 的布尔结果。累计差额可达 $\sim 10^{15}$，Python int 任意精度不会溢出（C++ 需 long long）。
• 实测：数据仓 10 组真实数据（$n \leqslant 10^5$）全部 PASS，最大单测 0.072s、峰值内存约 38MB；$n = 10^6$ 满规模下 Python 存在 TLE/MLE 风险（本仓库允许），算法复杂度不受影响。

总结

• 差额化 $a_i = p_i - d_i$ 把"途中不缺油"等价成"环形前缀和全非负"，判定与具体油量、距离解耦。
• 整圈前缀按固定衔接点拆成"不绕回段 + 绕回段"，两段最小值 $L(i)$ 与 $\mathrm{suffix}(i) + U(i-1)$ 各自 $O(1)$ 滚动合并，把 $O(n^2)$ 枚举压成 $O(n)$——本质是滑动窗口最小值的分段解法。
• 逆时针差额倒序存放即可复用同一判定，两个方向取或得到最终答案。