Problem: In the Ancient Kingdom of Snuke, there was a pyramid to strengthen the authority of Takahashi, the president of AtCoder Inc.   The pyramid had _center coordinates_ (C_X, C_Y) and _height_ H. The altitude of coordinates (X, Y) is max(H - |X - C_X| - |Y - C_Y|, 0).  Aoki, an explorer, conducted a survey to identify the center coordinates and height of this pyramid. As a result, he obtained the following information:    * C_X, C_Y was integers between 0 and 100 (inclusive), and H was an integer not less than 1.    * Additionally, he obtained N pieces of information. The i-th of them is: "the altitude of point (x_i, y_i) is h_i."   This was enough to identify the center coordinates and the height of the pyramid. Find these values with the clues above.

Submission attempts (in order):


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 submit():
    n, conds = read_input()    

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

    center_cands = {}
    for i in range(101):
        for j in range(101):
            center_cands[(i, j)] = None

    for p, h in conds:
        for i in range(101):
            for j in range(101):
                if center_cands[(i, j)] == -1:
                    continue
                
                d = manhattan(p, (i, j))
                if not center_cands[(i, j)]:    
                    center_cands[(i, j)] = (h - d, h + d)
                else:
                    if center_cands[(i, j)][0] == h - d:
                        center_cands[(i, j)] = (h - d, -1)
                    elif center_cands[(i, j)][1] == h + d :
                        center_cands[(i, j)] = (-1, h + d)
                    else:
                        center_cands[(i, j)] = -1

    for k, h in center_cands.items():
        if h == None or h == -1:
            continue
    
        if h[0] > 0:
            print("{} {} {}".format(k[0], k[1], h[0]))
        else:
            print("{} {} {}".format(k[0], k[1], h[1]))
            
            
if __name__ == "__main__":
    submit()



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 submit():
    n, conds = read_input()    

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

    center_cands = {}
    for i in range(101):
        for j in range(101):
            center_cands[(i, j)] = None

    for p, h in conds:
        for i in range(101):
            for j in range(101):
                if center_cands[(i, j)] == -1:
                    continue
                
                d = manhattan(p, (i, j))
                if not center_cands[(i, j)]:    
                    center_cands[(i, j)] = (h - d, h + d)
                else:
                    if center_cands[(i, j)][0] == h - d:
                        center_cands[(i, j)] = (h - d, -1)
                    elif center_cands[(i, j)][1] == h + d :
                        center_cands[(i, j)] = (-1, h + d)
                    else:
                        center_cands[(i, j)] = -1

    for k, h in center_cands.items():
        if h == None or h == -1:
            continue
    
        if h[0] > 0:
            print("{} {} {}".format(k[0], k[1], h[0]))
        else:
            print("{} {} {}".format(k[0], k[1], h[1]))
            
            
if __name__ == "__main__":
    submit()



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) 
            center_cands.append((t, th))
    
    
    for cond in plus_conds[1:]:
        center_cands = [c for c in center_cands if satisfy(cond, c)]

    
    for cond in zero_conds:
        center_cands = [c for c in center_cands if zero_satisfy(cond, c)]

    
    center, h = center_cands[0]
    print("{} {} {}".format(center[0], center[1], h))
            

if __name__ == "__main__":
    submit()

Verdicts: Wrong Answer

Wrong Answer

Accepted