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 = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(X+1, Y):
    dist[i] = min(dist[i-1]+1, dist[i+1]+1, dist[i])
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

print(N)
for k in range(2, N):
  count = 0
  for i in range(N):
    #print('i='+str(i))
    #dist = dist_map[i]
    #print(*dist)
    count += dist_map[i].count(k)
  print(count//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y = map(int,input().split())
cnt = [0]*(n)
path = [(i, i+1) for i in range(n-1)]
path.append((x-1, y-1))
res = []
for i in range(n):
    d = [float('inf')]*n
    que = deque([(i, 0)])
    while que:
        idx, c = que.popleft()
        if d[idx]!=float('inf'):
            continue
        else:
            d[idx] = min(d[idx], c)
            for s,g in path:
                if s==idx:
                    que.append((g, c+1))
                if g==idx:
                    que.append((s, c+1))
    res.append(d)

for r in res:
    for i in range(n-1):
        cnt[i] += r.count(i)
for c in cnt[1:]:
    print(c//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import OrderedDict

sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


def map_int_input():
    return map(int, input())


MII = map_int_input


def MII_split():
    return map(int, input().split())


def MII_to_index():
    return map(to_index, input())


def MII_split_to_index():
    return map(to_index, input().split())


# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))


LII = list_int_inputs


def LII_split():
    return list(map(int, input().split()))


# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]


def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]


N, X, Y = MII_split()

dists = []
for start_node in range(N - 1):

    dists_from_start = OrderedDict()

    for i in range(start_node, N):
        dists_from_start[i] = i - start_node
    # if X - 1 >= start_node:
    #     dists_from_start[Y - 1] = dists_from_start[X - 1] + 1
    #     for i in range(start_node, N):
    #         dists_from_start[i] = dists_from_start[Y - 1] + abs(i - (Y - 1))
    # else:
    back_s = abs(start_node - (X - 1))
    for i in range(start_node, N):
        dist_t = back_s + 1 + abs(Y - 1 - i)
        dists_from_start[i] = min(dist_t, dists_from_start[i])

    dists += dists_from_start.values()

for k in range(1, N):
    print(dists.count(k))

Submission status: Time Limit Exceeded

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

lists = [0 for i in range(N-1)]
for i in range(1,N+1):
    for j in range(i+1,N+1):
        if i <= X and Y <= j:
            pro = j-i-dis+1
            lists[pro-1] += 1
        elif i <= X and X <= j <= Y:
            pro = X+Y-i-j+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and Y <= j:
            pro = i+j-X-Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        elif X <= i <= Y and X <= j <= Y:
            pro = i-j-X+Y+1
            sta = j-i
            lists[min(pro,sta)-1] += 1
        else:
            lists[j-i-1] += 1
            
for i in lists:
    print(i)

Submission status: Time Limit Exceeded

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

p = []

for i in range(1, N):
    for j in range(i+1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)

for k in range(1,N):
    print(p.count(k))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def update_distance(d, num, N):
    minn = num
    maxx = num
    # 要素数の小さい方に向けて
    while True:
        if minn > 0:
            minn -= 1
        else:
            break
        if d[minn] > d[minn+1] + 1:
            d[minn] = d[minn+1] + 1
        else:
            break
    # 要素数の大きいほうに向けて
    while True:
        if maxx < (N - 1):
            maxx += 1
        else:
            break
        if d[maxx] > d[maxx-1] + 1:
            d[maxx] = d[maxx-1] + 1
        else:
            break

(N, X, Y) = (int(i) for i in input().split())
X = X-1
Y = Y-1

# まずは経路情報をd[N][N]の二次元配列に格納
# (i, j)がつながっていれば1, つながってなければ2*10^3

d = []
for i in range(N):
    dd = []
    for j in range(N):
        dd.append(abs(i - j))
    d.append(dd)

# XとYがつながることで最短経路を修正していく
for i in range(N):
    dd = d[i]
    dd[X] = min(dd[X], dd[Y] + 1)
    dd[Y] = min(dd[Y], dd[X] + 1)
    update_distance(dd, X, N)
    update_distance(dd, Y, N)

# dの全リストを連結してあとは0~N-1までカウントする
d_list = []
for i in range(N - 1):
    d_list += d[i][i+1:]

#print(d_list)

for i in range(1, N):
    count = d_list.count(i)
    print(count)

Submission status: Time Limit Exceeded

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

L=[[i+1 for i in range(j+1)][::-1]+[0]*(N-1-j) for j in range(N-1)]
for i in range(len(L)):
    L[i]=[0]+L[i]+[0]
L.append([0]*(N+2))
L.insert(0,[0]*(N+2))
L.insert(0,[0]*(N+2))

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

L[Y][X]=1
task=[(Y,X,1)]
while len(task)>0:
    P=task.pop()
    y,x,c=P[0],P[1],P[2]
    if y<0 or x<0 or y>N or x>N:
        continue
    if L[y+1][x]>c+1:
        L[y+1][x]=c+1
        task.append((y+1,x,c+1))
    if L[y-1][x]>c+1:
        L[y-1][x]=c+1
        task.append((y-1,x,c+1))
    if L[y][x+1]>c+1:
        L[y][x+1]=c+1
        task.append((y,x+1,c+1))
    if L[y][x-1]>c+1:
        L[y][x-1]=c+1
        task.append((y,x-1,c+1))
    #print(y,x,c)
    #print(numpy.array(L))

LL=[]
for i in range(len(L)):
    LL+=L[i]

import collections
D=collections.Counter(LL)
d=list(D.values())
d.pop(0)
d+=[0]*(max(N-len(d)-1,0))

for i in d:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
  
n, x, y = map(int, input().split())
x -= 1
y -= 1
d= [[float('inf')]*n for _ in range(n)]
for i in range(n-1):
  if i == 0:
    d[0][1] = 1
    d[n-1][n-2] = 1
  else:
    d[i][i+1] = 1
    d[i][i-1] = 1
for i in range(n):
  d[i][i] = 0

d[x][y] = 1
d[y][x] = 1
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

d = warshall_floyd(d)
  
from collections import defaultdict
di = defaultdict(int)
for i in range(n):
  for j in range(i+1, n):
    di[d[i][j]] += 1 

for i in range(1, n):
  if i in di.keys():
    print(di[i])
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
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, a, b = map(int, input().split())

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(n-1):
    # x,y,z = map(int,input().split())
    # cost[x][y] = z
    # cost[y][x] = z
    cost[i][i+1] = 1
    cost[i+1][i] = 1
cost[a-1][b-1] = 1
cost[b-1][a-1] = 1


ANS = []
for i in range(n):
    ANS.extend(dijkstra(i, n, n, cost)[i:])

import collections

c = collections.Counter(ANS)

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

Submission status: Time Limit Exceeded

Solution code:



def main():
    # import numpy as np
    N, X, Y = map(int, input().split())

    path_len = Y-X
    G = [0]*N
    for i in range(N):
        if i == 0:
            G[0] = [1]
        elif i == N-1:
            G[N-1] = [N-2]
        else:
            G[i] = [i-1, i+1]
        if i+1 == X:
            G[i].append(Y-1)
        if i+1 == Y:
            G[i].append(X-1)
    # print(G)
    D =[0]*N
    for j,g in enumerate(G):
        D[j] = [1 if i in g else N for i in range(N)]
    
    # from pprint import pprint 
    # pprint(D)
    # D =np.array(D)

    # D=[[0]*N]*N
    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])
    # pprint(D)
    D=sum(D, [])

    for i in range(1,N):
        tmp = D.count(i)
        if i ==2:
            tmp = tmp - N
        
        print(tmp//2)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter

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

    counter = Counter()
    for i in range(1,N+1):
        distance = [float("inf")]*(N+1)
        q = deque()
        q.append(i)
        distance[i] = 0
        while q:
            p = q.popleft()
            if p != 1 and p != N:
                if distance[p+1] == float("inf"):
                    if distance[p]+1 < distance[p+1]:
                        distance[p+1] = distance[p]+1
                        q.append(p+1)
                        counter[distance[p]+1] += 1
                if distance[p-1] == float("inf"):
                    if distance[p]+1 < distance[p-1]:
                        distance[p-1] = distance[p]+1
                        q.append(p-1)
                        counter[distance[p]+1] += 1
            elif p == 1:
                if distance[p+1] == float("inf"):
                    if distance[p]+1 < distance[p+1]:
                        distance[p+1] = distance[p]+1
                        q.append(p+1)
                        counter[distance[p]+1] += 1
            else:
                if distance[p-1] == float("inf"):
                    if distance[p]+1 < distance[p-1]:
                        distance[p-1] = distance[p]+1
                        q.append(p-1)
                        counter[distance[p]+1] += 1
            if p == X:
                if distance[p]+1 < distance[Y]:
                    distance[Y] = distance[p]+1
                    q.append(Y)
                    counter[distance[p]+1] += 1
            if p == Y:
                if distance[p]+1 < distance[X]:
                    distance[X] = distance[p]+1
                    q.append(X)
                    counter[distance[p]+1] += 1

    for i in range(1,N):
        print(counter[i]//2)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
def main():
    N,X,Y = map(int,input().split())
    dp = [[float("inf") for i in range(N)] for j in range(N)]
    heap = []
    heapq.heapify(heap)
    for i in range(N-1):
        dp[i][i+1] = 1
        dp[i+1][i] = 1
        heapq.heappush(heap,(1,i,i+1))
    dp[X-1][Y-1] = 1
    dp[Y-1][X-1] = 1
    heapq.heappush(heap,(1,X-1,Y-1))
    while True:
        if len(heap) == 0 :
            break
        else:
            cost,a,b = heapq.heappop(heap)
            #xを動かす
            for i in [-1,1]:
                if (a + i) < 0 or (a + i) >= N or (a + i) == b :
                    continue
                if dp[a+i][b] > (cost+dp[a][a+i]):
                    dp[a+i][b] = (cost+dp[a][a+i])
                    dp[b][a+i] = (cost+dp[a][a+i])
                    heapq.heappush(heap,(dp[a+i][b],a+i,b))
            for i in [-1,1]:
                if (b + i) < 0 or (b + i) >= N or (b + i) == a :
                    continue
                if dp[a][b+i] > (cost + dp[b][b + i]):
                    dp[a ][b + i] = (cost + dp[b][b + i])
                    dp[b + i][a] = (cost + dp[b][b + i])
                    heapq.heappush(heap, (dp[b + i][a], a, b+ i))
    
    ans = [0 for i in range(N - 1)]
    for i in range(N):
        for j in range(N):
            if dp[i][j] == float("inf"):
                pass
            else:
                ans[dp[i][j] - 1] += 1
    for i in range(N - 1):
        print(ans[i] // 2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, X, Y = [int(x) for x in input().split()]

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

for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        naive_length = j - i
        short_cut_length1 = abs(X - i) + abs(Y - j) + 1
        short_cut_length2 = abs(X - j) + abs(Y - i) + 1
        min_length = min([naive_length, short_cut_length1, short_cut_length2])
        num_distances[min_length] += 1

for d in num_distances[1:]:
    print(d)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop
# Warshall Floyd (scipy ver) : O ( N**3 )
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
import numpy as np


INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, X, Y = MAP()

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

    graph = csr_matrix(dist_matrix)
    dist_matrix = floyd_warshall(graph, directed=False)  # directed=True
    dist_matrix = dist_matrix.astype('int64')
    lis = np.bincount(dist_matrix.flatten())
    for i in range(len(lis)-1):
        print(lis[i+1]//2)
    for i in range(N-len(lis)):
        print(0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

p = []

for i in range(1, N):
    for j in range(1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
for k in range(1,N):
    print(p.count(k))

Submission status: Time Limit Exceeded

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

ans = [0]*(n-1)
d = {}
Q = deque()
flag = [False]*n
for i in range(n-1):
    Q.clear()
    Q.append((i,-1,0))
    for j in range(n): flag[j] = False
    flag[i] = True
    while Q:
        cur,prev,dist = Q.popleft()
        for nxt in to[cur]:
            if nxt == prev: continue
            if flag[nxt]: continue
            flag[nxt] = True
            if (i,nxt) not in d: ans[dist] += 1
            Q.append((nxt,cur,dist+1))
            d[(i,nxt)] = 1
            d[(nxt,i)] = 1

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

Submission status: Time Limit Exceeded

Solution code:

N, X, Y = list(map(lambda x: int(x) ,input().split(" ")))
li = []
result = [ N - i - 1 for i in range(N-1)]

for i in range(N-1):
  l = []
  for k in range(i +1):
    s = i - k
    l.append((X - s, Y + k))
    l.append((X - s, Y - k))
    l.append((X + s, Y - k))
    l.append((X + s, Y + k))
  l = list(set(l))
  for j in l:
    if not(j[0] <= 0 or j[1] > N):
      if j[1] - j[0]  > i + 1:
        result[i] += 1
        result[j[1] - j[0] -1] -= 1


for i in result:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
# input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

    node = [[[] for _ in range(N)] for _ in range(N)]
    used = [[False] * N for _ in range(N)]

    for i in range(N):
        node[i][0].append(i)
        used[i][i] = True


    for k in range(1,N):
        ans = 0
        for i in range(N):
            for x in node[i][k-1]:
                if x == X-1 and (not used[i][Y -1]):
                    node[i][k].append(Y-1)
                    used[i][Y-1] = True
                    ans += 1

                if x == Y-1 and (not used[i][X -1]):
                    node[i][k].append(X-1)
                    used[i][X-1] = True
                    ans += 1

                if (x - 1 >= 0 )and (not used[i][x - 1]):
                    node[i][k].append(x - 1)
                    used[i][x - 1] = True
                    ans += 1

                if (x + 1 < N) and (not used[i][x + 1]):
                    node[i][k].append(x + 1)
                    used[i][x + 1] = True
                    ans += 1
        print(ans//2)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
from collections import OrderedDict
def key(x, y):
    return str(x)+str(y)
def main():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1

    # M = []
    # for i in range(N):
    #     M.append([j for j in range(N-i)])
    M = OrderedDict()
    for i in range(N):
        for j in range(i, N):
            M[key(i, j)] = j - i
    # print(M)
    
    def helper(x, y, from_cost):
        if 0 <= x <= N-1 and 0 <= y <= N-1:
            # print('cost before after', M[key(x,y)], from_cost+1)
            if M[key(x,y)] >= from_cost+1:
                # print('key', key(x,y), '->', from_cost+1)
                M[key(x,y)] = from_cost + 1
                cost = from_cost + 1

                helper(x-1,y, cost)
                helper(x+1,y, cost)
                helper(x,y-1, cost)
                helper(x,y+1, cost)
        
    # M[key(X,Y)] = min(M[key(X,Y)], 1)
    # print(M)
    helper(X, Y, 0)

    cost_list = list(M.values())
    # print(cost_list)
    for k in range(N-1):
        print(cost_list.count(k+1))


main()

Submission status: Time Limit Exceeded

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

G = [[n for i in range(n+1)] for j in range(n+1)]

for i in range(1,n):
    G[i][i] = 1
G[x][y-1]=1

for s in range(1,n-1):
    for i in range(1,n):
        for j in range(i,n):
            if G[i][j]==s:
                G[i+1][j]=min([G[i+1][j], G[i][j]+1])
                G[i][j+1]=min([G[i][j+1], G[i][j]+1])
                G[i-1][j]=min([G[i-1][j], G[i][j]+1])
                G[i][j-1]=min([G[i][j-1], G[i][j]+1])
G_t = []
for i in G[1:-1]:
    G_t.append(i[1:-1])

ans = [0 for i in range(n-1)]
for i in range(n-1):
    for j in range(i,n-1):
        ans[G_t[i][j]-1] += 1
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:



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

    path_len = Y-X
    G = [0]*N
    for i in range(N):
        if i == 0:
            G[0] = [1]
        elif i == N-1:
            G[N-1] = [N-2]
        else:
            G[i] = [i-1, i+1]
        if i+1 == X:
            G[i].append(Y-1)
        if i+1 == Y:
            G[i].append(X-1)
    # print(G)
    D =[0]*N
    for j,g in enumerate(G):
        D[j] = [1 if i in g else np.inf for i in range(N)]
    
    # from pprint import pprint 
    # pprint(D)
    # D =np.array(D)

    # D=[[0]*N]*N
    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])
    # pprint(D)
    D=sum(D, [])

    for i in range(1,N):
        tmp = D.count(i)
        if i ==2:
            tmp = tmp - N
        
        print(tmp//2)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
ans = [0]*(N-1)
X , Y = X-1 , Y-1#配列の場所に合わせる

for i in range(N):
  for k in range(N):
    if i == k:
      pass
    else:
      if i < k:
        ans_ = min(abs(k-i),abs(X-i)+abs(Y-k)+1)
        ans[ans_-1] += 1
      else:
        ans_ = min(abs(k-i),abs(X-k)+abs(Y-i)+1)
        ans[ans_-1] += 1

ans = [int(i/2) for i in ans]

for i in ans:
  print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
import collections


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

route = np.array([[0 for _ in range(n)]for _ in range(n)])
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)


ans = [0 for _ in range(n)]
for i in range(n):
	for j in range(i,n):
		ans[int(res[i][j])] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
n,x,y=map(int,input().split())


l1=n-y-x
l2=y-x

l=[0]*(n-1)
k=0
a=0
b=0
c=0
for i in range(1,n):
	for j in range(i+1,n+1):
		a=j-i
		b=abs(i-x)+1+abs(j-y)
		c=abs(i-y)+1+abs(j-x)
		k=min(a,b,c)
		l[k-1]+=1
		k=0
		a=0
		b=0
		c=0

for j in range(n-1):
	print(l[j])

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int,input().split())
data = [[3000]*N for _ in range(N)]
edge = []
for i in range(N-1):
  edge.append((i+1,i+2))
edge.append((X,Y))
for item in edge:
  data[item[0]-1][item[1]-1] = 1
  data[item[1]-1][item[0]-1] = 1
for i in range(N):
  data[i][i] = 0
for k in range(N):
  for i in range(N):
    for j in range(N):
      data[i][j] = min(data[i][j],data[i][k]+data[k][j])
for i in range(N-1):
  counter = 0
  for j in range(N):
    counter += data[j].count(i+1)
  print(int(counter//2))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def dijkstra(s, n, w, cost):
    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 = map(int, input().split())

cost = [[float("inf") for _ in range(n)] for _ in range(n)]

ans = [0] * n
for i in range(n-1):
    cost[i][i+1] = 1
    cost[i+1][i] = 1

cost[x-1][y-1] = 1
cost[y-1][x-1] = 1

for i in range(n):
    cost[i][i] = 0

for i in range(n):
    a = dijkstra(i, n, n, cost)
    for j in range(n):
        ans[a[j]] += 1

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

Submission status: Time Limit Exceeded

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




p = []

for i in range(1, N):
    for j in range(1, N+1):
        if j<=X:
            p.append(j-i)
        elif j<=Y:
            if i <= X:
                p.append(min(j-i, X-i+1+Y-j))
            else:
                p.append(min(j-i, i-X+1+Y-j))
        else:
            if i <= X:
                p.append(j-i-(Y-X)+1)
            elif i <=Y:
                p.append(min(j-i, i-X+1+j-Y))
            else:
                p.append(j-i)
for k in range(1,N):
    print(sum(x==k for x in p))

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np

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

# print(n, x, y)

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

# print(g)

for i in range(n):
  for j in range(i+1, n):
    if j != y-1:
      g[i][j] = g[i][j-1] + 1
    elif i < x:
      g[i][j] = g[i][x-1] + 1
    else: 
      g[i][j] = min((g[i][j-1] + 1), i+1-x + 1)

# print(g)

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

# print(g)

gn = np.array(g)

# print(gn)

for i in range(1, n):
  print(np.count_nonzero(gn == i))

Submission status: Time Limit Exceeded

Solution code:
import queue
def main():
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1
    ans = [[0]*n for _ in range(n)]
    t = [[i+1, i-1] for i in range(n)]
    t[x].append(y)
    t[y].append(x)
    q = queue.Queue()
    for i in range(n):
        f = [True]*n
        f[i] = False
        q.put([i, 0])
        while not q.empty():
            a, b = q.get()
            for v in t[a]:
                if 0 < v and v < n:
                    if f[v]:
                        if i < v:
                            ans[i][b + 1] += 1
                        f[v] = False
                        if i < v or (i <= (x+y+1)//2 and x <= v):
                            q.put([v, b+1])
    for i in range(1, n):
        p = 0
        for j in range(n):
            p += ans[j][i]
        print(p)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
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

def main():
    n, x, y = map(int, input().split())
    cost = [[float("inf") for i in range(n)] for i in range(n)] 
    for i in range(n):
        if i == n - 1:
            tmp_x, tmp_y = x-1, y-1
        else:
            tmp_x, tmp_y = i, i+1
        cost[tmp_x][tmp_y] = 1
        cost[tmp_y][tmp_x] = 1

    ans_list = [0]*n

    for i in range(n):
        di_list = dijkstra(i,n,n,cost)
        for j in range(i+1,n):
            ans_list[di_list[j]] += 1

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb
#from scipy.special import comb
import itertools

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

combi = list(itertools.combinations(range(1,N+1), 2))
#print(combi)
dist = {}
for i in range(1, N):
    dist[i] = 0

c = [min([kyori[1] - kyori[0], int(abs((kyori[1] - Y))) + 1 + int(abs((X - kyori[0])))]) for kyori in combi]

for i in range(len(c)):
    dist[c[i]] += 1
    #print(c, kyori)
dist2 = sorted(dist.items())
#print(dist, dist2)
for i in range(0, N-1):
    print(dist2[i][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

N, X, Y = map(int, input().split())
field = [[] for _ in range(N)]
for i in range(N-1):
    field[i].append(i+1)
    field[i+1].append(i)
field[X-1].append(Y-1)
field[Y-1].append(X-1)

counter = [0]*(N-1)


def bfs(current, destination, counter, paper):
    next_place = [current]
    while True:
        nn_place = []
        for current_place in next_place:
            if current_place == destination:
                return counter
            else:
                for des in field[current_place]:
                    if paper[des] == False:
                        nn_place.append(des)
                        paper[des] = True
        counter += 1
        next_place = nn_place


for i in range(N-1):
    for j in range(i+1, N):
        if i == j:
            continue
        else:
            paper = [False for i in range(N)]
            step = bfs(i, j, 0, paper)
            counter[step-1] += 1

for el in counter:
    print(str(el))

Submission status: Time Limit Exceeded

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

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

dist_list = []

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

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