Problem p03240 (python)

Fixed submission:


def read_input():
    n = int(input())
    conds = []
    for _ in range(n):
        x, y, h = map(int, input().split())
        conds.append(((x, y), h))

    return n, conds


def manhattan(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


def satisfy(cond, center):
    c, ch = center
    p, h = cond
    return ch == h + manhattan(p, c)


def zero_satisfy(cond, center):
    c, ch = center
    p, h = cond
    return ch <= manhattan(p, c)


def submit():
    n, conds = read_input()    

    if n == 1:
        p, h = conds[0]
        print("{} {} {}".format(p[0], p[1], h))
        return

    plus_conds = [c for c in conds if c[1] > 0]
    zero_conds = [c for c in conds if c[1] == 0]
    st = plus_conds[0]

    center_cands = []
    for i in range(101):
        for j in range(101):
            t = (i, j)
            th = st[1] + manhattan(st[0], t) # 仮にtがpより高い位置の頂点だとする
            center_cands.append((t, th))
    
    # 各条件について満たすか否かを判定していく
    for cond in plus_conds[1:]:
        center_cands = [c for c in center_cands if satisfy(cond, c)]

    # h=0の条件について、有効かどうか判定していく
    for cond in zero_conds:
        center_cands = [c for c in center_cands if zero_satisfy(cond, c)]

    # 全条件を満たすポイントは1つのはず
    center, h = center_cands[0]
    print("{} {} {}".format(center[0], center[1], h))
            

if __name__ == "__main__":
    submit()

Buggy submission (verdict: Runtime Error):


def read_input():
    n = int(input())
    conds = []
    for _ in range(n):
        x, y, h = map(int, input().split())
        conds.append(((x, y), h))

    return n, conds


def manhattan(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


def satisfy(cond, center):
    c, ch = center
    p, h = cond
    return ch == h + manhattan(p, c)


def submit():
    n, conds = read_input()    

    if n == 1:
        p, h = conds[0]
        print("{} {} {}".format(p[0], p[1], h))
        return

    center_cands = []
    s, sh = conds[0]
    for i in range(101):
        for j in range(101):
            t = (i, j)
            th = sh + manhattan(s, t) # 仮にtがpより高い位置の頂点だとする
            center_cands.append((t, th))
    
    # 各条件について満たすか否かを判定していく
    for cond in conds:
        center_cands = [c for c in center_cands if satisfy(cond, c)]

    # 全条件を満たすポイントは1つのはず
    center, h = center_cands[0]
    print("{} {} {}".format(center[0], center[1], h))
            

if __name__ == "__main__":
    submit()

Buggy submission (verdict: Runtime Error):

import math


def read_input():
    n = int(input())
    conds = [tuple(map(int, input().split())) for _ in range(n)]

    return n, conds


def m_dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])


def submit():
    n, conds = read_input()
    conds = [((c[0], c[1]), c[2]) for c in conds]
    conds.sort(key=lambda x: x[1], reverse=True)

    # n == 1のとき
    # そこが頂点になる
    if len(conds) == 1:
        print("{} {} {}".format(conds[0][0], conds[0][1], conds[1]))
        return

    # max(hi)が重複ない場合
    # 特定できるはずなので、そこが頂点になる
    if conds[0][1] > conds[1][1]:
        print("{} {} {}".format(conds[0][0][0], conds[0][0][1], conds[0][1]))
        return

    # max(hi)が重複する場合、それらをh0, h1とする
    # (x0, y0), (x1, y1)から等距離にある点を考える
    p1, p2 = conds[0][0], conds[1][0]
    h_12 = conds[0][1]

    cands = []
    for x in range(min((p1[0], p2[0])), max((p1[0], p2[0])) + 1):
        for y in range(min((p1[1], p2[1])), max((p1[1], p2[1])) + 1):
            t = (x, y)
            
            if m_dist(t, p1) != m_dist(t, p2):
                continue

            cands.append((t, h_12 + m_dist(t, p1)))

    for cand, cand_h in cands:
        check = True
        for p, h in conds:
            if h != max(0, cand_h - m_dist(cand, p)):
                check = False
                break

        if check:
            print("{} {} {}".format(cand[0], cand[1], cand_h))
            return

    assert False


if __name__ == "__main__":
    submit()