#let A be nxn array
for i in 1..n:
  for j in 1..n:

    if i == 1:
      A[i][j] = c(i, j)

    else:
      if j == 1:
        A[i][j] = c(i, j) + min(A[i-1][j], A[i-1][j+1])
      else if j == n:
        A[i][j] = c(i, j) + min(A[i-1][j-1], A[i-1][j])
      else:
        A[i][j] = c(i, j) + min(A[i-1][j-1], A[i-1][j], A[i-1][j+1])

# get minimum value for A[n][j]
min_cost = inf
min_j = None
for j in 1..n:
  if min_cost < A[n][j]:
    min_cost = A[n][j]
    min_j = j

# minimum path-recovery
min_path = [(n, min_j)]
current_min_cost = min_cost - c(n, min_j)

for i in n-1..1:
  last_j = min_path[-1][1]
  if A[i][last_j] == current_min_cost:
    new_j = last_j
  else if last_j != 1 and A[i][last_j - 1] == current_min_cost:
    new_j = last_j - 1
  else:
    new_j = last_j + 1
  min_path.append((i, new_j))
  current_min_cost -= c(i, new_j)

# reverse since nodes were added in reversed order
min_path = min_path[::-1]

# algorithm's output
print min_path