Problem:


Score : 400 points

Problem Statement

We have an undirected graph G with N vertices numbered 1 to N and N edges as follows:

For each i=1,2,...,N-1, there is an edge between Vertex i and Vertex i+1.

There is an edge between Vertex X and Vertex Y.

For each k=1,2,...,N-1, solve the problem below:

Find the number of pairs of integers (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j in G is k.

Constraints

3 \leq N \leq 2 \times 10^3

1 \leq X,Y \leq N

X+1 < Y

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X Y

Output

For each k=1, 2, ..., N-1 in this order, print a line containing the answer to the problem.

Sample Input 1

5 2 4

Sample Output 1

5
4
1
0

The graph in this input is as follows:

There are five pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 1: (1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5).

There are four pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 2: (1,3)\,,(1,4)\,,(2,5)\,,(3,5).

There is one pair (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 3: (1,5).

There are no pairs (i,j) (1 \leq i < j \leq N) such that the shortest distance between Vertex i and Vertex j is 4.

Sample Input 2

3 1 3

Sample Output 2

3
0

The graph in this input is as follows:

Sample Input 3

7 3 7

Sample Output 3

7
8
4
2
0
0

Sample Input 4

10 4 8

Sample Output 4

10
12
10
8
4
1
0
0
0



Sample input:
5 2 4


Sample output:
5
4
1
0

Submission status: Runtime Error

Solution code:
N,X,Y=map(int,input().split())
ans=0
right=X-1
cycle=Y-X+1
left=N-Y
import copy
ring=copy.copy(cycle)
branchr=copy.copy(right)
if right>0:
    branchr+=1
branchl=copy.copy(left)
if left>0:
    branchl+=1
ring_branchr=0
ring_branchl=0
branchrl=0
count=0
if cycle%2==0:
    for k in range(1,max(left+cycle//2,right+cycle//2,left+right+1)+1):
        if k==cycle//2:
            ring = cycle//2
        if k>cycle//2:
            ring = 0
        if right>0:
            branchr-=1
            if k>right:
                branchr=0
        if left>0:
            branchl-=1
            if k>left:
                branchl=0
        if right>0:
            ring_branchr=min(2*(k-1),right*2)
            if k>cycle//2:
                ring_branchr-=2*(k-cycle//2)-1
            if ring_branchr<0:
                ring_branchr=0
        if left>0:
            ring_branchl=min(2*(k-1),left*2)
            if k>cycle//2:
                ring_branchl-=2*(k-cycle//2)-1
            if ring_branchl<0:
                ring_branchl=0
        if right>0 and left>0:
            if k ==3:
                branchrl=1
            if 3<k<right+left+1:
                branchrl=min(k-2,right,left)
            if k==right+left+1:
                branchrl=1
            if k>right+left+1:
                branchrl=0
        ans=ring+branchr+branchl+ring_branchr+ring_branchl+branchrl
        print(ans)
        count+=1
if cycle%2==1:
    for k in range(1,max(left+cycle//2,right+cycle//2,left+right+1)+1):
        if k>cycle//2:
            ring = 0
        if right>0:
            branchr-=1
            if k>right:
                branchr=0
        if left>0:
            branchl-=1
            if k>left:
                branchl=0
        if right>0:
            ring_branchr=min(2*(k-1),right*2)
            if k>cycle//2+1:
                ring_branchr-=2*(k-cycle//2-1)
            if ring_branchr<0:
                ring_branchr=0
        if left>0:
            ring_branchl=min(2*(k-1),left*2)
            if k>cycle//2+1:
                ring_branchl-=2*(k-cycle//2-1)
            if ring_branchl<0:
                ring_branchl=0
        if right>0 and left>0:
            if k ==3:
                branchrl=1
            if 3<k<right+left+1:
                branchrl=(k-2,right,left)
            if k==right+left+1:
                branchrl=1
            if k>right+left+1:
                branchrl=0
        ans=ring+branchr+branchl+ring_branchr+ring_branchl+branchrl
        print(ans)
        count+=1
for k in range(count+1,N):
    print(0)

Submission status: Runtime Error

Solution code:
import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    N,X,Y = map(int,input().split())

    d = [ [ 0 for j in range(N) ] for i in range(N) ]
    d = np.array(d)

    for i in range(N-1):
        for j in range(i,N):
            temp1 = abs(j-i)
            temp2 = abs(X-i) + 1 + abs(j-Y)
            temp3 = abs(Y-i) + 1 + abs(j-X)
            d[i,j] = min(tem1,temp2,temp3)

    for k in range(1,N):
        res = np.count_nonzero(d == k)
        print(res)



main()

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())
x -= 1
y -= 1

ans = [0] * n
for i in range(n):
    for j in range(i + 1, n):
        d = min(abs(i - j),
                abs(i - x) + 1 + abs(y - j),
                abs(i - y) + 1 + abs(x - j))
        ans[dist[i][j]] += 1

for k in range(1, n):
    print(ans[k])

Submission status: Runtime Error

Solution code:
n = list(map(int,input().split()))
for i in range(1,n[0]+1):
    for j in range(1,n[0]+1):
        ans = [abs(j-1),abs(n[1]-i)+1+abs(j-n[2]),abs(n[2]-i)+1+abs(j − n[1])]
        print(min(ans))

Submission status: Runtime Error

Solution code:
from collections import Counter

n, x, y = map(int, input().split())

ans = [0]*((10**3)*3)
counter = 0
for i in range(n-1):
    for j in range(i+1,n):
        # ショートカットできない場合
        # print(i,j)
        if j < x:
            temp = j-i
            ans[counter] = temp
        else:
            shortcut = abs((x-1) - i) + 1 + abs((y-1) -j )
            not_shortcut = j-i
            temp = min(shortcut,not_shortcut)
            ans[counter] = temp
        counter+=1
        # print(temp)

for i in range(1,n):
    print(ans.count(i))

Submission status: Runtime Error

Solution code:
n,x,y=map(int, input().split())

ans=[0]*n-1

for i in range(n):
    for j in range(n):
        ans[min(j-i, abs(x-i)+1+abs(j-y), abs(y-i)+1+abs(j-x))]+=1

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N, X, Y = list(map(int, input().split()))
res = [0] * (n-1)
for i in range(1, N + 1):
    for j in range(1, N + 1):
        if i >= j:
            continue
        if i == X and Y == j:
            key = 1
        else:
            key = int(min(j - i, abs(X - i) + abs(Y - j) + 1))
        res[key] += 1

for i in range(1, N):
    print(res[i])

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())

ans = {}
for i in range(n-1):
  ans[i+1] = 0
  
for i in range(n):
  for j in range(i+1,n):
    if i <= x-i:
      if j <= x-1:
      	t=j-i
      	ans[t] += 1
      elif j <= y-1:
      	t = min(j-i, (x-1)-i + 1 + (y-1) -j)
      	ans[t] += 1
      else: #j > y-1
      	t = (x-1)-i + 1 + j -(y-1)
      	ans[t] += 1
    elif i < y-1:
      if j < y-1:
      	t = min(j-i, i-(x-1) + 1 + (y-1) -j)
      	ans[t] += 1
      else: #j >= y-1:
      	t = min(j-i, i-(x-1) + 1 + j - (y-1))
      	ans[t] += 1
    elif i >= y-1:
      t=j-i
      ans[t] += 1
    else:
      print("error")

for i in range(1,n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
a = b

Submission status: Runtime Error

Solution code:
def find_shortest_path(graph, start, end, path=[]):
    path = path + [start]
    if start == end:
        return path
    if not start in graph.keys():
        return None
    shortest = None
    for node in graph[start]:
        if node not in path:
            newpath = find_shortest_path(graph, node, end, path)
            if newpath:
                if not shortest or len(newpath) < len(shortest):
                    shortest = newpath
    return shortest


n,x,y=map(int,input().split())
g={}
d=[]
for i in range(n):
    g[i+1]=[]
    d.append(0)
    if i>0:
        g[i+1].append(i)
    if i!=n-1:
        g[i+1].append(i+2)

g[x].append(y)
g[y].append(x)

for i in range(n):
    for j in range(i+1,n):
        p=find_shortest_path(g,i+1,j+1)
        d[len(p)-1]+=1
for i in range(n-1):
    print (d[i+1])

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())
x = x-1
y = y-1

result = [0] * n
for i in range(n):
    for j in range(i, n, 1):
        if i == j:
            continue
        minij = min([(j - i - 1), ((x - i + 1) + (y - j) - 1)])
        result[minij] += 1
for i in range(n-1):
    print(result[i])

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split(' '))

dct = {X : Y}
short = Y - X - 1

dist_list = [0] * N

for i in range(1,N):
    for j in range(i+1,N+1):
        d1 = abs(X - i) + 1 + abs(Y - j)
        d2 = j - i
        dist = min(d1,d2)
        dist_list[dist] += 1

for k in range(1,N):
    print(dist[k])

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())

ans = {}
for i in range(n-1):
  ans[i+1] = 0
  
for i in range(n):
  for j in range(i+1,n):
    if i <= x-i:
      if j <= x-1:
      	t=j-i
      	ans[t] += 1
      elif j <= y-1:
      	t = min(j-i, (x-1)-i + 1 + (y-1) -j)
      	ans[t] += 1
      else: #j > y-1
      	t = (x-1)-i + 1 + j -(y-1)
      	ans[t] += 1
    elif i < y-1:
      if j < y-1:
      	t = min(j-i, i-(x-1) + 1 + (y-1) -j)
      	ans[t] += 1
      else: #j >= y-1:
      	t = min(j-i, i-(x-1) + 1 + j - (y-1))
      	ans[t] += 1
    elif i >= y-1:
      t=j-i
      ans[t] += 1
    else:
      print("error")

for i in range(1,n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())

ans = {}
for i in range(n-1):
  ans[i+1] = 0
  
for i in range(n):
  for j in range(i+1,n):
    if i <= x-i:
      if j <= x-1:
      	t=j-i
      	ans[t] += 1
      elif j <= y-1:
      	t = min(j-i, (x-1)-i + 1 + (y-1) -j)
      	ans[t] += 1
      else: #j > y-1
      	t = (x-1)-i + 1 + j -(y-1)
      	ans[t] += 1
    elif i < y-1:
      if j < y-1:
      	t = min(j-i, i-(x-1) + 1 + (y-1) -j)
      	ans[t] += 1
      elif j >= y-1:
      	t = min(j-i, i-(x-1) + 1 + j - (y-1))
      	ans[t] += 1
    elif i >= y-1:
      t=j-i
      ans[t] += 1
    else:
      print("error")

for i in range(1,n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import numpy as np

N, X, Y = list(map(int, input().split()))
A = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    A[i][i + 1] = 1
    A[i+1][i] = 1
A[X - 1][Y - 1] = 1
A[Y - 1][X - 1] = 1

D = [(i, j) for i in range(N) for j in range(N) if i<j]

A = np.array(A)

a = np.identity(N)
for i in range(N-1):
    r = 0
    tmp = []
    a = np.matmul(a, A)
    for (i, j) in D:
        if a[i][j] > 0:
            r += 1
        else:
            tmp.append((i, j))
    D = tmp
    print(r)

Submission status: Runtime Error

Solution code:
from collections import Counter
N, X, Y = map(int, input().split())
ans = []

for i in range(N):
    for j in range(i+1, N):
        ans.append(min(j-i, 1+abs(i-x)+abs(j-Y)))

c = Counter(ans)
for i in range(1,N):
    print(c[i])

Submission status: Runtime Error

Solution code:
import numpy as np

N, X, Y = list(map(int, input().split()))
A = [[0 for _ in range(N)] for _ in range(N)]

for i in range(N-1):
    A[i][i + 1] = 1
    A[i+1][i] = 1
A[X - 1][Y - 1] = 1
A[Y - 1][X - 1] = 1

D = [(i, j) for i in range(N) for j in range(N) if i<j]

A = np.array(A)

a = np.identity(N)
for i in range(N-1):
    r = 0
    tmp = []
    a = np.matmul(a, A)
    for (i, j) in D:
        if a[i][j] > 0:
            r += 1
        else:
            tmp.append((i, j))
    D = tmp
    print(r)

Submission status: Runtime Error

Solution code:
import math

N, x, y = list(map(int, input().split()))
INF = math.inf
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  # print("i", i)
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Submission status: Runtime Error

Solution code:
import heapq
n,X,Y = map(int,input().split())

def dijkstra_heap(s,edge):
    d=[10**20]*n
    used = [True]*n
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
E = []
for i in range(n-1):
    E.append([i,i+1,1])
E.append([X-1,Y-1,1])

edge = [[] for i in range(n)]
for i in range(w):
    for e in E:
        x,y,z = map(int,e)
        edge[x].append([z,y])
        edge[y].append([z,x])

for i in range(1,n):
    cnt = 0
    for j in range(n):
        tmp = dijkstra_heap(j,edge)
        for t in tmp[j:]:
            if t==i:
                cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
N, x, y = list(map(int, input().split()))
import math
INF = math.inf
adj_mtx = [ [INF] * (N+1) for _ in range(N+1) ]

for i in range(1, N+1):
  if i != N:
    adj_mtx[i][i] = 0
    adj_mtx[i][i+1] = 1
    adj_mtx[i+1][i] = 1
adj_mtx[x][y] = 1
adj_mtx[y][x] = 1

for k in range(1, N+1):
  for i in range(1, N+1):
    for j in range(1, N+1):
      if i == 1 and j == 6 and k == 7: import pdb; pdb.set_trace()
      adj_mtx[i][j] = min(adj_mtx[i][j], adj_mtx[i][k] + adj_mtx[k][j])

for i in range(1, N):
  print(sum([ r.count(i) for r in adj_mtx ]) // 2)

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split(' '))
distance = [0] * N - 1
for i in range(N-1):
  for j in range(1, N):
    if i >= Y or j <= X:
      distance[j - i - 1] += 1
    elif i <= X and j >= Y:
      distance[j - Y + X - i - 1] += 1
    else:
      distance[j-Y + X-i - 1] += 1

for d in distance:
  print(d)

Submission status: Runtime Error

Solution code:
N, X, Y = map(int, input().split(' '))
distance = [0] * N - 1
for i in range(N-1):
  for j in range(1, N):
    if i >= Y or j <= X:
      distance[j - i = 1] += 1
    elif i <= X and j >= Y:
      distance[j - Y + X - i - 1] += 1
    else:
      distance[j-Y + X-i - 1] += 1

for d in distance:
  print(d)

Submission status: Runtime Error

Solution code:
import math

def get_target_min_index(min_index, distance, unsearched_nodes):
  start = 0
  while True:
    index = distance.index(min_index, start)
    found = index in unsearched_nodes
    if found:
      return index
    else:
      start = index + 1


n, x, y = map(int, input().split())

graph = [[0] * n for i in range(n)]
ans = [0] * n

for i in range(n - 1):
  graph[i][i + 1] = 1
  graph[i + 1][i] = 1

graph[x - 1][y - 1] = 1
graph[y - 1][x - 1] = 1
# print(graph)

for j in range(n - 1):
  node_num = len(graph)

  unsearched_nodes = list(range(node_num))
  distance = [math.inf] * node_num
  previous_nodes = [-1] * node_num
  distance[j] = 0 

  while(len(unsearched_nodes) != 0): #未探索ノードがなくなるまで繰り返す
      posible_min_distance = math.inf
      for node_index in unsearched_nodes:
          if posible_min_distance > distance[node_index]: 
              posible_min_distance = distance[node_index]
      target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes)
      unsearched_nodes.remove(target_min_index)

      target_edge = graph[target_min_index]
      for index, route_dis in enumerate(target_edge):
          if route_dis != 0:
              if distance[index] > (distance[ target_min_index] + route_dis):
                  distance[index] = distance[ target_min_index] + route_dis
                  previous_nodes[index] =  target_min_index


  del distance[:(j + 1)]

  for i in range(n - 1):
    ans[i] += distance.count(i + 1)

  # print(distance)
# print(ans)

for i in range(len(ans) - 1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    n,x,y=INTM()
    z=y-x
    sc=y-x-1
    loop=y-x+1
    maxl=(n)-(y-x)
    for i in range(1,n):
        ct=0
        if ct==0:
            for j in range(1,n):
                if j+i<=x or j>=y:
                    if j+i<=n:
                        ct+=1
                else:
                    if j<=x:
                        if j+i+sc<=n:
                            ct+=1
                        temp=i-(x-j)
                        if temp>=2:
                            if loop>temp*2:
                                ct+=2
                            elif loop==temp*2:
                                ct+=1
                        else:
                            ct+=1
                        
                    else:
                        lpmin=min(y-j,+(j-x+1))
                        if lpmin==j-x+1:
                            if lpmin==y-j:
                                if lpmin+(n-y)>=i:
                                    ct+=1
                            else:
                                if lpmin>i:
                                    ct+=1
                                else:
                                    if lpmin+(n-y)>=i:
                                        ct+=1
                                    if loop>i*2:
                                        ct+=
                                    elif loop==i*2:
                                        ct+=1
                        else:
                            if lpmin+(n-y)>=i:
                                ct+=1
                print(ct)
            print(ct)        
        else:
            print(ct)
                
        
if __name__ == '__main__':
    do()

Submission status: Runtime Error

Solution code:
n,x,y=map(int, input().split())

ans=[0]*(n-1)

def func2(np, nd, state):
    #print(np, nd, state)
    nxp=[]
    for p in np:
        if p > 0 and not state[p-1]:
            nxp.append(p-1)
            ans[nd]+=1
        if p < n-1 and not state[p+1]:
            nxp.append(p+1)
            ans[nd]+=1
        if p == x-1 and not state[y-1]:
            nxp.append(y-1)
            ans[nd]+=1
        if p == y-1 and not state[x-1]:
            nxp.append(x-1)
            ans[nd]+=1
#    if nd == 1:
#        print(nd, nxp)

    nxp=list(set(nxp))
    for i in nxp:
        state[i]=True
    if len(nxp) == 0:
        return
    else:
        func2(nxp, nd+1, state)

for i in range(n):
    st=[False]*n
    st[i]=True
    func2([i], 0, st)

for i in ans:
    print(i//2)

Submission status: Runtime Error

Solution code:
# import math
# import sys
# A, B = [int(i) for i in input().split()]
# for i in range(math.ceil(12.5 * A), math.ceil(12.5 * (A + 1))):
#     if math.floor(i//10) == B:
#         print(i)
#         sys.exit()
# print(-1)

# x = int(input())
# s, a = divmod(x, 500)
# print(s*1000 + (a // 5)*5)

# k, n = [int(i) for i in input().split()]
# a = [int(i) for i in input().split()]
# maxx = 0
# key = 0
# for i in range(0, n):
#   if i == n-1:
#     key = (k + a[0]) - a[i]
#   else:
#     key = a[i+1] - a[i]
#   if maxx < key:
#     maxx = key
# print(k - maxx)

n, x, y = [int(i) for i in input().split()]
p = y - x + 1
a = x - 1
b = n - y
print(n)
ans2 = n - (y - x) + 1
if 2 < p/2:
    ans2 += p
elif 2 == 2/p:
    ans2 += 2
print(ans2)
for k in range(3, n):
    ans = 0
    main = 0
    eda1 = 0
    eda2 = 0
    if p % 2 == 1:
        if k <= p // 2:
            main = n - (y - x) - k + 1
            eda1 = min(a, (k - 1)) * 2
            eda2 = min(b, (k - 1)) * 2
            ans = p + main + eda1 + eda2
        else:
            main = n - (y - x) - k + 1
            if k - (p//2) > a:
                eda1 = 0
            else:
                eda1 = min(a - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            if k - (p//2) > b:
                eda2 = 0
            else:
                eda2 = min(b - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            ans = main + eda1 + eda2 - 2
    else:
        if k < p // 2:
            main = n - (y - x) - k + 1
            eda1 = min(a, (k - 1)) * 2
            eda2 = min(b, (k - 1)) * 2
            ans = p + main + eda1 + eda2
        elif k == p // 2:
            main = n - (y - x) - k + 1
            if k - (p//2) > a:
                eda1 = 0
            else:
                eda1 = min(a - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            if k - (p//2) > b:
                eda2 = 0
            else:
                eda2 = min(b - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            ans = p//2 +main + eda1 + eda2 - 2
        else:
            main = n - (y - x) - k + 1
            if k - (p//2) > a:
                eda1 = 0
            else:
                eda1 = min(a - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            if k - (p//2) > b:
                eda2 = 0
            else:
                eda2 = min(b - (k - (p//2)) + 1, k - (p//2) + 1) * 2
            ans = main + eda1 + eda2 - 2
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,x,y = map(int, input().split())
s = np.zeros((n,n))
t = np.zeros(n)
for i in range(0,n):
  for j in range(i,n):
    s[i][j] = abs(i-j)
x = x-1
y = y-1
s[x][y] = 1
for i in range(0,n):
  for j in range(i,n):
    a = abs(i-x)+abs(j-y)+1
    if a < s[i][j];
    s[i][j] = a

for i in range(0,n):
  for j in range(i,n):
    for k in range(0.n):
      if k+1 == s[i][j]:
        t[k+1] += 1

for k in range(0.n):
  print t[k]

Submission status: Runtime Error

Solution code:
import string
def num():
    return int(input())
def nums():
    return list(map(int,input().split()))

N,X,Y = nums()

class Node:
    def __init__(self,id):
        self.id = id
        self.to_node = []
        self.from_node = []
    def edge_to(self,node):
        self.to_node.append(node)
        node.from_node.append(self)


def _get_distance(start,goal,res=0,already=set()):
    global N
    if start.id == goal.id:
        return res
    candidate = set()
    already.add(start.id)
    for to in start.to_node + start.from_node:
        if to.id in already:continue
        already.add(to.id)
        if to.id == goal.id:
            return res+1
        candidate.add(get_distance(to,goal,res+1,already))
    return N*2 if len(candidate) == 0 else min(candidate)



def get_distance(start,goal,res=0,already=set()):
    global N
    if start.id == goal.id:
        return res
    answers = set({N*2})
    already.add(start.id)
    for next_node in (start.from_node + start.to_node):
        if not (next_node.id in already):
            answers.add(get_distance(next_node,goal,res+1,already))
        else:
            continue

    return min(answers)



nodes = [Node(i) for i in range(1,N+1)]

for i in range(N-1):
    nodes[i].edge_to(nodes[i+1])
nodes[X-1].edge_to(nodes[Y-1])

ans = {}

for start_node_idx in range(N):
    for goal_node_idx in range(N):
        if goal_node_idx > start_node_idx:
            start_node = nodes[start_node_idx]
            goal_node = nodes[goal_node_idx]

            distance = get_distance(start_node, goal_node,already=set())
            print("distance between",start_node.id,"and",goal_node.id,"is",distance)

            if ans.get(distance):
                ans[distance] += 1
            else:
                ans[distance] = 1
for k in range(1,N):
    if ans.get(k):
        print(ans[k])
    else:
        print(0)

Submission status: Runtime Error

Solution code:
NXY = list(map(int, input().split()))
N, X, Y = NXY[0], NXY[1], NXY[2]


def flatten_2dim(array):
    return [item for sublist in array for item in sublist]


dp = []
for i in range(N):
    dp.append([])
    for j in range(N):
        if j < i:
            dp[i].append(0)
        else:
            dp[i].append(j-i)

for i in range(int(N*0.5)):
    for j in range(int(N*0.5)):
        if i == 0 and j == 0:
            dp[X-1][Y-1] = 1
        else:
            dp[X-1-i][Y-1-j] = min(1+i+j, dp[X-1-i][Y-1-j])
            dp[X-1+i][Y-1-j] = min(1+i+j, dp[X-1+i][Y-1-j])
            dp[X-1-i][Y-1+j] = min(1+i+j, dp[X-1-i][Y-1+j])
            dp[X-1+i][Y-1+j] = min(1+i+j, dp[X-1+i][Y-1+j])
print(dp)
for k in range(1, N):
    print(flatten_2dim(dp).count(k))

Submission status: Runtime Error

Solution code:
import heapq
n,X,Y = map(int,input().split())

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

E = []
for i in range(n-1):
    E.append([i,i+1,1])
E.append([X-1,Y-1,1])

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    for e in E:
        x,y,z = map(int,e)
        edge[x].append([z,y])
        edge[y].append([z,x])

for i in range(1,n):
    cnt = 0
    for j in range(n):
        tmp = dijkstra_heap(j,edge)
        for t in tmp[j:]:
            if t==i:
                cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
import collections
n,x,y=map(int,input().split())
import heapq
class Dijkstra:

    def __init__(self, rote_map, start_point, goal_point=None):
        self.rote_map = rote_map
        self.start_point = start_point
        self.goal_point = goal_point

    def execute(self):
        num_of_city = len(self.rote_map)
        dist = [float("inf") for _ in range(num_of_city)]
        prev = [float("inf") for _ in range(num_of_city)]

        dist[self.start_point] = 0
        heap_q = []
        heapq.heappush(heap_q, (0, self.start_point))
        while len(heap_q) != 0:
            prev_cost, src = heapq.heappop(heap_q)

            if dist[src] < prev_cost:
                continue

            for dest, cost in self.rote_map[src].items():
                if cost != float("inf") and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost
                    heapq.heappush(heap_q, (dist[dest], dest))
                    prev[dest] = src
        if self.goal_point is not None:
            return self.get_path(self.goal_point, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        path = [goal]
        dest = goal

        while prev[dest] != float("inf"):
            path.append(prev[dest])
            dest = prev[dest]

        return list(reversed(path))

route_map = [dict() for _ in range(n)]
route_map[x-1][y-1]=1
route_map[y-1][x-1]=1
for i in range(n-1):
    route_map[i][i+1] = 1
    route_map[i+1][i]=1    
lst=[]
for i in range(n):
    lst+=Dijkstra(route_map,i).execute()//2        
Lst=list(collections.Counter(lst).items())
Key=list(collections.Counter(lst).keys())
m=max(Key)
for i in range(1,m+1):
    print(Lst[i][1])
for i in range(m+1,n):
    print(0)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	long long n,x,y;
	cin>>n>>x>>y;
	x--;
	y--;
	long long sp[n];
	for(long long i=0; i<n; i++)
	{
		sp[i] = 0;
	}
	for(long long i=0; i<n; i++)
	{
		for(long long j=0; j<n; j++)
		{
			long long dis;
			long long loc;
			if(i<=j){
				
			if(i==j)
			{
				dis = 0;
			}
			else if(i==j-1)
			{
				dis = 1;
				sp[0]++;
			}
			else if((i<=x||j>=y)||(j<=x||i>=y))
			{
				if(i<=x)
				{
					if(j<y)
					{
						if((1+x+y-i-j)<(j-i))dis=1+x+y-i-j;
						else dis = j-i;
					}
					else if(j>=y)
					{
						dis = 1+x+j-i-y;
					}
					loc = abs(dis-1);
					sp[loc]++;
				}
				else if(j>=y)
				{
					if(i>x)
					{
						if((1+i+j-x-y)<(j-i))dis = 1+i+j-x-y;
						else dis = j-i;
					}
					loc = abs(dis-1);
					sp[loc]++;
				}
			}
			else
			{
				if(j>i)
				{
					dis = j - i;
					loc = abs(dis-1);
					sp[loc]++;
				}
			}
			
		}
		}
	}
	
	for(long long i = 0; i<n-1; i++)
	{
		cout << sp[i] << '\n';
	}
}

Submission status: Runtime Error

Solution code:
n, x, y = map(int, input().split())
edge = [[] for _ in range(n+1)]
dist = [[abs(i-j) for i in range(n)] for j in range(i+1,n+1)]
counter = [0 for i in range(n)]
for i in range(1, n):
    edge[i].append(i+1)
    edge[i+1].append(i)
edge[x].append(y)
edge[y].append(x)
for i in range(y+1):
    for j in range(x, n+1):
        new_dist = abs(x-i)+abs(y-j)+1
        if new_dist < dist[i][j]:
            dist[i][j] = new_dist

for i in range(1, n+1):
    for num in dist[i][1:]:
        counter[num] += 1
# print(dist)

for num in counter[1:]:
    print(num)

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
red_eat_num, green_eat_num, red_total, green_total, no_total = map(int, input().split())

red = list(map(int, input().split()))
green = list(map(int, input().split()))
no = list(map(int, input().split()))

red = sorted(red, reverse=True)
green = sorted(green, reverse=True)
no= sorted(no, reverse=True)

count_x = 0
count_y = 0
pointaA = 0
pointaB = 0
pointaC = 0
total_red = 0
total_green = 0
flag_red = 0
flag_green = 0

while 1:
    count_x = count_x + 1
    if count_x > red_eat_num:
        break
    
    if flag_red == 1:
        total_red = total_red + no[pointaC]
        pointaC = pointaC + 1
    elif flag_red == 2:
        total_red = total_red + red[pointaA]
        pointaA = pointaA + 1
    else: 
        if red[pointaA] >= no[pointaC]:
            total_red = total_red + red[pointaA]
            pointaA = pointaA + 1
            if pointaA >= red_total:
                flag_red = 1
        else:
            total_red = total_red + no[pointaC]
            pointaC = pointaC + 1
            if pointaA >= no_total:
                flag_red = 2
    
# print(total_red)

if flag_red == 2:
    flag_green == 2

while 1:
    count_y = count_y + 1
    if count_y > green_eat_num:
        break
    if flag_green == 1:
        total_green = total_green + no[pointaC]
        pointaC = pointaC + 1
    elif flag_green == 2:
        total_green = total_green + green[pointaB]
        pointaB = pointaB + 1
    else:
        if green[pointaB] >= no[pointaC]:
            total_green = total_green + green[pointaB]
            pointaB = pointaB + 1
            if pointaB >= green_total:
                flag_green = 1
        else:
            total_green = total_green + no[pointaC]
            pointaC = pointaC + 1
            if pointaC >= no_total:
                flag_green = 2
    
# print(total_green)
        
print(total_red + total_green)