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:
from collections import deque


def BFS(s):
    color=["white" for _ in range(n+1)]
    D=[0 for _ in range(n+1)]

    D[s]=0
    color[s]="gray"
    queue=deque([s])

    while len(queue)>0:
        u=queue.popleft()
        for i in M[u]:
            if color[i]=="white":
                D[i]=D[u]+1
                color[i]="gray"
                queue.append(i)
        color[u]="black"

    return D


n,x,y=map(int,input().split())
M=[[] for _ in range(n+1)]
for i in range(1,n):
    M[i].append(i+1)
    M[i+1].append(i)
M[x].append(y)
M[y].append(x)

A=[0]*(n)
for i in range(1,n+1):
    for j in BFS(i)[i:]:
        A[j] +=1

for i in A[1:]:
    print(i)

Submission status: Time Limit Exceeded

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


def distance(i,j):
    d1 = abs(i-j)
    d2 = abs(i-x)+1+abs(j-y)
    d3 = abs(i-y)+1+abs(j-x)    
    d = min(d1,d2,d3)
    return d

d = [0]*(n-1)
for i in range(1, n+1):
    for j in range(i+1,n+1):
        d[distance(i,j)-1] = d[distance(i,j)-1] + 1

for i in d:
    print(i)

Submission status: Time Limit Exceeded

Solution code:


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


def distance(i,j):
    d1 = abs(i-j)
    d2 = abs(i-x)+1+abs(j-y)
    d3 = abs(i-y)+1+abs(j-x)    
    d = min(d1,d2,d3)
    return d

c = []
for i in range(1, n+1):
    for j in range(i+1,n+1):
        c.append(distance(i,j))

d = [0]*(n-1)
for i in c:
    d[i-1] = d[i-1] + 1
for i in d:
    print(i)

Submission status: Time Limit Exceeded

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


def distance(i,j):
    d1 = abs(i-j)
    d2 = abs(i-x)+1+abs(j-y)
    d3 = abs(i-y)+1+abs(j-x)    
    d = min(d1,d2,d3)
    return d

c = []
for i in range(1, n+1):
    for j in range(i+1,n+1):
        c.append(distance(i,j))

for i in range(1,n):
    d = 0
    for j in c:
        if j == i:
            d = d + 1
    print(d)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc160/tasks/abc160_d
N, X, Y = map(int, input().split())

visited = set()

# special case: first advance
for i in range(N - 1):
    visited.add((i, i + 1))
visited.add((X - 1, Y - 1))

print(len(visited))

for _ in range(N - 2):
    total = 0

    for point in visited.copy():
        x, y = point

        if (x - 1, y) not in visited and x - 1 >= 0:
            visited.add((x - 1, y))
            total += 1

        if (x + 1, y) not in visited and x + 1 != y:
            visited.add((x + 1, y))
            total += 1

        if (x, y - 1) not in visited and x != y - 1:
            visited.add((x, y - 1))
            total += 1

        if (x, y + 1) not in visited and y + 1 < N:
            visited.add((x, y + 1))
            total += 1

    print(total)

Submission status: Time Limit Exceeded

Solution code:
def dist(i,j,x,y):
    a = abs(i-j)
    b = abs(x-i) + abs(y-j) + 1
    c = abs(x-j) + abs(y-i) + 1
    return min(a,b,c)

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

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

    for i in range(N):
        for j in range(N):
            index = dist(i,j,X,Y)
            K[index] += 1

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, X, Y = LI()
X -= 1
Y -= 1
path = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(i, N):
        path[i][j] = j - i
        path[j][i] = j- i
    
path[X][Y] = 1
path[Y][X] = 1

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

anss = [0 for i in range(N)]
# for p in path:
#     print(p)

for i in range(N):
    for j in range(i + 1, N):
        anss[path[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, X, Y = LI()
X -= 1
Y -= 1
path = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        path[i][j] = abs(i - j)
        path[j][i] = abs(j - i)
    
path[X][Y] = 1
path[Y][X] = 1


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

anss = [0 for i in range(N)]
# for p in path:
#     print(p)

for i in range(N):
    for j in range(N):
        anss[path[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, X, Y = LI()
path = [[mod for i in range(N)] for i in range(N)]
for i in range(N):
    path[i][i] = 0

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

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

anss = [0 for i in range(N)]
# print(path)
for i in range(N):
    for j in range(N):
        anss[path[i][j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
n,x,y = [int(i) for i in readline().split()]

INF = 1001001001

from collections import deque

def push(v,d):
    if dist[v] != INF:
        return
    dist[v] = d
    q.append(v)

x -= 1
y -= 1
ans = [0]*n
for sv in range(n):
    dist = [INF]*n
    q = deque()
    push(sv, 0) # 初期状態
    while len(q):
        v = q.popleft()
        d = dist[v]
        if v-1 >= 0: push(v-1, d+1)
        if v+1 < n: push(v+1, d+1)
        if v == x: push(y, d+1)
        if v == y: push(x, d+1)
    for i in range(n):
        ans[dist[i]] += 1
for i in range(n):
    ans[i] //= 2 # (1,2)と(2,1)を2度数えてしまっているので2で割る
for i in range(1,n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
def min_distance(i,j):
    return min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
               
n,x,y=list(map(int,input().split()))
x=x-1
y=y-1
dp=[]
for i in range(n):
    for j in range(n):
        dp.append(min_distance(i,j))
dic=Counter(dp)
for i in range(1,n):
    print(int(dic[i]/2))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import Counter
#入力
n,x,y=list(map(int,input().split()))
x=x-1
y=y-1
#幅優先探索　i番目いけるdp
def bfs(i):
    dp=[float("INF")]*n
    q=deque([i])
    dp[i]=0
    while len(q)>0:
        p=q.popleft()
        if 0<=p-1<=n-1 and dp[p]+1<dp[p-1]:
            dp[p-1]=dp[p]+1
            q.append(p-1)
        if 0<=p+1<=n-1 and dp[p]+1<dp[p+1]:
            dp[p+1]=dp[p]+1
            q.append(p+1)
        if  p==x and dp[p]+1<=dp[y]:
            dp[y]=dp[p]+1
            q.append(y)
        if  p==y and dp[p]+1<=dp[x]:
            dp[x]=dp[p]+1
            q.append(x)
    return Counter(dp)
 
answer_list={}
answer_list=Counter(answer_list)
for i in range(n):
    answer_list=answer_list+bfs(i)
for i in range(1,n):
    print(int(answer_list[i]/2))

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
ans = [0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        dis = min(j-i, abs(j-(x-1))+1+abs((y-1)-i), abs(j-(y-1))+1+abs((x-1)-i))
        ans[dis-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())
ans = [0 for _ in range(n-1)]
for i in range(n-1):
    for j in range(i+1,n):
        dis = min(j-i, abs(j-(x-1))+1+abs((y-1)-i), abs(j-(y-1))+1+abs((x-1)-i))
        ans[dis-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())
x -= 1
y -= 1
dis = [0 for i in range(n)]
for i in range(n):
    for j in range(i+1,n):
        dis[min(abs(j-i),min(abs(j-y)+abs(x-i)+1,abs(j-x)+abs(y-i)+1))] += 1
print("\n".join(map(str,dis[1:])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = list(map(int,input().split(' ')))
ls = {}
for i in range(1,N):
	for j in range(i+1,N+1):
		l = min(abs(j-i),abs(i-X)+1+abs(j-Y),abs(i-Y)+1+abs(j-X))
		if l not in ls.keys():
			ls[l] = 1
		else:
			ls[l] = ls[l] + 1

for i,(k,v) in enumerate(sorted(ls.items(),key=lambda x:x[0])):
	print(v)

for j in range(i+2,N):
	print(0)

Submission status: Time Limit Exceeded

Solution code:
#template
def inputlist(): return [int(k) for k in input().split()]
#template
N,X,Y = inputlist()
cost = [[10**5]*(N) for _ in range(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
def dijkstra(s,n,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
li = [0]*N
for i in range(N):
    d = dijkstra(i,N,cost)
    li[i] = d
dic = {n:0 for n in range(1,N)}
for i in range(N):
    for j in range(N):
        if li[i][j] == 0:
            continue
        dic[li[i][j]] +=1
for i in range(1,N):
    print(dic[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict

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

L= [[1]]+[[i-1,i+1] for i in range(1,N-1)]+ [[N-2]]
L[X-1].append(Y-1)
L[Y-1].append(X-1)

def BFS(x,L):
  d=[-1 for _ in range(N)] #距離
  d[x]=0
  v=deque([x])
  
  while len(v)>0:
    a=v.popleft()
    for num in L[a]:
      if d[num]==-1:
        d[num]=d[a]+1
        v.append(num)
  return d

ans=defaultdict(int)

for j in range(N):
  tmp=BFS(j,L)
  #print(tmp)
  for num in tmp:
    ans[num] += 1
    
for k in range(1,N):
  if k in ans:
    print(ans[k]//2)
  else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

L= [[1]]+[[i-1,i+1] for i in range(1,N-1)]+ [[N-2]]
L[X-1].append(Y-1)
L[Y-1].append(X-1)

def BFS(x,L,k):
  cnt=0
  d=[-1 for _ in range(N)] #距離
  d[x]=0
  v=deque([x])
  
  while len(v)>0:
    a=v.popleft()
    for num in L[a]:
      if d[num]==-1:
        d[num]=d[a]+1
        v.append(num)
        if d[num]==k:
          cnt+=1
  return cnt

for k in range(1,N):
  ans=0
  for j in range(N):
    ans+=BFS(j,L,k)
  print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

L= [[1]]+[[i-1,i+1] for i in range(1,N-1)]+ [[N-2]]
L[X-1].append(Y-1)
L[Y-1].append(X-1)

def BFS(x,L,k):
  d=[-1 for _ in range(N)] #距離
  d[x]=0
  v=deque([x])
  
  while len(v)>0:
    a=v.popleft()
    for num in L[a]:
      if d[num]==-1:
        d[num]=d[a]+1
        v.append(num)
  else:
    ret=0
    for num in d:
      if num==k:
        ret+=1
    return ret

for k in range(1,N):
  ans=0
  for j in range(N):
    ans+=BFS(j,L,k)
  print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, X, Y = map(int, input().split())
dic = {key: 0 for key in range(1, N)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if(i < j):
            key = min(abs(j - i), abs(X - i)+1+abs(j - Y),
                      abs(Y - i) + 1 + abs(j - X))
            dic[key] += 1
for ans in dic.values():
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

N, X, Y = map(int, input().split())
dic = {key: 0 for key in range(1, N)}
for i in range(1, N+1):
    for j in range(1, N+1):
        if(i < j):
            key = min(abs(j - i), abs(X - i)+1+abs(j - Y),
                      abs(Y - i) + 1 + abs(j - X))
            dic[key] += 1
for ans in dic.values():
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - Line++

import queue

N, X, Y = map(int, input().split())
X, Y = X - 1, Y - 1
M = [(i, []) for i in range(N)]
for i in range(N):
    if i != 0:
        M[i][1].append(i - 1)
    if i != N - 1:
        M[i][1].append(i + 1)
    if i == X:
        M[X][1].append(Y)
    if i == Y:
        M[Y][1].append(X)

cost = [[-1] * N for _ in range(N)]
p = [[None] * N for _ in range(N)]
Q = queue.Queue()

for i in range(N):
    Q.put(M[i])
    key = M[i][0]
    cost[key][key] = 0
    p[key][key] = key
    while not Q.empty():
        q = Q.get()
        for j in q[1]:
            if cost[i][j] == -1:
                p[i][j] = q[0]
                cost[i][j] = cost[i][p[i][j]] + 1
                Q.put(M[j])

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]


def dk(edge,vis):
    q=[[0,vis]]
    visited=[False]*N
    heapify(q)
    while len(q):
        e=heappop(q)
        if visited[e[1]]:
            continue
        visited[e[1]]=True
        if e[1]>vis:
            ans[e[0]]+=1
        for ne in edge[e[1]]:
            heappush(q,[e[0]+1,ne])



N, X, Y = map(int,input().split()) #n:頂点数　w:辺の数
ans=[0]*(N)
edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
for i in range(N-1):
    x,y=i,i+1
    edge[x].append(y)
    edge[y].append(x)
edge[X-1].append(Y-1)
edge[Y-1].append(X-1)

for vis in range(N-1):
    dk(edge,vis)
    #print(ans)
for a in ans[1:]:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(start, end):
    Q = deque()
    Q.append(start)
    dist[start] = 0

    while Q:
        v = Q.popleft()

        for nv in G[v]:
            if dist[nv] != -1:
                continue
            Q.append(nv)
            dist[nv] = dist[v] + 1

            if nv == end:
                return dist[nv]


N, X, Y = map(int, input().split())
G = [[] for _ in range(N)]
res = [0] * N

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

if abs(X - Y) != 1:
    G[X - 1].append(Y - 1)
    G[Y - 1].append(X - 1)

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

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

Submission status: Time Limit Exceeded

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

from collections import deque, defaultdict
INF = 10**9
d = defaultdict(int)
def bfs(n):
    reached = [INF] * N
    reached[n] = 0
    q = deque()
    q.append(n)
    while q:
        x = q.popleft()
        dx = [-1, 1]
        for i in dx:
            nx = x + i
            if nx < 0 or nx > N - 1 or reached[nx] != INF:
                continue
            reached[nx] = reached[x] + 1
            q.append(nx)
        if x == X and reached[Y] == INF:
            reached[Y] = reached[x] + 1
            q.append(Y)
        if x == Y and reached[X] == INF:
            reached[X] = reached[x] + 1
            q.append(X)
    for i in range(N):
        k = reached[i]
        d[k] += 1

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

Submission status: Time Limit Exceeded

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

for i in range(1,n):
	ans = 0
	for j in range(1,n-i+1):
		if i+j <= x:
			ans += 1
			continue
		elif j >= y and i+j < n:
			ans += 1
			continue
		else:
			# x-j+1 = jからyまでの距離
			# y-i-j = yからi+j(目的地)までの距離
			#print(abs(x-j)+1+abs(y-i-j))
			if min(abs(x-j)+1+abs(y-i-j),i) == i:
				ans += 1
		num = i-(abs(x-j)+1)
		if num >= 0:
			d1 = y+num
			d2 = y-num
			if i+j < d1 and d1 <= n:
				ans += 1
			if i+j < d2 and d1 != d2:
				ans += 1
		#print(i,j,ans)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import csr_matrix
# from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import dijkstra

input = sys.stdin.readline

n, x, y = map(int, input().split())
# A,B: 頂点, C: コスト
A, B, C = [], [], []

for i in range(n-1):
    A.append(i)
    B.append(i+1)
    C.append(1)

A.append(x-1)
B.append(y-1)
C.append(1)

# directed: 有効ならTrue, indices: 始点
# WF O(V^3)
# wf = floyd_warshall(csr_matrix((C, (A, B)), shape = (n, n)), directed=False)
# Dijkstra O((V+E)logV)
ans = [0 for i in range(n-1)]

for i in range(n):
    di = dijkstra(csr_matrix((C, (A, B)), shape = (n, n)), directed=False, indices=i)
    for k in di:
        if k:
            ans[int(k-1)] += 1

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

map = [[n for j in range(n)] for i in range(n)]

#making Node
for i in range(len(map)) :
    if i+1 < n:
        map[i][i+1] = 1
    if i == x-1 :
        map[i][y-1] = 1
for i,row in enumerate(map) :
    q = [[i,0]]
    while len(q) > 0 :
        [pos,cost] = q.pop(0)
        if cost <= row[pos] :
            row[pos] = cost
            #shortcut
            if pos == x-1 :
                q.append([y-1,cost+1])
            if pos == y-1 :
                q.append([x-1,cost+1])
            if pos + 1 < n :
                q.append([pos+1,cost+1])
            if pos - 1 >= 0 :
                q.append([pos-1,cost+1])
ls = []
for i in range(n) :
    for j in range(i,n) :
        ls.append(map[i][j])

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

result = []

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

for i in range(1, N):
    print(result.count(i)//2)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

dp = [[float('inf')] * (N+1) for _ in range(N+1)]
# dp[Y][X] = 1
dp[X][Y] = 1

for i in range(1,N+1):
    for j in range(i,N+1):
        if i == j:
            dp[i][j] = 0
        elif i == X and j == Y:
            dp[X][Y] = 1
        elif i <= X:
            dp[i][j] = min(dp[i][j-1] + 1, dp[i][X] + abs(Y - j) + 1)
        else:
            dp[i][j] = min(dp[i][j-1]+ 1, abs(i - X)+ abs(Y - j) + 1 )

dp = list(itertools.chain.from_iterable(dp))
for i in range(1,N):
    print(dp.count(i))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans=[0]*(n-1)
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(min(j-i,abs(x-i)+1+abs(j-y)),abs(y-i)+1+abs(j-x))-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())
x -= 1
y -= 1

distance_dict = {}
for k in range(1,n):
    distance_dict[k] = set()

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

for keys,vals in distance_dict.items():
    print(len(vals))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
K = [0 for i in range(N)]

for i in range(N-1):
    for j in range(i+1, N):
        a = abs(j - i)
        b = abs(X - i) + 1 + abs(j - Y)
        c = abs(Y - i) + 1 + abs(j - X)
        K[min(a, b, c)] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

Q = deque()
N, X, Y = map(int, input().split())
K = [0 for i in range(N)]

edge = [[]for i in range(N+1)]
for i in range(1, N):
    edge[i].append(i + 1)
    edge[i+1].append(i)
edge[X].append(Y)
edge[Y].append(X)

for i in range(1, N):
    Done = [-1 for j in range(N+1)]
    Q.append(i)
    Done[0] = 0
    Done[i] = 0
    while len(Q) > 0:
        x = Q.popleft()
        for y in edge[x]:
            if Done[y] >= 0:
                continue
            else:
                Done[y] = Done[x] + 1
                Q.append(y)
                if y > i:
                    K[Done[y]] += 1

for z in K[1:]:
    print(z)

Submission status: Time Limit Exceeded

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

distance=[0 for n in range(N-1)]

for i in range(1,N):
    for j in range(i+1,N+1):
        k=min(abs(i-j),abs(X-i)+1+abs(Y-j),abs(X-j)+1+abs(Y-i))
        if k!=0:
            distance[k-1]+=1

for e in distance:
    print(e)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
l = []
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < Y:
            ss = abs(j - Y) + abs(X - i) + 1 
            l.append(min(s, ss))
        elif i >= Y:
            l.append(s)
for i in range(1, N):
    print(l.count(i))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
l = []
for i in range(1, N):
    for j in range(i+1, N+1):
        s = j -i
        if 0 < i < X and Y <= j:
            ss = j - i - (Y - X) + 1
            l.append(ss)
        elif 0 < i < X and X < j < Y:
            ss = X - i + 1 + Y - j
            l.append(min(s, ss))
        elif 0 < i < X and i < j<= X:
            l.append(s)
        elif Y > i >= X and Y >= j > i:
            ss = i - X + 1 + Y - j
            l.append(min(s, ss))
        elif Y > i >= X and Y < j:
            ss = j - Y + 1 + i -X
            l.append(min(s, ss))
        elif i >= Y and j > Y:
            l.append(s)
for i in range(1, N):
    print(l.count(i))

Submission status: Time Limit Exceeded

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

inf = 100000000
G = [[inf for i in range(n)] for j in range(n)]

for i in range(n-1):
    G[i][i] = 0
    G[i][i+1] = 1
    G[i+1][i] = 1
    G[x-1][y-1] = 1
    G[y-1][x-1] = 1
    
v = [False]*n #visited
d = [0]*n #shortest distance

def getsmallindex():
    index = 0
    mn = inf
    for i in range(n):
        if d[i] < mn and v[i] == False:
            mn = d[i]
            index = i
    return index

def dijkstra(start):
    for i in range(n):
        d[i] = G[start][i]
    v[start] = True
    for i in range(n-1):
        current = getsmallindex()
        v[current] = True
        for j in range(n):
            if v[j] == False:
                if d[current] + G[current][j] < d[j]:
                    d[j] = d[current] + G[current][j]

s = [0]*n 
for i in range(n):
    v = [False]*n #visited
    d = [0]*n #shortest distance
    dijkstra(i)
    for k in range(1,n):
        for j in range(i,n):
            if d[j] == k:
                s[k] = s[k] + 1
    
for i in range(1,n):
    print(s[i])

Submission status: Time Limit Exceeded

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

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


for i in range(N-1):
  print(list.count(i+1))

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, X, Y = getlist()
	G = Graph()
	G.add_edge(X - 1, Y - 1)
	G.add_edge(Y - 1, X - 1)
	for i in range(N - 1):
		G.add_edge(i, i + 1)
		G.add_edge(i + 1, i)

	ans = [0] * N
	for i in range(N):
		BF = BFS(G, i, N)
		dist = BF.dist
		for j in range(N):
			ans[dist[j]] += 1

	# print(ans)
	for i in range(1, N):
		print(int(ans[i] // 2))




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.prev = [None] * N
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.put(i)
					self.visit[i] = "Yes"

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, X, Y = getlist()
	G = Graph()
	G.add_edge(X - 1, Y - 1)
	G.add_edge(Y - 1, X - 1)
	for i in range(N - 1):
		G.add_edge(i, i + 1)
		G.add_edge(i + 1, i)

	ans = [0] * N
	for i in range(N):
		BF = BFS(G, i, N)
		for j in range(N):
			ans[BF.dist[j]] += 1

	# print(ans)
	for i in range(1, N):
		print(int(ans[i] // 2))




if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

k = [0 for i in range(N-1)]

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

print('\n'.join(map(str,k)))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    n, x, y = map(int, input().split())
    x, y = x - 1, y - 1
    k = [0] * (n - 1)
    for i in range(n):
        tmp = 0
        for j in range(i):
            if i == j:
                continue
            t = min(abs(i - j), abs(i - x) + 1 + abs(y - j), abs(i - y) + 1 + abs(x - j))
            k[t - 1] += 1
    for i in k:
        print(i)

Submission status: Time Limit Exceeded

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

dp = [[0]*(N+1) for _ in range(N+1)]

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

dp = sum(dp,[])
for j in range(1,N):
    print(dp.count(j))

Submission status: Time Limit Exceeded

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

dp = [[0]*(N+1) for _ in range(N+1)]

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

for j in range(1,N):
    ans = 0
    for k in range(N+1):
        ans += dp[k].count(j)
    print(ans)