Codeforces Round #615 B. Collecting Packages

シンプルな問題

概要

• x,yの二次元平面があり、たかだかマスは1000程度である
• 0,0にロボットがおり、UかRのアクションを行える
• 100個のnx, nyが順番に与えられる
• ロボットは各nx,nyを通過できるか判定せよ。YESの場合、例を１つ表示せよ。

アプローチ

• 今の座標をx,yに対して、x <= nx かつ y <= nyであるかを判定。NGなら、"NO"が確定
• 可能なら、x軸の差分だけRを、y軸の差分だけUを表示する

q = int(input())
for q in range(q):
    qq = int(input())
    dat = []
    s = ""
    for _ in range(qq):
        x, y = map(int, input().split())
        dat.append([x, y])
        dat.sort(key=lambda a: a[0] + a[1])
    cx, cy = 0, 0
    f = True
    for i in range(qq):
        x, y = dat[i][0], dat[i][1]
        if x < cx or y < cy:
            f = False
            break
        s += "R" * (x - cx)
        s += "U" * (y - cy)
        cx,cy = dat[i][0], dat[i][1]
    if f:
        print("YES")
        print(s)
    else:
        print("NO")