2502 問題 C: 信息學奧賽一本通T1600-旅行問題
時間限制: 1s
內存限制: 128MB 提交: 71 解決: 16
題目描述
原題來自:POI 2004
John 打算駕駛一輛汽車周游一個環(huán)形公路。公路上總共有 n 車站,每站都有若干升汽油(有的站可能油量為零),每升油可以讓汽車行駛一千米。John 必須從某個車站出發(fā),一直按順時針(或逆時針)方向走遍所有的車站,并回到起點。在一開始的時候,汽車內油量為零,John 每到一個車站就把該站所有的油都帶上(起點站亦是如此),行駛過程中不能出現沒有油的情況。
任務:判斷以每個車站為起點能否按條件成功周游一周。
輸入
第一行是一個整數 n,表示環(huán)形公路上的車站數;
接下來 n 行,每行兩個整數 pi,di ,分別表示表示第 i 號車站的存油量和第 i 號車站到下一站的距離。
輸出
輸出共 n 行,如果從第 i 號車站出發(fā),一直按順時針(或逆時針)方向行駛,能夠成功周游一圈,則在第 i 行輸出 TAK,否則輸出 NIE。
提示
數據范圍與提示:
對于全部數據,3≤n≤106,0≤pi≤2×109,0<di≤2×109 。