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: Wrong Answer

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

# i = 1
print(N)

# i >= 2
loop = Y - X + 1
left = X
right = N-Y+1

for i in range(2, N):
    ans = 0
    # loop
    if(loop // 2 >= i):
        if(loop/2 == i):
            ans += loop // 2
        else:
            ans += loop

    # lr only
    if(left >= i):
        ans += left - i
    if(right >= i):
        ans += right - i

    # use left
    if left >= 2:
        for j in range(1, left):
            if(loop // 2 >= i-j and i-j > 0):
                if(loop/2 == i-j or i-j == 0):
                    ans += 1
                else:
                    ans += 2
    # use right
    if right >= 2:
        for j in range(1, right):
            if(loop // 2 >= i-j and i-j > 0):
                if(loop/2 == i-j or i-j == 0):
                    ans += 1
                else:
                    ans += 2

    # use both
    if left >= 2 and right >= 2:
        if(i >= 3 and i <= left + right -1):
            if i == 3 or i == left + right - 1:
                ans += 1
            else:
                ans += 2

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, X, Y = map(int, input().split())

inf = float('inf')
d = np.array([[inf]*N for i in range(N)])

for i in range(1,N):
    d[i-1][i] = 1
d[X-1][Y-1] = 1

def warshall_floyd(d):
    for k in range(N):
        for i in range(N):
            for j in range(i+1,N):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


for i in range(N):
    d[i][i] = 0
tmp = warshall_floyd(d)

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

Submission status: Wrong Answer

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

cnt=[0 for i in range(n)]

for i in range(1,n+1):
  for j in range(i+1,n+1):
    a=min(abs(x-i),abs(y-i))
    b=min(abs(x-j),abs(y-j))
    l=min(j-i,a+b+y-x)
    cnt[l] += 1
      
for i in range(1,n):
  print(cnt[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline

N, X, Y = map(int, input().split())
skip = Y - X  - 1
ans = []

for i in range(1, N):
    for j in range(i+1, N+1):
        dist = j - i
        if i < X and j < Y:
            dist = j - i
        elif i < X and j >= X and j <= Y:
            left = j - X
            right = Y - j + 1
            if right < left:
                dist += right - left
        elif i >= X and i <= Y and j >= X and j <= Y:
            r1 = j - i
            r2 = i - X + Y - j + 1
            if r2 < r1:
                dist = r2
        elif i >= X and i < Y and j > Y:
            left2 = i - X + 1
            right2 = Y - i
            if left2 < right2:
                dist += left2 - right2
        elif i <= X and j >= Y:
            dist = j - i - skip
        ans.append(dist)
out = Counter(ans)

for i in range(1, N):
    if i in out:
        print(out[i])
    else:
        print(0)

Submission status: Wrong Answer

Solution code:
n,x,y=[int(j) for j in input().split()]
l=[[0]*n for i in range(n)]
x-=1
y-=1
s=y-x-1
for i in range(n):
    for j in range(n):
        if (i<=x and y<=j) or (j<=x and y<=i):
            l[i][j]=abs(i-j)-s
        else:
            l[i][j]=abs(i-j)

for i in range(n):
    for j in range(n):
        if i==0:
            if j==0 or j==n-1:
                continue
            l[i][j]=min(l[i][j],l[i][j+1]+1,l[i][j-1]+1,l[i+1][j]+1)
            continue
        if j==0:
            if i==0 or i==n-1:
                continue
            l[i][j]=min(l[i][j],l[i][j+1]+1,l[i+1][j]+1,l[i-1][j]+1)
            continue
        if i==n-1:
            if j==0 or j==n-1:
                continue
            l[i][j]=min(l[i][j],l[i][j+1]+1,l[i][j-1]+1,l[i-1][j]+1)
            continue
        if j==n-1:
            if i==0 or i==n-1:
                continue
            l[i][j]=min(l[i][j],l[i][j-1]+1,l[i+1][j]+1,l[i-1][j]+1)
            continue
        l[i][j]=min(l[i][j],l[i][j+1]+1,l[i][j-1]+1,l[i+1][j]+1,l[i-1][j]+1)

import numpy as np
l=np.array(l)
ans=np.bincount(l.reshape(-1,))

c=0
for i in ans[1:n]:
    c+=1
    print(i//2)

while c<n-1:
    print(0)
    c+=1

Submission status: Wrong Answer

Solution code:
INF = float('inf')
N, X, Y = map(int, input().split())
G = [[0 if i == j else INF for j in range(N)] for i in range(N)]
for i in range(N-1):
  G[i][i+1] = G[i+1][i] = 1
G[X-1][Y-1] = G[Y-1][X-1] = 1
for k in range(N):
  for i in range(N):
    for j in range(N):
      if j <= i: continue
      G[i][j] = min(G[i][j], G[i][k] + G[k][j])
for k in range(1, N):
  rk = 0
  for i in range(N):
    for j in range(N):
      if j <= i: continue
      if G[i][j] == k:
        rk += 1
  print(rk)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, X, Y = [int(x) for x in input().strip().split()]
G = np.zeros((N, N), dtype=int)
for k in range(N):
    for k2 in range(k+1, N):
        G[k, k2] = min(k2 - k, G[min(k, X-1), max(k, X-1)]+1+abs(k2 - (Y - 1)))

for k in range(1, N):
    print(sum(sum(G == k)))

Submission status: Wrong Answer

Solution code:
n,x,y=map(int,input().split())
p=[0 for i in range(n-1)]
for i in range(1,n):
    for j in range(i+1,n+1):
        if i<=x and j>=y:
            p[x-i+j-y]+=1
        else:
            if i>=x and j>=y and j-i-1>i-x+j-y:
                p[i-x+j-y]+=1
            elif i<=x and j<=y and j-i-1>x-i+y-j:
                p[x-i+y-j]+=1
            else:
                p[j-i-1]+=1
for i in p:
    print(i)

Submission status: Wrong Answer

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

from collections import defaultdict
graph = defaultdict(set)

for i in range(N-1):
  graph[i] |= {i+1}
  graph[i+1] |= {i}

graph[X-1] |= {Y-1}
graph[Y-1] |= {X-1}
MAP = [[ N for j in range(N)] for i in range(N)]
for i in range(N):
  MAP[i][i] = 0
for fr in range(N):
  for to in range(N):
    MAP[fr][to] = min(
      [MAP[fr][i]+1 for i in graph[to]]
    )
res = []
for i in MAP:
  for j in i:
    res.append(j)
from collections import Counter
c = Counter(res)
for i in range(2,N+1):
  print(c[i])

Submission status: Wrong Answer

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

cnt=[0 for i in range(n)]

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

Submission status: Wrong Answer

Solution code:

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

for k in range(1,N):

    ans = 0

    for j in range(1,N):



        p1 = j + k
        if abs(j-X) < k:
            p2 = Y - (k - abs(j-X) - 1)
        if abs(j-X) < k:
            p3 = Y + (k - abs(j-X) - 1)

        if abs(Y-p1) + 1 + abs(j-X) > k and p1<=N:
            ans += 1
            #print (j,p1)

        if abs(j-X) < k and p1 != p2 and 1 <= p2 <= N and p2 > j and abs(p2-j) > k:
            ans += 1
            #print (j,p2)

        if abs(j-X) < k and p1 != p3 and p2 != p3 and 1<=p3<=N and p3 > j and abs(p3-j) > k:
            ans += 1
            #print (j,p3)

        

    print (ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

X -= 1
Y -= 1

ans_list = [0] * (N + 1)

q = deque()

for start in range(N):
    mapped_node = [N + 10] * N
    q.append(start)
    mapped_node[start] = 0
    while len(q) > 0:
        from_node = q.popleft()
        if from_node > 0 and mapped_node[from_node - 1] >= mapped_node[from_node] + 1:
            q.append(from_node - 1)
            mapped_node[from_node - 1] = mapped_node[from_node] + 1
        if from_node < N - 1 and mapped_node[from_node + 1] >= mapped_node[from_node] + 1:
            q.append(from_node + 1)
            mapped_node[from_node + 1] = mapped_node[from_node] + 1
        if from_node == X and mapped_node[Y] >= mapped_node[from_node] + 1:
            q.append(Y)
            mapped_node[Y] = mapped_node[X] + 1
        elif from_node == Y and mapped_node[X] >= mapped_node[from_node] + 1:
            q.append(X)
            mapped_node[X] = mapped_node[Y] + 1
    for length in mapped_node:
        ans_list[length] += 1

for ans in ans_list[1:]:
    print(ans // 2)

Submission status: Wrong Answer

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

cnt=[0 for i in range(n)]

for i in range(1,n+1):
  for j in range(i+1,n+1):
    if i <= x and y <= j:
      cnt[(j-y)+(x-i)+1] += 1
    else:
      cnt[j-i] += 1
      
for i in range(1,n):
  print(cnt[i])

Submission status: Wrong Answer

Solution code:
from itertools import combinations
N,X,Y=(int(x) for x in input().split())
result=[]
for i in combinations(range(1,N+1),2):
	result.append(min(abs(i[0]-X)+abs(i[1]-Y)+1,i[1]-i[0]))
for i in range(1,N+1):
  print(result.count(i))

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict
n,x,y=map(int,sys.stdin.readline().split())
dis=defaultdict(lambda:10000)
dis[(x-1,y-1)]=1
for i in range(n):
    dis[(i,i)]=0
d=defaultdict(int)
for i in range(n-1,-1,-1):
    for j in range(i+1,n):
        dis[(i,j)]=min(dis[(i,j)],dis[(i+1,j)]+1,dis[(i,j-1)]+1,dis[(i-1,j)]+1,dis[(i,j+1)]+1)
        d[dis[(i,j)]]+=1
#print(dis,'dis')
for i in range(1,n):
    print(d[i])

Submission status: Wrong Answer

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

ans=[0 for i in range(n-1)]

a=[[abs(i-j) for i in range(n)]for j in range(n)]

for i in range(x+1):
  for j in range(y,n):
    a[i][j]=x-i+1+j-y
    
l=y-x-1
l//=2

for i in range(x+1):
  for j in range(y-l,y):
    a[i][j]=x-i+1+y-j
    
for i in range(x,x+1+l):
  for j in range(y,n):
    a[i][j]=i-x+1+j-y
    
for i in range(n-1):
  for j in range(i+1,n):
    ans[a[i][j]-1]+=1
    
#for i in range(n):
#  for j in range(n):
#    print(a[i][j],end=" ")
#  print()
    
for k in range(n-1):
  print(ans[k])

Submission status: Wrong Answer

Solution code:
n,x,y= map(int,input().split(' '))
arr=[n-i for i in range(n)]

cut= y-x
for j in range(1,x+1):
    for i in range(y,n+1):
        dist= (i-y)+1+(x-j)
        arr[dist]+=1
        arr[cut+dist-1]-=1
for a in arr[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,x,y=map(int,input().split())
d=[[n+1]*n for i in range(n)]
for i in range(n-1):
    d[i][i+1]=1
d[x-1][y-1]=1
d=warshall_floyd(d)
ans=[0]*(n+2)
for i in range(n):
    for j in range(i+1,n):
        ans[d[i][j]]+=1
for k in range(1,n):
    print(ans[k])

Submission status: Wrong Answer

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

cnt=[0 for i in range(n)]

for i in range(1,n+1):
  for j in range(i+1,n+1):
    if i <= x and y <= j:
      cnt[(j-y)-(x-i)+1] += 1
    else:
      cnt[j-i] += 1
      
for i in range(1,n):
  print(cnt[i])

Submission status: Wrong Answer

Solution code:
n,x,y=map(int,input().split())
x-=1
y-=1
d=[[0]*n for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        d[i][j]=min(j-i,abs(x-i)+abs(y-j)+1)
        
# for i in d:
#     print(i)
ans=[0]*(n+1)
for i in range(n):
    for j in range(n):
        ans[d[i][j]]+=1
for i in range(1,n+1):
    print(ans[i])

Submission status: Wrong Answer

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

R = [0 for _ in range(N - 1)]

for i in range(N - 1):
    for j in range(i + 1, N):
        res = j - i
        if i <= X <= j <= Y:
            res = min(res, Y - j + X - i + 1)
        if X <= i <= Y <= j:
            res = min(res, i - X + j - Y + 1)
        if i <= X and Y <= j:
            res = min(res, j - Y + X - i + 1)
        R[res - 1] += 1

for r in R:
    print(r)

Submission status: Wrong Answer

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

L = [0] * N

for i in range(1, X):
  L[i] = X - i

for i in range(1, N - Y + 1):
  L[i] += N - Y + 1 - i

C = Y - X - 1
for i in range(1, C):
  L[i] += C - i

for i in range(X):
  for j in range(X + 1, Y):
    k = min(j - X, Y - j + 1)
    L[i + k] += 1

for i in range(N - Y + 1):
  for j in range(X + 1, Y):
    k = min(j - X + 1, Y - j)
    L[i + k] += 1

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

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

Submission status: Wrong Answer

Solution code:
print(sorted([1,3,2]))
print(sorted([1,3,2],reverse=True))

Submission status: Wrong Answer

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

LI = [0 for _ in range(n-1)]
for i in range(1,n):
	for j in range(i+1, n+1):
		dis = min((j-i), (abs(j-y)+abs(i-x)+1))
		print([i, j, dis])
		LI[dis-1] += 1

for i in range(n-1):
	print(LI[i])

Submission status: Wrong Answer

Solution code:
n,x,y = map(int,input().split())
d = y-x-1
x -= 1
y -= 1
A = [0 for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        if i <= x and y <= j:
            A[j-i-d] += 1
        else:
            print(i,j,j-i, abs(x-i)+abs(y-j)+d+1)
            A[min(j-i, abs(x-i)+abs(y-j)+1)] += 1
        # A[min(j-i, abs(x-i)+abs(y-j)+d+1)] += 1
# print(A)
for i in range(1, n):
    print(A[i])

Submission status: Wrong Answer

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

ans = [0]*(N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if j <= X:
            ans[j-i-1] += 1
        elif i <= X:
            ans[X-i+min(1+abs(j-Y), j-X)-1] += 1
        elif i <= Y:
            ans[min(j-i, abs(j-Y)+2)-1] += 1
        else:
            ans[j-i-1] += 1
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
N, X, Y = map(int, input().split())
ans = [0 for i in range(N)]

dqs = [-1, 1]
for i in range(N-1):
  vis = [-1 for _ in range(N)]
  Q = deque([i])
  vis[i] = 0
  while Q:
    q = Q.popleft()
    for dq in dqs:
      if 0 <= q + dq < N:
      	if vis[q + dq] == -1:
          vis[q + dq] = vis[q] + 1
          Q.append(q + dq)
          if q + dq > i:
            ans[vis[q + dq]] += 1
    if q==X-1:
      if vis[Y-1] == -1:
        vis[Y-1] = vis[q] + 1
        Q.append(Y-1)
        if Y-1 > i:
          ans[vis[Y-1]] += 1
    if q==Y-1:
      if vis[X-1] == -1:
        vis[X-1] = vis[q] + 1
        Q.append(X-1)
        if X-1 > i:
          ans[vis[X-1]] += 1
for a in ans[1:]:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
graph = [[] for _ in range(n)]

for i in range(n):
  if i+1 < n:
    graph[i].append(i+1)
  if i-1 >=0:
    graph[i].append(i-1)
graph[x-1].append(y-1)
graph[y-1].append(x-1)

ans = [0] * (n-1)
from collections import deque
for i in range(n):
  dist = [-1] * n
  dist[i] = 0
  d = deque()
  d.append(i)
  while d:
    v = d.popleft()
    for j in graph[v]:
      if dist[j] != -1:
        continue
      dist[j] = dist[v] + 1
      ans[dist[j] - 1] += 1
      d.append(j)
for a in ans:
  print(a//2)

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n, x, y = i_map()
    p = [[INF]*n for i in range(n)]
    for i in range(n-1):
        p[i][i] = 0
        p[i][i+1] = p[i+1][i] = 1
    p[-1][-1] = 0

    x -= 1
    y -= 1
    p[x][y] = p[y][x] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                p[i][j] = min(p[i][j], p[i][k] + p[k][j])
    p = list(itertools.chain.from_iterable(p))
    p.sort()
    p = [i for i in p if i != 0]
    start = 1
    cnt = 0
    for i in p:
        if start != i:
            start = i
            print(cnt//2)
            cnt = 1
        else:
            cnt += 1
    print(cnt//2)
    for i in range(n-start-1):
        print(0)


if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n, x, y = i_map()
    p = [[INF]*n for i in range(n)]
    for i in range(n-1):
        p[i][i] = 0
        p[i][i+1] = p[i+1][i] = 1
    p[-1][-1] = 0

    x -= 1
    y -= 1
    p[x][y] = p[y][x] = 1

    for k in range(n):
        for i in range(n):
            for j in range(n):
                p[i][j] = min(p[i][j], p[i][k] + p[k][j])
    p = list(itertools.chain.from_iterable(p))
    for i in range(1,n):
        ans = p.count(i) // 2
        print(ans)









if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline

N,X,Y = map(int,readline().split())
G = [[] for i in range(N)]

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

ans = [0] * N

from collections import deque
for i in range(N):
  q = deque([])
  q.append([i, -1, 0])
  seen = set()
  while q:
    v, parent,cost = q.popleft()
    if v in seen:
      continue
    seen.add(v)
    ans[cost] += 1
    for child in G[v]:
      if child == parent:
        continue
      q.append([child, i, cost + 1])
      
for i in range(1, N):
  print(ans[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y=map(int,input().split())
edge=[[] for _ in range(n)]
for i in range(n-1):
    edge[i+1].append(i)
    edge[i].append(i+1)
edge[x-1].append(y-1)
edge[y-1].append(x-1)
ans=[[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    dist=[-1]*n
    dist[i]=0
    que=deque([i])
    while que:
        now=que.popleft()
        for j in edge[now]:
            if dist[j]==-1:
                dist[j]=dist[now]+1
                que.append(j)
    for j in range(n):
        ans[i][j]=dist[j]
aa=[0]*n
for i in ans:
    for j in i:
        aa[j]+=1
for i in aa[1:]:
    print(i//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import collections

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

connect=[[i-1,i+1] for i in range(1,n-1)]
connect.insert(0,[1])
connect.append([n-2])
connect[x-1].append(y-1)
connect[y-1].append(x-1)

dist_from_i = []

for i in range(0,n):
    
    d=0
    dist = [10**6]*n
    
    dq=deque()
    dq.append([i,d])
    dist[i]=d
    
    while len(dq):
        
        x,d = dq.popleft()
                
        for nextx in connect[x]:
            if d<dist[nextx]:
                dq.append([nextx,d+1])
                dist[nextx] = d+1
                
    dist_from_i.append(dist)
            
    c = collections.Counter(sum(dist_from_i,[]))

for k in range(1,n):
    print(c[k]//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n, x, y= map(int, input().split())
    x -= 1
    y -= 1
    dis = defaultdict(int)
    for i1 in range(n):
        for i2 in range(n):
            d = min(abs(i2-i1), abs(x-i1)+abs(y-i2)+1, abs(x-i2)+abs(y-i1)+1)
            dis[d] += 1

    for k1 in range(1, n):
        print(dis[k1]//2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int,input().split())
x, y = x-1, y-1
d=[0 for i in range(n)]

for i in range(n):
    for j in range(n):
        m = min(abs(i-j), abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1)
        d[m] += 1
for i in range(n-1):
    print(d[i+1]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = map(int,input().split())
next = [[] for i in range(n)]
next[0].append(1)
next[n-1].append(n-2)
next[x-1].append(y-1)
next[y-1].append(x-1)
for i in range(1,n-1):
  next[i].append(i-1)
  next[i].append(i+1)

ans = [0] *(n-1)

for j in range(n):
  mark = ['inf']*(n)
  que = deque([j])
  mark[j] = 0
 
  while que:
    q = que.popleft()
    for k in next[q]:
      if mark[k] == 'inf':
        mark[k] = mark[q] + 1
        que.append(k)
  
  for l in range(0,n):
    if mark[l] != 0:
      ans[mark[l]-1] += 1

import numpy as np    
arr = np.array(ans) //2
for x in arr:
  print(x)

Submission status: Time Limit Exceeded

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

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [sorted(dijkstra(i)[i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)

Submission status: Time Limit Exceeded

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

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [dijkstra(i) for i in range(n)]
d = [sorted(d[i][i:]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans)

Submission status: Time Limit Exceeded

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

import heapq

def dijkstra(s):
    hq = [(0, s)]
    heapq.heapify(hq) # リストを優先度付きキューに変換
    cost = [float('inf')] * n # 行ったことのないところはinf
    cost[s] = 0 # 開始地点は0
    while hq:
        c, v = heapq.heappop(hq)
        if c > cost[v]: # コストが現在のコストよりも高ければスルー
            continue
        for d, u in e[v]:
            tmp = d + cost[v]
            if tmp < cost[u]:
                cost[u] = tmp
                heapq.heappush(hq, (tmp, u))
    return cost

e = [[] for _ in range(n)]
for i in range(n-1):
    e[i].append((1, i+1))
    e[i+1].append((1, i)) # 有向グラフでは削除
e[x-1].append((1, y-1))
e[y-1].append((1, x-1))

d = [dijkstra(i) for i in range(n)]
d = [sorted(d[i]) for i in range(n)]

import bisect

for i in range(1,n):
    ans = 0
    for j in range(n):
        ans += bisect.bisect_right(d[j], i) - bisect.bisect_left(d[j], i)
    print(ans // 2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = [int(_) for _ in input().split()]

INF = 10 ** 9
dp = [[INF] * N for _ in range(N)]

for i in range(N - 1):
    dp[i][i + 1] = 1
    dp[i+1][i] = 1

dp[X - 1][Y - 1] = 1
dp[Y - 1][X - 1] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            # k経由でiからjへ
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

cnt = [0] * N
for i in range(N):
    for j in range(i+1, N):
        v = dp[i][j]
        cnt[v]+=1
for i in range(1,N):
    print(cnt[i])

Submission status: Time Limit Exceeded

Solution code:
import networkx as nx
n,x,y=map(int,input().split())
g=nx.Graph()
for p in range(1,n):
     g.add_edge(p,p+1)
g.add_edge(x,y)

l=[0]*n
for q in nx.all_pairs_shortest_path_length(g):
     for j in range(1,n+1):
          l[q[1][j]]+=1
for w in range(1,len(l)):
     print(l[w]//2)

Submission status: Time Limit Exceeded

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

ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(i+1, N):
        tmp1 = abs(i - X + 1) + abs(j - Y + 1) + 1
        tmp2 = abs(i - Y + 1) + abs(j - X + 1) + 1
        min_dist = min(abs(i - j), tmp1, tmp2)

        ans[min_dist - 1] += 1

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

Submission status: Time Limit Exceeded

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

dist = [[0 for _ in range(N)] for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(i, N):
        tmp1 = abs(i - X + 1) + abs(j - Y + 1) + 1
        tmp2 = abs(i - Y + 1) + abs(j - X + 1) + 1
        min_dist = min(abs(i - j), tmp1, tmp2)

        ans[min_dist - 1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dist = [[0 for _ in range(N)] for _ in range(N)]
ans = [0 for _ in range(N)]

for i in range(N):
    for j in range(N):
        tmp1 = abs(i - X + 1) + abs(j - Y + 1) + 1
        tmp2 = abs(i - Y + 1) + abs(j - X + 1) + 1

        dist[i][j] = min(abs(i - j), tmp1, tmp2)
        dist[j][i] = min(abs(i - j), tmp1, tmp2)

for i in range(N):
    for j in range(i+1, N):
        ans[dist[i][j]-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(n: int, graph: list) -> list:
    d = deque([n])
    check = [-1 for _ in range(N)]
    check[n] = 0
    while d:
        e = d.popleft()
        for i in range(N):
            if (graph[e][i]) == 1 and check[i] == -1:
                check[i] = 1 + check[e]
                d.append(i)
    return check


dist = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if abs(i - j) == 1:
            dist[i][j] = 1

dist[X-1][Y-1] = 1
dist[Y-1][X-1] = 1

ans = [0 for _ in range(N - 1)]
for i in range(N):
    tmp = bfs(i, dist)
    for j in range(i):
        ans[tmp[j]-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(n: int, graph: list) -> list:
    d = deque([n])
    check = [-1 for _ in range(N)]
    check[n] = 0
    while d:
        e = d.popleft()
        for i in range(N):
            if (graph[e][i]) == 1 and check[i] == -1:
                check[i] = 1 + check[e]
                d.append(i)
    return check


dist = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if abs(i - j) == 1:
            dist[i][j] = 1

dist[X-1][Y-1] = 1
dist[Y-1][X-1] = 1

ans = [0 for _ in range(N - 1)]
for i in range(N):
    tmp = bfs(i, dist)
    for j in range(i):
        ans[tmp[j]-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
n, x, y = map(int, input().split())

adj = [[] for i in range(n)]
for i in range(1, n):
    adj[i].append(i-1) 
    adj[i-1].append(i)
adj[x-1].append(y-1)
adj[y-1].append(x-1)
d = [[30**3]*n for i in range(n)]
def bfs(s):
    q = Queue()
    d[s][s] = 0
    q.put(s)
    while not q.empty():
        c = q.get()
        #print (s, c, d[s][c])
        for a in adj[c]:
            if d[s][a] > d[s][c] + 1:
                d[s][a] = d[s][c] + 1
                q.put(a)
for i in range(n):
    bfs(i)
    #print()
ks = [0]*n
for i in range(n):
    for j in range(n):
        if d[i][j] < n:
            ks[d[i][j]] += 1
for i in range(1, n):
    print (ks[i]//2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = [int(n) for n in input().split(" ")]

X = X - 1
Y = Y - 1

D = {}
for i in range(N):
    D[i] = []

for i in range(N):
    if i != N - 1:
        D[i].append(i + 1)
        if i != 0:
            D[i].append(i - 1)
    else:
        D[i].append(i - 1)

D[X].append(Y)
D[Y].append(X)


def search(start):
    queue = [start]
    depth = 0
    dic = {start: 0}

    while len(queue) > 0:
        depth += 1
        nextQueue = []
        while len(queue) > 0:
            now = queue[0]
            del(queue[0])
            neighbors = D[now]
            for n in neighbors:
                if n not in dic:
                    nextQueue.append(n)
                    dic[n] = depth
        queue = nextQueue
    return dic
    
lenD = []
for i in range(N):
    d = search(i)
    lenD.append(d)

kcounter = [0 for _ in range(N - 1)]

for i in range(N):
    for j in range(i + 1, N):
        k = lenD[i][j]
        kcounter[k - 1] += 1

for k in kcounter:
    print(k)