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):
import collections

N = int(input())

dp = [[None]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if dp[x][y] == None: 
        dp[x][y] = h
    elif dp2[x][y] != check[x][y]:
        dp[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if dp[nx][ny] == None: 
                            dp[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == dp[nx][ny]: 
                                
                                pass
                            else: 
                                dp[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

if ans_x == -1 and ans_y == -1:
    for h in range(N):
        a, b, c = lst[h]
        bfs2(a,b,c)
    for i in range(101):
        for j in range(101):
            if ans < dp[i][j]:
                ans = max(ans, dp[i][j])
                ans_x, ans_y = i, j



print (ans_x, ans_y, ans)
#print (check)





import collections

N = int(input())

dp = [[0]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]
    dp[x][y] = z

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(2, 3, 5))
#print (bfs(2, 1, 5))
#print (bfs(1, 2, 5))
#print (bfs(3, 2, 5))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)

ans = 0
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

print (ans_x, ans_y, ans)
#print (check)

import collections

N = int(input())

dp = [[None]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

print (ans_x, ans_y, ans)
#print (check)





import collections

N = int(input())

dp = [[None]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if dp[x][y] == None: 
        dp[x][y] = h
    elif dp2[x][y] != check[x][y]:
        dp[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if dp[nx][ny] == None: 
                            dp[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == dp[nx][ny]: 
                                
                                pass
                            else: 
                                dp[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

if ans_x == -1 and ans_y == -1:
    for h in range(N):
        a, b, c = lst[h]
        bfs2(a,b,c)
    for i in range(101):
        for j in range(101):
            if ans < dp[i][j]:
                ans = max(ans, check[i][j])
                ans_x, ans_y = i, j



print (ans_x, ans_y, ans)
#print (check)





import collections

N = int(input())

dp = [[None]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

def bfs2(x, y, h):
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs2(a, b, c)
    #print (check)

ans = -1
ans_x = -1
ans_y = -1
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

if ans_x != -1 and ans__y != -1:
    print (ans_x, ans_y, ans)
else:
    for h in range(N):
        a, b, c = lst[h]
        bfs(a, b, c)
        for i in range(101):
            for j in range(101):
                if ans < check[i][j]:
                    ans = max(ans, check[i][j])
                    ans_x, ans_y = i, j
    print (ans_x, ans_y, ans)
#print (check)





import collections

N = int(input())

dp = [[0]* 101 for _ in range(101)] 
check = [[None]* 101 for _ in range(101)] 　重ね合わせた結果に利用
#print (dp)
lst = []
for i in range(N):
    x, y, z = map(int, input().split())
    lst += [[x, y, z]]
    dp[x][y] = z

#print (lst)
#print (dp)

move = [[-1,0], [1, 0], [0, -1],[0, 1]]
def bfs(x, y, h):
    if h == 0:
        return 0
    dp2 = [[-1]* 101 for _ in range(101)] 　bfsするときに訪れたかどうかの判定に利用
    dp2[x][y] = h 
    if check[x][y] == None: 
        check[x][y] = h
    elif dp2[x][y] != check[x][y]:
        check[x][y] = -10
    
    q = collections.deque()
    q.append([x, y]) 
    #print (q)
    while True: 
        #print ('True') 
        if not q: 
            #print (q)
            #print ('dp2', dp2)
            return 'B'
        else: 
            px, py = q.popleft() 
            for dx, dy in move:
                nx = px + dx
                ny = py + dy
                if 0 <= nx and nx <101 and 0 <= ny and ny < 101: 
                    if dp2[nx][ny] == -1: 
                        if check[nx][ny] == None: 
                            check[nx][ny] = dp2[px][py] + 1 
                            dp2[nx][ny] = dp2[px][py] + 1 
                            q.append([nx, ny]) 
                            #print (check)
                            #print ('C')
                        else: 
                            #print ('D')
                            dp2[nx][ny] = dp2[px][py] + 1
                            if dp2[nx][ny] == check[nx][ny]: 
                                
                                pass
                            else: 
                                check[nx][ny] = -10
                            q.append([nx, ny])
    return 'A'

#print (bfs(59, 3, 0))
#print (bfs(64, 94, 56))
#print (bfs(5, 62, 11))
#print (bfs(3, 93, 14))

for h in range(N):
    a, b, c = lst[h]
    bfs(a, b, c)
    #print (check)

ans = 0
ans_x = 0
ans_y = 0
for i in range(101):
    for j in range(101):
        if ans < check[i][j]:
            ans = max(ans, check[i][j])
            ans_x, ans_y = i, j

print (ans_x, ans_y, ans)
#print (check)





import sys
N = int(input())

lst = []
for i in range(N):
    a = list(map(int, input().split()))
    lst += [a]

#print (lst)


for px in range(101):
    for py in range(101):
#        print ('px, py ', px, py)
        j = 0
        while lst[j][2] == 0:
            j += 1
        h = lst[j][2] + abs(px-lst[j][0]) + abs(py -lst[j][1])
#        print ('j, h ', j, h)
        k = 0
        while k < N:
            if lst[k][2] == max(h - abs(px-lst[k][0]) - abs(py -lst[k][1]), 0):
                k += 1
#                print ('A')
            else:
#                print ('B')
                k = 10 ** 9
        if k == N:
            print (px, py, h)
            sys.exit()
        else:
            pass
#            print ('C')


Verdicts: Wrong Answer

Runtime Error

Wrong Answer

Wrong Answer

Runtime Error

Wrong Answer

Accepted