P83252

旅行问题

难度 6 级 初三 数据结构入门 单调队列
讨论 统计 7通过 12提交 58.3%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

火星的所有空间站都位于一个圆上,Byteazar 在其中一个空间站登陆然后开始绕圈旅行。

旅行需要耗费油料,一升油料只能跑 1 米,每个空间站可以补给的油料都有所不同。

Byteazar 每到一个空间站便可以把该空间站的油料全部拿走(他的油箱是没有容量限制的)。但是如果走到某个时候突然没油了那么旅行便失败了。

Byteazar 需要决定要在哪个地方登陆使得他能顺利访问完所有的空间站后回到他当初登陆的地方,他登陆后可以选择两个方向中的任意一个进行旅行。

输入

第一行一个整数 n,代表空间站数量,所有空间站由 1 至 n 进行标号。

之后 n 行,每行两个整数 p_i,d_i,第 i + 1 行描述了第 i 号空间站的信息,其中 p_i 表示该空间站可以补给的油量,d_i 则指明了它到 i+1 号空间站的距离,对于 n 号空间站,d_i 表示它和 1 号空间站的距离。

输出

输出 n 行,每行一个字符串 TAK 或 NIE。

若你认为在 i 号空间站登陆是可行的,则需要在第 i 行输出 TAK,否则输出 NIE。

样例

样例 1
输入
5
3 1
1 2
5 2
0 1
5 4
输出
TAK
NIE
TAK
NIE
TAK

提示

对于 100\% 的数据,3\le n\le10^6,p_i \ge 0,d_i>0,\sum d_i,\sum p_i\le2\times10^9。

来源

动规专题

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交