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: Time Limit Exceeded

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

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

for k in range(N-1):
    print(dist_list.count(k+1))

Submission status: Time Limit Exceeded

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

for i in range(N):
    for j in range(i+1, N):
        if i+1 <= X and j+1 >= Y:
            dist_list.append(j - Y + X - i + 1)
        else:
            dist_list.append(min(j - i, abs(i+1 - X) + abs(j+1 -Y) + 1))

for k in range(N-1):
    print(dist_list.count(k+1))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = list(map(int,input().split()))
 
distance_list =[]
 
for i in range(1,n):
    for j in range(i+1,n+1):
        a = j - i
        b = abs(i - x) + abs(j-y) + 1
        distance_list.append(min(a,b))
count_list = []
 
for i in range(n-1):
    count_list.append(distance_list.count(i+1))
    
for i in range(n-1):
    print(count_list[i])

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
li = [0]*(N-1)
for i in range(0,N-1):
    for j in range(i+1,N):
        dis = min(j-i,abs(j-(X-1))+1+abs(i-(Y-1)),abs(i-(X-1))+1+abs(j-(Y-1)))
        li[dis-1] += 1
for ans in li:
    print(ans)

Submission status: Time Limit Exceeded

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

ans = [0 for i in range(n)]
for s in range(n) :
  for g in range(s,n) :
    if s == g :
      continue
    dis = min(abs(g-s),abs(abs(x-s)+1+abs(y-g)),abs(abs(y-s)+1+abs(x-g)))
    ans[dis] += 1
    
for i in range(1,n) :
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def D():
    nxy=list(map(int,input().split()))
    len_list=[]
    len_count=0
    
    for i in range(1,nxy[0]+1):
        for j in range(i,nxy[0]+1):
            if i<j: len_list.append(min(abs(j-i),abs(nxy[1]-i)+1+abs(j-nxy[2])))
                
    
    len_list.sort()
    for k in range(1,nxy[0]):
        print(len_list.count(k))
    
        
if __name__=='__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
def D():
    nxy=list(map(int,input().split()))
    len_list=[]
    len_count=0
    
    for i in range(1,nxy[0]+1):
        for j in range(1,nxy[0]+1):
            if i<j: len_list.append(min(abs(j-i),abs(nxy[1]-i)+1+abs(j-nxy[2])))
                
    
    len_list.sort()
    for k in range(1,nxy[0]):
        print(len_list.count(k))
    
        
if __name__=='__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
def D():
    nxy=list(map(int,input().split()))
    len_list=[]
    len_count=0
    
    for i in range(1,nxy[0]+1):
        for j in range(1,nxy[0]+1):
            if i<j: len_list.append(min(abs(j-i),abs(nxy[1]-i)+1+abs(j-nxy[2])))
                
    
    for k in range(1,nxy[0]):
        for i in len_list:
             if k==i: len_count+=1
                
        print(len_count)
        len_count=0
        
    
if __name__=='__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

inf = 100100100

x -= 1
y -= 1

ans = [0] * n

for i in range(n):
    dist = [inf] * n
    queue = deque()
    queue.append(i)
    dist[i] = 0
    while queue:
        current = queue.popleft()
        d = dist[current]

        if current - 1 >= 0 and dist[current - 1] == inf:
            queue.append(current - 1)
            dist[current - 1] = d + 1
        if current + 1 < n and dist[current + 1] == inf:
            queue.append(current + 1)
            dist[current + 1] = d + 1
        if current == x and dist[y] == inf:
            queue.append(y)
            dist[y] = d + 1
        if current == y and dist[x] == inf:
            queue.append(x)
            dist[x] = d + 1

    for j in range(n):
        ans[dist[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    ans = [0] * N
    
    for start_vertex in range(N):
        q = deque()
        distance_list = [float('inf')] * N
        def push(vertex, distance):
            if distance_list[vertex] != float('inf'):
                return
            distance_list[vertex] = distance
            q.append(vertex)
        
        push(start_vertex, 0)
        while len(q) > 0:
            vertex = q.popleft()
            distance = distance_list[vertex]

            if vertex - 1 >= 0:
                push(vertex-1,distance+1)
            if vertex + 1 < N:
                push(vertex+1,distance+1)
            if vertex == X:
                push(Y,distance+1)
            if vertex == Y:
                push(X,distance+1)
        for d in distance_list:
            ans[d] += 1
    
    ans = list(map(lambda x: x // 2, ans))
    print(*ans[1:], sep='\n')
        

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, x, y = map(int,input().split())
    ans = [0] * n
    dp = [[0] * (n - 1) for i in range(n)]
    for i in range(1,n+1):
        for j in range(1,n+1):
            dirct = abs(i-j)
            mid_x = abs(x-i) + 1 + abs(y - j)
            mid_y = abs(y-i) + 1 + abs(x - j)
            ans[min(dirct, mid_x, mid_y)] += 1
    for i in range(1, n ):
        print(ans[i] // 2)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#template
from collections import Counter
def inputlist(): return [int(j) for j in input().split()]
#template
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True

        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

N,X,Y = inputlist()
X-=1
Y-=1
ans = [0]*N
cost = [[float('inf') for _ in range(N)] for _ in range(N)]
for i in range(N):
    if i != N-1:
        cost[i][i+1] = 1
    if i != 0:
        cost[i][i-1] = 1
    if i == X:
        cost[X][Y] = 1
    if i == Y:
        cost[i][X] = 1
for i in range(N):
    ans[i] = dijkstra(i,N,N,cost)
li = [0]*(N)
for i in range(N):
    for j in range(N):
        li[ans[i][j]] +=1
for i in range(1,N):
    print(li[i]//2)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
lis = []
for i in range(1, n):
    for j in range(i+1, n+1):
        lis.append(min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)]))
for i in range(1, n):
    print(lis.count(i))

Submission status: Time Limit Exceeded

Solution code:
#未提出
n, x, y = map(int, input().split())
lis = []
for i in range(1, n):
    for j in range(i+1, n+1):
        lis.append(min([j-i, abs(x-i)+1+abs(y-j), abs(y-i)+1+abs(x-j)]))
import collections
dic = collections.Counter(lis)
for i in range(1, n):
    print(dic[i])

Submission status: Time Limit Exceeded

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

d = [[] for n in range(N)]
answer = [0 for n in range(N - 1)]
for i in range(N):
  r = 0
  for j in range(i + 1, N):
    d[i].append(min([abs((i + 1) - (j + 1)), abs(X - (i + 1)) + 1 + abs(Y - (j + 1)), abs(Y - (i + 1)) + 1 + abs(X - (j + 1))]))
    answer[d[i][r] - 1] += 1
    r += 1

for i in range(len(answer)):
  print(answer[i])

Submission status: Time Limit Exceeded

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

d = [[-1 for n in range(N)] for n in range(N)]
answer = [0 for n in range(N - 1)]
for i in range(N):
  for j in range(i + 1, N):
    d[i][j] = min([abs((i + 1) - (j + 1)), abs(X - (i + 1)) + 1 + abs(Y - (j + 1)), abs(Y - (i + 1)) + 1 + abs(X - (j + 1))])
    answer[d[i][j] - 1] += 1

for i in range(len(answer)):
  print(answer[i])

Submission status: Time Limit Exceeded

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

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

answer = [0 for n in range(N - 1)]
for i in range(N):
  for j in range(N):
    if d[i][j] != - 1:
      answer[d[i][j] - 1] += 1

for i in range(len(answer)):
  print(answer[i])

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split(' '))
cost = [0 for i in range(n - 1)]
for i in range(n - 1):
    for l in range(i + 1, n):
        result = min(abs(i - l),abs(i - x + 1) + 1 + abs(l - y + 1),abs(i - y + 1) + 1 + abs(l - x + 1))
        cost[result - 1] += 1
for per in cost:
    print(per)

Submission status: Time Limit Exceeded

Solution code:
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
cost = [0 for i in range(num_data[0] - 1)]
for i in range(num_data[0] - 1):
    for l in range(i + 1, num_data[0]):
        result = min(abs(i - l),abs(i - num_data[1] + 1) + 1 + abs(l - num_data[2] + 1),abs(i - num_data[2] + 1) + 1 + abs(l - num_data[1] + 1))
        cost[result - 1] += 1
for per in cost:
    print(per)

Submission status: Time Limit Exceeded

Solution code:
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number
for i in range(num_data[0] - 1):
    for l in range(num_data[0] - i - 1):
        result = min(abs(i - l - i - 1),abs(i - num_data[1] + 1) + 1 + abs(l + i + 1 - num_data[2] + 1),abs(i - num_data[2] + 1) + 1 + abs(l + i + 1 - num_data[1] + 1))
        cost[int(result) - 1] += 1
for per in cost:
    print(per)

Submission status: Time Limit Exceeded

Solution code:
def main():
    dist = []
    import numpy as np
    from collections import deque
    n, x, y = map(int,input().split())
    g = [[] for _ in range(n)] 
    for i in range(n-1):

        g[i] += i+1,
        g[i+1] += i,
    g[x-1] += y-1,
    g[y-1] += x-1,
    a = [0]*n
    for start in range(n):
        d = [-1] * n
        d[start] = 0
        q = deque([start])
        add,pop=q.append,q.popleft
        while q:
            v = pop()
            for nv in g[v]:
                if d[nv] < 0:
                    d[nv] = d[v]+1
                    add(nv)
        # for i in d:
        #     a[i] += 1
        dist.append(d)
    dist = np.array(dist).flatten()
    for i in range(1,n):
        print(int(len([x for x in dist if x==i])/2))
    # for i in range(1,n):
    #     print(int(a[i]/2))
main()

Submission status: Time Limit Exceeded

Solution code:
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number
for i in range(num_data[0]):
    for l in range(num_data[0]):
        if(l != i):
            result = min(abs(i - l),abs(i - num_data[1] + 1) + 1 + abs(l - num_data[2] + 1),abs(i - num_data[2] + 1) + 1 + abs(l - num_data[1] + 1))
            cost[int(result) - 1] += 1
for per in cost:
    print(int(per/2))

Submission status: Time Limit Exceeded

Solution code:
def main():
    dist = []
    import numpy as np
    from collections import deque
    n, x, y = map(int,input().split())
    g = [[] for _ in range(n)] 
    for i in range(n-1):

        g[i] += i+1,
        g[i+1] += i,
    g[x-1] += y-1,
    g[y-1] += x-1,
    a = [0]*n
    for start in range(n):
        d = [-1] * n
        d[start] = 0
        q = deque([start])
        add,pop = q.append,q.popleft
        while q:
            v = pop()
            for nv in g[v]:
                if d[nv] < 0:
                    d[nv] = d[v]+1
                    add(nv)
        # for i in d:
        #     a[i] += 1
        dist.append(d)
    dist = np.array(dist).flatten()
    for i in range(1,n):
        print(int(np.count_nonzero(dist==i)/2))
    # print(' '.join(str(i//2) for i in a[1:]))
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,
a = [0]*n
for start in range(n):
    d = [-1] * n
    d[start] = 0
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        v = pop()
        for nv in g[v]:
            if d[nv] < 0:
                d[nv] = d[v]+1
                add(nv)
    for i in d:
        a[i] += 1
print(' '.join(str(i//2) for i in a[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,
a = [0]*n
for start in range(n):
    d = [-1] * n
    d[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        # v = que.get()
        v = pop()
        for nv in g[v]:
            if d[nv] < 0:
                d[nv] = d[v]+1
                # que.put(nv)
                add(nv)
    for i in d:
        a[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in a[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for start in range(n):
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    add,pop = q.append,q.popleft
    while q:
        # v = que.get()
        v = pop()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                add(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for start in range(n):
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n-1):

    g[i] += i+1,
    g[i+1] += i,
g[x-1] += y-1,
g[y-1] += x-1,

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ 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)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
# for i in range(1,n):
#     # print(int(np.count_nonzero(d==i)/2))
#     print(int(ans[i]/2))
print(' '.join(str(i//2) for i in ans[1:]))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ 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)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)

ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] == -1:
                dist[nv] = dist[v]+1
                # que.put(nv)
                q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ 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)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            # que.put(nv)
            q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i].append(i+1)
    elif i == n-1:
        g[i].append(i-1)
    else:
        g[i].append(i-1)
        g[i].append(i+1)
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            # que.put(nv)
            q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1,i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            # que.put(nv)
            q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
import queue
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1,i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    que = queue.Queue()
    que.put(start)
    while not que.empty():
        v = que.get()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            que.put(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))

Submission status: Time Limit Exceeded

Solution code:
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
data = [[i - 1,i + 1] if 0 < i and i < num_data[0] - 1 else [i + 1] for i in range(num_data[0])]
data[num_data[1] - 1].append(num_data[2] - 1)
data[num_data[2] - 1].append(num_data[1] - 1)
data[num_data[0] - 1][0] = num_data[0] - 2
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number

key = 0
number = 0
for i in range(num_data[0]):
    curent = i
    count = 1
    seen = [False for i in range(num_data[0])]
    seen[i] = True
    todo = [i]
    key = 0
    while(all(seen) == False):
        if(key == 0):
            key = len(todo) - 1
        else:
            key -= 1
        for per in data[curent]:
            if(seen[per]):
                pass
            else:
                seen[per] = True
                todo.append(per)
                cost[count - 1] += 1
        todo.pop(0)
        curent = todo[0]
        if(key == 0):
            count += 1

for per in cost:
    print(int(per/2))

Submission status: Time Limit Exceeded

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

lst = [0 for _ in range(1, n)]
for _ in itertools.combinations([_ for _ in range(1, n+1)], 2):
    i, j = _[0], _[1] 
    ans = min(abs(i-j), abs(x-j)+1+abs(y-i),abs(x-i)+1+abs(y-j))
    lst[ans-1] += 1
    
for _ in lst:
    print(_)

Submission status: Time Limit Exceeded

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

res = [0] * (N)

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

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

Submission status: Time Limit Exceeded

Solution code:
import os
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
data = [[i - 1,i + 1] if 0 < i and i < num_data[0] - 1 else [i + 1] for i in range(num_data[0])]
data[num_data[1] - 1].append(num_data[2] - 1)
data[num_data[2] - 1].append(num_data[1] - 1)
data[num_data[0] - 1][0] = num_data[0] - 2
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number

key = 0
for i in range(num_data[0]):
    curent = i
    count = 1
    seen = [False for i in range(num_data[0])]
    seen[i] = True
    todo = [i]
    key = 0
    while(all(seen) == False):
        if(key == 0):
            key = len(todo) - 1
        else:
            key -= 1
        for per in data[curent]:
            if(seen[per]):
                pass
            else:
                seen[per] = True
                todo.append(per)
                cost[count - 1] += 1
        todo.pop(0)
        curent = todo[0]
        if(key == 0):
            count += 1

for per in cost:
    print(int(per/2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = input().split()
ans_list = []
for i in range(1, int(n)):
    for j in range(i+1, int(n)+1):
        ans_list.append(min(abs(i-j), abs(i-int(x))+1+abs(j-int(y)), abs(i-int(y))+1+abs(j-int(x))))
for i in range(1, int(n)):
    print(ans_list.count(i))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import queue

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

edges = [[] for _ in range(n)]
for i in range(n-1):
    edges[i].append(i+1)

for i in range(1, n):
    edges[i].append(i-1)

edges[x-1].append(y-1)
edges[y-1].append(x-1)

count = defaultdict(int)


def bfs(start):
    dist = [10**4] * n
    dist[start] = 0
    todo = queue.Queue(maxsize=10)
    for to in edges[start]:
        todo.put([1, to])

    while not todo.empty():
        d, node = todo.get()
        if d >= dist[node]:
            continue

        dist[node] = d
        for to in edges[node]:
            todo.put([d+1, to])
    return dist


for start in range(n):
    dist = bfs(start)
    for d in dist:
        count[d] += 1

for k in range(1, n):
    res = count[k] // 2
    print(res)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-*-

from sys import stdin
import numpy as np
from scipy.sparse.csgraph import shortest_path


class Dijkstra:
    def __init__(self, num_of_nodes):
        n = np.full((num_of_nodes, num_of_nodes), float('inf'))
        for i in range(num_of_nodes):
            n[i][i] = 0
        self.graph = n

    def add_node(self, node_u, node_v, cost=1):
        self.graph[node_u][node_v] = cost
        self.graph[node_v][node_u] = cost

    def search_shotest_path(self, method='auto'):
        return shortest_path(self.graph, method=method, directed=False, return_predecessors=False, unweighted=False, overwrite=False)


def main():
    N, X, Y = list(map(int, stdin.readline().split()))

    d = Dijkstra(N)
    for i in range(N - 1):
        d.add_node(i, i + 1)
    d.add_node(X - 1, Y - 1)
    result = d.search_shotest_path()
    for i in range(N - 1):
        print(np.count_nonzero(result == i + 1) // 2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from heapq import heappush, heappop


class Dijkstra:
    def __init__(self, num_nodes):
        self.n = num_nodes
        # 隣接行列 d[u][v]: uからvへのコスト
        self.adj_matrix = [[float("inf")]*self.n for i in range(self.n)]

    # Edge数分回すことを想定
    def add_edge(self, start, end, weight=1, undirected=False):
        self.adj_matrix[start][end] = weight
        if undirected:
            self.adj_matrix[end][start] = weight

    def distance(self, start):
        # 始点から各頂点までの最短距離を格納する
        self.dist = [float('inf') for _ in range(self.n)]
        # 最短経路における, その頂点の前の頂点のIDを格納する
        self.prev = [float('inf') for _ in range(self.n)]
        self.dist[start] = 0
        # 各要素は，(頂点vのID, startからある頂点vまでの仮の距離)からなるタプル
        q = []
        heappush(q, (start, 0))
        while len(q) != 0:
            src, prov_cost  = heappop(q)
            # プライオリティキューに格納されている最短距離が, 現在計算できている最短距離より大きければ，distの更新をする必要はない
            if self.dist[src] < prov_cost:
                continue
            # 他の頂点の探索
            for dest in range(self.n):
                cost = self.adj_matrix[src][dest]
                if cost != float('inf') and self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost # distの更新
                    heappush(q, (dest, self.dist[dest])) # キューに新たな仮の距離の情報をpush
                    self.prev[dest] = src
        return self.dist

    def shortest_path(self, goal):
        path = [goal]
        dest = goal
        # 終点から最短経路を逆順に辿る
        while self.prev[dest] != float('inf'):
            path.append(self.prev[dest])
            dest = self.prev[dest]
        return path[::-1]


# BFS pypyでAC
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    solver = Dijkstra(N)
    for val in _data:
        solver.add_edge(val[0]-1, val[1]-1, undirected=True)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist = solver.distance(i)
        for j in range(i, N):
            dist_cnt[dist[j]] += 1
    for i in range(1, N):
        print(dist_cnt[i])


if __name__ == '__main__':
    data = list(map(int, stdin.readline().rstrip('\n').split(' ')))
    get_result(data)

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
king_li = []
for i in range(1, n+1):
    for j in range(i+1,n+1):
        li = []
        li.append(abs(y-j)+abs(x-i)+1)
        li.append(j-i)
        king_li.append(min(li))
for z in range(1,n):
    print(king_li.count(z))