Problem:


危ない橋

  会津若松市よりずっと北に位置する会津古松村では、「ヤ橋(やばし)   」と呼ばれる橋が周辺の村へ移動する唯一の手段となっています。その橋は通行人が多いにも関わらず、今にも壊れそうなほど老朽化が進んでしまっています。 

 ヤ橋は 150 [kg] まで耐えられる強度を持っています。例えば、80 [kg] の人と 50 [kg] の人が同時に渡ることはできますが、80 [kg] の人が渡っているときに 90 [kg] の人が渡り始めると、ヤ橋は壊れてしまいます。

  もしヤ橋が壊れてしまったら、会津古松村の人々は周辺の村へ移動する手段を失ってしまいます。そこで、村で唯一のプログラマーであるあなたは、村民の生活を守るために、橋の渡り方から橋が壊れるか否かを判定するプログラムを作成することにしました。

 橋を渡る通行人の人数 n (1 ≤ n ≤ 100)、各通行人の体重 mi (1 ≤ mi ≤ 100)、橋を渡り始める時刻 ai、渡り終える時刻 bi (0 ≤ ai, bi < 231) を入力とし、橋が壊れない場合は“OK ”と出力し、壊れる場合は“NG ”と出力するプログラムを作成してください。なお、橋の上にいる通行人の体重の総和が 150 [kg] を超えてしまうとヤ橋は壊れてしまいます。また、ai の時点で通行人は橋の上にいますが、bi の時点では橋の上にいません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。各データセットは以下の形式で与えられます。

n
m1 a1 b1
m2 a2 b2
:
mn an bn

データセットの数は 1200 を超えません。

Output

入力データセットごとに、橋が壊れるか否かを1行に出力します。

Sample Input

3
80 0 30
50 5 25
90 27 50
3
80 0 30
70 5 25
71 30 50
0

Output for the Sample Input

NG
OK



Sample input:
3
80 0 30
50 5 25
90 27 50
3
80 0 30
70 5 25
71 30 50
0


Sample output:
NG
OK

Submission status: Wrong Answer

Solution code:
while True:
    N = int(input())
    if not N:
        break
    e = []
    for i in range(N):
        m, a, b = map(int, input().split())
        e.append((a, m))
        e.append((b, -m))

    M = 0
    ot = -1
    for t, m in sorted(e):
        M += m
        if M > 150 and ot != t:
            print('NG')
            break
        ot = t
    else:
        print('OK')

Submission status: Wrong Answer

Solution code:
while True:
    N = int(input())
    if not N:
        break
    e = []
    for i in range(N):
        m, a, b = map(int, input().split())
        e.append((a, m))
        e.append((b, -m))

    M = 0
    ot = -1
    for t, m in sorted(e):
        M += m
        if M >= 150 and ot != t:
            print('NG')
            break
        ot = t
    else:
        print('OK')

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((a, m))
        t_w.append((b, -m))
    t_w.sort(key=lambda x: x[0])
    ans, cur = 'OK', 0
    for t, w in t_w:
        cur += w
        # print('t', t, 'w', w, 'cur', cur)
        if cur > 150:
            ans = 'NG'
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((b, -m))
        t_w.append((a, m))
    t_w.sort(key=lambda x: x[0])
    ans, cur = 'OK', 0
    for t, w in t_w:
        cur += w
        # print('t', t, 'w', w, 'cur', cur)
        if cur > 150:
            ans = 'NG'
            break
    print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((a, m, 5))
        t_w.append((b, -m, 3))
        t_w.sort(key=itemgetter(0, 2))
        ans, cur = 'OK', 0
        for t, w, pri in t_w:
            cur += w
            # print('t', t, 'w', w, 'cur', cur)
            if cur > 150:
                ans = 'NG'
                break
            print(ans)

Submission status: Wrong Answer

Solution code:

from operator import itemgetter

while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((a, m, 5))
        t_w.append((b, -m, 3))
        t_w.sort(key=itemgetter(0, 2))
        ans, cur = 'OK', 0
        for t, w, pri in t_w:
            cur += w
            # print('t', t, 'w', w, 'cur', cur)
            if cur > 150:
                ans = 'NG'
                break
        print(ans)

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break

    bridge = []
    for i in range(n):
        m, a, b = map(int, raw_input().split())
        bridge.append([a, m])
        bridge.append([b, -m])

    bridge.sort(cmp=lambda x, y: cmp(x[0], y[0]))

    w = 0
    for i in bridge:
        w += i[1]
        if w > 150:
            break

    print "OK" if w <= 150 else "NG"

Submission status: Accepted

Solution code:
while True:
    N = int(input())
    if not N:
        break
    e = []
    for i in range(N):
        m, a, b = map(int, input().split())
        e.append((a, m))
        e.append((b, -m))

    M = 0
    ot = 0
    for t, m in sorted(e):
        if M > 150 and ot != t:
            print('NG')
            break
        M += m
        ot = t
    else:
        print('OK')

Submission status: Accepted

Solution code:
import operator
while 1:
    n = int(input())
    if n == 0:break

    s = [list(map(int,input().split())) for i in range(n)]
    e = s[:]
    s.sort(key = operator.itemgetter(1))
    e.sort(key = operator.itemgetter(2))
    s_i = e_i = 0
    w = 0
    for i in range(n*2):
        if e_i < len(e) and s[s_i][1] >= e[e_i][2]:
            w -= e[e_i][0]
            e_i += 1
        else:
            w += s[s_i][0]
            s_i += 1

        if w > 150:
            print('NG')
            break
        if i == n*2-1 or s_i >= len(s):
            print('OK')
            break

Submission status: Accepted

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        w=0
        e=[]
        b=0
        for i in range(n):
            d=[int(x) for x in raw_input().split()]
            e.append((d[1],d[0]))
            e.append((d[2],-d[0]))
        es=sorted(e)
        for i in range(2*n):
            h=es.pop(0)
            w=w+h[1]
            if w>150:
                b=1
                break
        if b:
            print 'NG'
        else:
            print 'OK'

Submission status: Accepted

Solution code:
def f(p):
    t = 0
    for v in data:
        w, a, b = v
        if a <= p < b:
            t += w
    else:
        if t <= 150:
            return True
        else:
            return

while True:
    n = int(raw_input())
    if n == 0: break
    data = [map(int, raw_input().split()) for i in range(n)]
    for p in sorted([v[1] for v in data]):
        if not f(p):
            print 'NG'
            break
    else:
        print 'OK'

Submission status: Accepted

Solution code:
from operator import itemgetter

while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((a, m, 5))
        t_w.append((b, -m, 3))
    t_w.sort(key=itemgetter(0, 2))
    ans, cur = 'OK', 0
    for t, w, pri in t_w:
        cur += w
        # print('t', t, 'w', w, 'cur', cur)
        if cur > 150:
            ans = 'NG'
            break
    print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

while 1:
    n = int(input())
    if n == 0:
        break
    t_w = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        t_w.append((a, m, 5))
        t_w.append((b, -m, 3))
        t_w.sort(key=itemgetter(0, 2))
        ans, cur = 'OK', 0
        for t, w, pri in t_w:
            cur += w
            # print('t', t, 'w', w, 'cur', cur)
            if cur > 150:
                ans = 'NG'
                break
    print(ans)

Submission status: Accepted

Solution code:
# AOJ 0231: Dangerous Bridge
# Python3 2018.6.25 bal4u
# 時間昇順ソート

while True:
	n = int(input())
	if n == 0: break
	tbl = []
	for i in range(n):
		m, a, b = map(int, input().split())
		tbl.append((a, m))
		tbl.append((b, -m))
	tbl.sort()
	sum, t, s = 0, -1, 0
	for i in range(len(tbl)):
		if t != tbl[i][0]:
			if (sum + s) > 150: break
			sum += s
			t, s = tbl[i][0], tbl[i][1]
		else: s += tbl[i][1]
	print("OK" if sum+s <= 150 else "NG")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  tlst = []
  qlst = []
  for _ in range(n):
    m, a, b = map(int, input().split())
    qlst.append((m, a, b))
    tlst.append(a)
    tlst.append(b)
    tlst.append(b - 1)
  tlst = sorted(list(set(tlst)))
  tlst.sort()
  tdic = {}
  for i, t in enumerate(tlst):
    tdic[t] = i
  lent = len(tlst)
  mp = [0] * lent
  for m, a, b in qlst:
    a, b = tdic[a], tdic[b]
    mp[a] += m
    mp[b] -= m
  
  acc = 0
  for i in range(lent):
    acc += mp[i]
    mp[i] = acc
    if acc > 150:
      print("NG")
      break
  else:
    print("OK")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  tlst = []
  qlst = []
  for _ in range(n):
    m, a, b = map(int, input().split())
    qlst.append((m, a, b))
    tlst.append(a)
    tlst.append(b)
    tlst.append(b - 1)
  tlst = sorted(list(set(tlst)))
  tlst.sort()
  tdic = {}
  for i, t in enumerate(tlst):
    tdic[t] = i
  lent = len(tlst)
  mp = [0] * lent
  for m, a, b in qlst:
    a, b = tdic[a], tdic[b]
    mp[a] += m
    mp[b] -= m
  
  acc = 0
  for i in range(lent):
    acc += mp[i]
    if acc > 150:
      print("NG")
      break
  else:
    print("OK")

Submission status: Accepted

Solution code:
while True:
  n = int(input())
  if n == 0:
    break
  tlst = []
  qlst = []
  for _ in range(n):
    m, a, b = map(int, input().split())
    qlst.append((m, a, b))
    tlst.append(a)
    tlst.append(b)
  tlst = sorted(list(set(tlst)))
  tlst.sort()
  tdic = {}
  for i, t in enumerate(tlst):
    tdic[t] = i
  lent = len(tlst)
  mp = [0] * lent
  for m, a, b in qlst:
    a, b = tdic[a], tdic[b]
    mp[a] += m
    mp[b] -= m
  
  acc = 0
  for i in range(lent):
    acc += mp[i]
    if acc > 150:
      print("NG")
      break
  else:
    print("OK")

Submission status: Accepted

Solution code:
while True:
    n=input()
    if n==0:break
    L=[]
    for	i in range(n):
	m,a,b=map(int,raw_input().split())
	L.append((a,1,m))
	L.append((b,0,m))
    L.sort()
    wgt=0
    for ts,p,w in L:
	if p:
            wgt+=w
        else:
            wgt-=w
    	if wgt>150:
            print "NG"
            break
    else:
	print "OK"

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break

    bridge = {}

    for i in range(n):
        m, a, b = map(int, raw_input().split())
        if a in bridge:
            bridge[a] += m
        else:
            bridge[a] = m

        if b in bridge:
            bridge[b] -= m
        else:
            bridge[b] = -m

    w = 0
    for key in sorted(bridge.keys()):
        w += bridge[key]
        if w > 150:
            break

    print "OK" if w <= 150 else "NG"

Submission status: Accepted

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break

    bridge = {}
    for i in range(n):
        m, a, b = map(int, raw_input().split())
        bridge[a] = bridge.setdefault(a, 0) + m
        bridge[b] = bridge.setdefault(b, 0) - m

    w = 0
    for key in sorted(bridge.keys()):
        w += bridge[key]
        if w > 150:
            break

    print "OK" if w <= 150 else "NG"

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	datas = [map(int,raw_input().split()) for i in range(n)]
	maxw = 0
	for d1 in datas:
		w = sum([d2[0] for d2 in datas if d2[1]<=d1[1]<d2[2]])
		maxw = max(w,maxw)
	print "OK" if maxw <= 150 else "NG"

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	d = [map(int,raw_input().split()) for i in range(n)]
	w = max([sum([d2[0] for d2 in d if d2[1]<=d1[1]<d2[2]]) for d1 in d])
	print "OK" if w <= 150 else "NG"

Submission status: Accepted

Solution code:
while 1:
    n=input()
    if n==0: break
    d=[map(int,raw_input().split()) for i in range(n)]
    w=max([sum([d2[0] for d2 in d if d2[1]<=d1[1]<d2[2]]) for d1 in d])
    print "OK" if w<151 else "NG"

Submission status: Accepted

Solution code:
while 1:
	n=input()
	if n==0: break
	d=[map(int,raw_input().split()) for i in range(n)]
	w=max([sum([d2[0] for d2 in d if d2[1]<=d1[1]<d2[2]]) for d1 in d])
	print "OK" if w<151 else "NG"

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    v = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        v.append((a,m))
        v.append((b,-m))
    v.sort()
    s = 0
    ans = 'OK'
    for x in v:
        s += x[1]
        if s > 150:
            ans = 'NG'
    print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


MAX = 150

OUT = 0
IN = 1

class Info:
    def __init__(self,arg_weight,arg_TIME,arg_Type):
        self.weight = arg_weight
        self.TIME = arg_TIME
        self.Type = arg_Type

    def __lt__(self,another):
        if self.TIME != another.TIME:
            return self.TIME < another.TIME
        else:
            return self.Type < another.Type

while True:
    N = int(input())
    if N == 0:
        break

    Q = []

    for _ in range(N):
        weight,left,right = map(int,input().split())
        heappush(Q,Info(weight,left,IN))
        heappush(Q,Info(weight,right,OUT))

    tmp_sum = 0
    FLG = True

    while len(Q) > 0 and FLG == True:
        info = heappop(Q)
        if info.Type == IN:
            tmp_sum += info.weight
            if tmp_sum > MAX:
                print("NG")
                FLG = False
                break
        else:
            tmp_sum -= info.weight

    if FLG == True:
        print("OK")

Submission status: Accepted

Solution code:

while True:
    num = int(input())
    if num == 0:
        break
    
    L = []
    start = set()
    for _ in range(num):
        w, a, b = [int(x) for x in input().split()]
        L.append([w,a,b])
        start.add(a)
    
    f = 0
    for t in sorted(start):
        wt  = 0
        for l in L:
            if t >= l[1] and t < l[2]:
                wt += l[0]
        if wt > 150:
            f += 1
    
    if f > 0:
        print("NG")
    else:
        print("OK")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Dangerous Bridge
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0231

"""
import sys


def solve(n):
    events = []
    for _ in range(n):
        m, a, b = map(int, input().split())
        events.append([a, m])
        events.append([b, -m])

    weight = 0
    for t, m in sorted(events):
         weight += m
         if weight > 150:
             return 'NG'
    return 'OK'


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        ans = solve(n)
        print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class Sch:
    def __init__(self, m, t):
        self.m = m
        self.t = t
        
    def __lt__(self,other):
        if self.t == other.t:
            return self.m < other.m
        else:
            return self.t < other.t
        

while True:
    N = int(input())
    if N == 0:
        break
    
    schedule = []
    for l in range(N):
        m,a,b = [int(i) for i in input().split()]
        schedule.append(Sch(m,a))
        schedule.append(Sch(-m,b))

    schedule.sort()
    
    M = 0
    ans = "OK"
    for i in range(len(schedule)):
        M = M + schedule[i].m
        if M > 150:
            ans = "NG"
            break
    
    print(ans)

Submission status: Accepted

Solution code:
while 1:
    N = int(input())
    if N == 0:
        break
    q = []
    M = {}
    for i in range(N):
        m, a, b = map(int, input().split())
        M[a] = M.get(a, 0) + m
        M[b] = M.get(b, 0) - m
    *q, = M.items()
    q.sort()
    ok = 1
    cur = 0
    for t, v in q:
        cur += v
        if cur > 150:
            ok = 0
    print("OK" if ok else "NG")

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	datas = [map(int,raw_input().split()) for i in range(n)]
	maxw = 0
	for d1 in datas:
		w = sum([d2[0] for d2 in datas if d2[1]<=d1[1]<d2[2]])
		maxw = max(w,mxw)
	print "OK" if maxw <= 150 else "NG"