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:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
#issueから始める
N,X,Y = inputlist()
graph = [[] for _ in range(N+1)]
for i in range(1,N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)
seen = [False]*(N+1)
ans = [0]*(N+1)
def bfs(i):
    from collections import deque
    que = deque()
    que.append([i,0])
    seen[i] = True
    while len(que)!=0:
        li = que.popleft()
        x = li[0]
        count = li[1]
        for j in graph[x]:
            if seen[j]:
                continue
            seen[j] = True
            counta= count + 1
            que.append([j,counta])
            ans[counta]+=1
for i in range(1,N+1):
    seen = [False]*(N+1)
    bfs(i)
for i in range(1,N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

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

def min_dis(i,j):
    return min(abs(j-i),min(abs(j-x)+abs(y-i)+1,abs(x-i)+abs(j-y)+1))
discount = [0]*n 

for i in range(1,n+1):
    for j in range(1,n+1):
        if i<j:
            discount[min_dis(i,j)]+=1

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

Submission status: Time Limit Exceeded

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

print("\n".join(map(lambda u: str(u//2), ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
class Graph(object):
  def __init__(self):
    self.graph = defaultdict(list)

  def addEdge(self, u, v):
    self.graph[u].append(v)
    self.graph[v].append(u)

  def search(self, v, searched):
    visited = [False] * len(self.graph)

    visited[v] = True
    queue = deque([(v,0)])
    while queue:
      s,d = queue.popleft()
      k = lambda x,y: (min(x,y),max(x,y))
      s_ = [(i,d+1) for i in self.graph[s] if not visited[i] and d+1<=searched[k(v,i)]]
      queue.extend(s_)
      for i,_ in s_:
        visited[i] = True
        searched[k(v,i)] = min(searched[k(v,i)], d+1)
        
def main():
  g = Graph()
  N,X,Y = map(int, input().split())
  for i in range(N-1): g.addEdge(i,i+1)
  g.addEdge(X-1,Y-1)
  ans = [0]*(N-1)
  searched = defaultdict(lambda :2*10**3)
  for i in range(N-1): g.search(i, searched)
  for v in searched.values(): ans[v-1] += 1
  for i in ans: print(i)
  
main()

Submission status: Time Limit Exceeded

Solution code:
# D
# -*- coding: utf-8 -*-
N, X, Y = map(int, input().split())
X -= 1
Y -= 1

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

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

Submission status: Time Limit Exceeded

Solution code:
import heapq

class Dijkstra:
    """
    使用方法

    # ゴールが設定されていなかった場合、
    # スタートから各頂点までの最短距離を格納したリストを返す
    dijkstra_result = Dijkstra(n, mp2, s - 1).execute()

    # 設定されていた場合、
    # ゴールまでの最短経路と距離を2つ返す
    dijkstra_result = Dijkstra(n, mp2, s - 1, t - 1).execute()

    # mp2の例 [[現在地, 繋がっている先の場所, 距離], [...]]
    # mp2 = [[2, 4, 2], [3, 4, 5], [3, 2, 1], [1, 3, 2], [2, 0, 8], [0, 2, 8], [1, 2, 4], [0, 1, 3]]
    """

    def __init__(self, n, mp2, start_point, goal_point=None):
        rote_map = [dict() for _ in range(n)]
        for ele in mp2:
            u, v, l = map(int, ele)
            rote_map[u-1][v-1] = l
            # 道が一方通行の場合は下の１行を消す
            rote_map[v - 1][u - 1] = l
        self.rote_map = rote_map
        self.start_point = start_point - 1
        if goal_point == None:
            self.goal_point = goal_point
        else:
            self.goal_point = goal_point - 1

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

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

            if dist[src] < prev_cost:
                continue

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

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

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

        return [n + 1 for n in list(reversed(path))]


from collections import defaultdict

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

for i in range(1, n):
    mp2.append([i, i+1, 1])
mp2.append([x, y, 1])

ans = defaultdict(int)
for i in range(1, n):
    tl = Dijkstra(n, mp2, i).execute()[i:]
    for key in tl:
        ans[key] += 1

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  else:
    d=min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
  return d
for l in range(2,n+1):
  distmap=np.array([dist(k,l) for k in range(1,n+1) for l in range(2,n+1)])
[print(np.count_nonzero(distmap==m)) for m in range(1,n)]

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N,X,Y = map(int, input().split())
ans = [0]*(N-1)
for a,b in combinations(range(N),2):
    c = min([abs(a-b), abs(X-1-a)+abs(Y-1-b)+1, abs(Y-1-a)+abs(X-1-b)+1])
    ans[c-1] += 1
print("\n".join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
from sys import *
from collections import deque
N, X, Y = map(int, stdin.readline().split())
dic = {}
dic[1] = set()
for i in range(1,N):
    dic[i].add(i+1)
    dic[i+1] = set([i])
dic[X].add(Y)
dic[Y].add(X)
distances = [0] * (N+1)
q = deque()
for i in range(1,N+1):
    visited = [False]*(N+1)
    visited[i] = True
    q.append([i, 0])
    while q:
        start , d = q.pop()
        for item in dic[start]:
            if not visited[item]:
                visited[item] = True
                distances[d] += 1
                q.appendleft([item, d+1])
stdout.write("\n".join(str(distances[x]//2) for x in range(0, N-1)))

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n,x,y = mi()
dist = y-x
import numpy as np
d = np.array([[0]*n for i in range(n)])
br = [[] for i in range(n)]
for i in range(1,n-1):
    br[i].append(i-1)
    br[i].append(i+1)
br[0].append(1)
br[n-1].append(n-2)
br[x-1].append(y-1)
br[y-1].append(x-1)
from collections import deque
l=deque()
for i in range(n):
    l.append(i)
    b = [-1]*n
    b[i]=1
    d[i][i]=0
    while len(l)>0:
        nn = l.popleft()
        for j in br[nn]:
            if b[j] ==-1:
                l.append(j)
                b[j] = 1
                d[i][j] = d[i][nn]+1


for i in range(1,n):
    print(len(d[d==i])//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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)
dist = [-1]*n
Q = deque()
for i in range(n):
    Q.clear()
    for j in range(n): dist[j] = -1
    Q.append((i,-1))
    dist[i] = 0
    while Q:
        cur,prev = Q.popleft()
        for nxt in to[cur]:
            if nxt == prev: continue
            if dist[nxt] != -1: continue
            Q.append((nxt,cur))
            dist[nxt] = dist[cur]+1
            ans[dist[cur]] += 1

print("\n".join(map(str,(map(lambda x:x//2,ans)))))

Submission status: Time Limit Exceeded

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

#ans = [0] * n
ans = np.zeros(n,np.uint16)
for i in range(1,n):
    for j in range(i+1,n+1):
        ans[min(j-i,abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from sys import *
from collections import deque
N, X, Y = map(int, stdin.readline().split())
dic = {}
dic[1] = []
for i in range(1,N):
    dic[i].append(i+1)
    dic[i+1] = [i]
dic[X].append(Y)
dic[Y].append(X)
distances = [0] * (N+1)
q = deque()
for i in range(1,N+1):
    visited = [False]*(N+1)
    visited[i] = True
    q.append([i, 0])
    while q:
        start , d = q.popleft()
        for item in dic[start]:
            if not visited[item]:
                visited[item] = True
                distances[d] += 1
                q.append([item, d+1])
stdout.write("\n".join(str(distances[x]//2) for x in range(0, N-1)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import collections

# 解説を読んだ。
n, x, y = [int(x) for x in input().split()]

nodes = [i for i in range(1, n + 1)]
patterns = itertools.combinations(nodes, 2)

distannces = []
distannces_append = distannces.append
for p in patterns:
    routes = (
        abs(p[1] - p[0]),
        abs(x - p[0]) + 1 + abs(p[1] - y),
        abs(y - p[0]) + 1 + abs(p[1] - x)
    )
    distannces_append(min(routes))

c = collections.Counter(distannces)

# distannces_count = distannces.count
for k in range(1, n):
    print(c[k])

# 後半 TLE したのでリストの関数をオブジェクトに格納した。

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, stdout  

N,X,Y = [int(c) for c in input().split()]
A=[]
for i in range(1,N+1):
    A.append([0]*N)

        
res1={}
for x in range(0,N):
    for y in range(0,N):
        #print(x,y,abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1),min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1)))
        A[x][y]=min(abs(x-y),abs(abs(X-1-x)+abs(Y-1-y)+1))
        if(x>=y):
            A[x][y]=0

for row in A:
    for y in row:
        if(y in res1):
                res1[y]=res1[y]+1
        else:
            res1[y]=1              

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

Submission status: Time Limit Exceeded

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

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

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(1,N+1-i):
    a, b = j,j+i
    c = min([abs(a-b), abs(X-a)+abs(Y-b)+1, abs(Y-a)+abs(X-b)+1])
    ans[c-1] += 1
print("\n".join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import queue


def bfs(d, s, N):
    dist = [-1]*N
    q = queue.Queue()
    q.put(s)
    dist[i] = 0
    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == -1:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    return dist


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

ans = [0]*(N+1)

for i in range(N):
    s = i+1
    c = Counter(bfs(d, i+1, N))
    for i, m in c.items():
        ans[i] += m

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
ans=[0 for i in range(n)]
for start in range(n):
  gone=[0 for i in range(n)]
  gone[start]=1
  now ={start}
  for i in range(1,n):
    go=set()
    for s in now:
      if s!=0 and gone[s-1]==0:
        go.add(s-1)
        gone[s-1]=1
        ans[i]+=1
      if s!=n-1 and gone[s+1]==0:
        go.add(s+1)
        gone[s+1]=1
        ans[i]+=1
      if s==x-1 and gone[y-1]==0:
        go.add(y-1)
        gone[y-1]=1
        ans[i]+=1
      if s==y-1 and gone[x-1]==0:
        go.add(x-1)
        gone[x-1]=1
        ans[i]+=1
    now=go
for i in range(1,n):
  print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappop, heappush

def dijkstra(s):
    used = [1] * n
    dp = [INF] * n
    dp[s] = 0
    hq = []
    used[s] = 0
    for i in cost[s]:
        heappush(hq, i)

    while hq:
        minv = heappop(hq)
        if used[minv[1]] == 0:
            continue
        v = minv[1]
        dp[v] = minv[0]
        used[v] = 0
        for i in cost[v]:
            if used[i[1]]:
                heappush(hq, [i[0] + dp[v], i[1]])
    return dp

INF = 10 ** 18
n, x, y = map(int, input().split())
cost = [[] for _ in range(n)]

for i in range(n - 1):
    a = i
    b = i + 1
    cost[a].append([1, b])
    cost[b].append([1, a])
cost[x - 1].append([1, y - 1])
cost[y - 1].append([1, x - 1])
ans = [0] * n
for i in range(n - 1):
    dp1 = dijkstra(i)
    for j in dp1[i:]:
        ans[j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
# 解説を読んだ。
n, x, y = [int(x) for x in input().split()]

nodes = [i for i in range(1, n + 1)]
patterns = itertools.combinations(nodes, 2)

distannces = []
distannces_append = distannces.append
for p in patterns:
    routes = (
        abs(p[1] - p[0]),
        abs(x - p[0]) + 1 + abs(p[1] - y),
        abs(y - p[0]) + 1 + abs(p[1] - x)
    )
    distannces_append(min(routes))

distannces_count = distannces.count
for k in range(1, n):
    print(distannces_count(k))

# 後半 TLE したのでリストの関数をオブジェクトに格納した。

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
K = Y - X
ans = np.zeros(N-1,dtype = int)
for i in range(1, N+1):
  for j in range(i+1, N+1):
    tmp = min(j-i,abs(X-i) +1 +abs(Y-j))
    ans[tmp-1] += 1
for i in range(N-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import queue

def bfs(d,s,N):
    dist = [None]*N
    q=queue.Queue()
    q.put(s)
    dist[i]=0
    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    return dist


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

ans=[0]*(N+1)

for i in range(N):
    s=i+1
    c=Counter(bfs(d,i+1,N))
    for i,m in c.items():
        ans[i]+=m

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
def dist(i,j):
  return min(abs(j-i),abs(y-j)+1+abs(x-i),abs(y-i)+1+abs(x-j))
distmap=[]
for l in range(2,n+1):
  distmap[len(distmap):len(distmap)]=[dist(k,l) for k in range(1,l)]
[print(distmap.count(m)) for m in range(1,n)]

Submission status: Time Limit Exceeded

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


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

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

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

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



main()

Submission status: Time Limit Exceeded

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

for k in range(1, n):
    print(distance.count(k))

Submission status: Time Limit Exceeded

Solution code:
import itertools
# 解説を読んだ。
n, x, y = [int(x) for x in input().split()]

nodes = [i for i in range(1, n + 1)]
patterns = itertools.combinations(nodes, 2)

distannces = []
for p in patterns:
    routes = (
        abs(p[1] - p[0]),
        abs(x - p[0]) + 1 + abs(p[1] - y),
        abs(y - p[0]) + 1 + abs(p[1] - x)
    )
    distannces.append(min(routes))

for k in range(1, n):
    print(distannces.count(k))

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):
        length=min(abs(i-j),abs(x-i)+1+abs(y-j),abs(y-i)+1+abs(x-j))
        ans[length-1]+=1
for i in range(n-1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import queue

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

ans=[0]*(N+1)

for i in range(N):
    dist = [None]*N
    s=i+1
    q=queue.Queue()
    q.put(s)
    dist[i]=0

    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    c=Counter(dist)
    for i,m in c.items():
        ans[i]+=m

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

Submission status: Time Limit Exceeded

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

for k in range(1, n):
    print(distance.count(k))

Submission status: Time Limit Exceeded

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

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

ans = [0 for i in range(n)]
for i in range(n):
	dist = [2 ** 30] * n
	que = Queue()
	que.put(i)
	dist[i] = 0
	while que.qsize():
		v = que.get()
        
		for to in links[v]:
			if dist[to] > dist[v] + 1:
				dist[to] = dist[v] + 1
				que.put(to)
	for d in dist:
		ans[d] += 1
for i in range(n-1): print(ans[i+1]//2)

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int, input().split())
n = list(range(1,N+1))
ans = {i: 0 for i in range(1,N)}
for i in range(1,N):
  for a,b in zip(n[:-i], n[i:]):
    c = min([abs(b-a), abs(X-a)+abs(Y-b)+1, abs(Y-a)+abs(X-b)+1])
    ans[c] += 1
print("\n".join([str(ans[i]) for i in range(1,N)]))

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int, input().split())
es=[[] for _ in range(n)]
for i in range(n):
    if i<n-1:
        es[i].append([1,i+1])
    if i>0:
        es[i].append([1,i-1])
    es[x-1].append([1,y-1])
    es[y-1].append([1,x-1])

import heapq

def dijkstra_heap(s):
    d = [float("inf")] * n
    used = [True] * n
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in es[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in es[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

from collections import defaultdict, Counter
aa=[]
ans=defaultdict(int)
for i in range(n-1):
    a=dijkstra_heap(i)[i+1:]
    ac=Counter(a)
    aa.append(ac)

for i in range(len(aa)):
    for a in aa[i].keys():
        ans[a]+=aa[i][a]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import *
from collections import deque
N, X, Y = map(int, stdin.readline().split())
dic = {}
dic[1] = []
for i in range(1,N):
    dic[i].append(i+1)
    dic[i+1] = [i]
dic[X].append(Y)
dic[Y].append(X)
distances = [0] * (N+1)
q = deque()
for i in range(1,N+1):
    visited = [False]*(N+1)
    visited[i] = True
    distance = [0] *(N+1)
    q.append(i)
    while q:
        start= q.popleft()
        for item in dic[start]:
            if not visited[item]:
                visited[item] = True
                distance[item] = distance[start] +1
                q.append(item)
    for item in distance:
        distances[item] += 1
stdout.write("\n".join([str(x//2) for x in distances[1:-1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	n, x, y = IN()
	al=[]
	for i in range(n):
		ll=[-1]*n
		ll[i]=0
		ol=queue.Queue()
		ol.put(i)
		while not ol.empty():
			pp=ol.get()
			if pp+1 < n and ll[pp+1]==-1:
				ll[pp+1]=ll[pp]+1
				ol.put(pp+1)
			if pp -1 >= 0 and ll[pp-1]==-1:
				ll[pp-1]=ll[pp]+1
				ol.put(pp-1)
			if pp == x-1 and ll[y-1]==-1:
				ll[y-1] = ll[pp]+1
				ol.put(y-1)
			if pp == y-1 and ll[x-1]==-1:
				ll[x-1] = ll[pp]+1
				ol.put(x-1)
		al.append(ll)
			
	rr=[0]*n
	for i in range(n):
		for j in range(i+1,n):
			rr[ al[i][j] ]+=1
	
	for v in rr[1:]:
		print(v)

def main2():
	n, x, y = IN()
	al=[[-1]*n for _ in range(n)]
	ol=queue.Queue()
	for i in range(n):
		al[i][i]=0
	
	for i in range(n-1):
		al[i][i+1]=1
		ol.put((i,i+1))
		al[i+1][i]=1
	al[x-1][y-1]=1
	ol.put((x-1, y-1))
	al[y-1][x-1]=1
	while not ol.empty():
		#print(ol.qsize())
		fp, tp = ol.get()
		for i, dist in enumerate(al[tp]):
			nd = al[fp][tp] + dist
			if dist > 0 and (al[fp][i] == -1 or al[fp][i] > nd) and fp < i:
				al[fp][i]=nd
				al[i][fp]=nd
				ol.put((fp,i))
			
		fp,tp=tp,fp
		for i, dist in enumerate(al[tp]):
			nd = al[fp][tp] + dist
			if dist > 0 and (al[fp][i] == -1 or al[fp][i] > nd) and fp < i:
				al[fp][i]=nd
				al[i][fp]=nd
				ol.put((fp,i))
			
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Time Limit Exceeded

Solution code:
N, x, y = map(int, input().split())
x -= 1
y -= 1
dist = [0] * (N-1)

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

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

Submission status: Time Limit Exceeded

Solution code:
n,x,y=map(int,input().split())
def dist(i,j):
  if i>=j:
    d=0
  elif i<x and y-(y-x)//2+1<=j<=y:
    d=y-j+1+x-i
  elif x<=i<=x+(y-x)//2-1 and y<j:
    d=j-y+1+i-x
  elif x<=i and j<=y:
    d=min(j-i,i+y-x+1-j)
  elif i<x and y<j:
    d=j-y+1+x-i
  else:
    d=j-i
  return d
distmap=[]
for l in range(2,n+1):
  distmap[len(distmap):len(distmap)]=[dist(k,l) for k in range(1,l)]
[print(distmap.count(m)) for m in range(1,n)]

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,Counter
import queue

N, X, Y = map(int, input().split())
d = defaultdict(list)
d[X].append(Y)
d[Y].append(X)
for i in range(1,N):
    d[i].append(i+1)
    d[i+1].append(i)

ans=defaultdict(int)

for i in range(N):
    dist = [None]*N
    s=i+1
    q=queue.Queue()
    q.put(s)
    dist[i]=0

    while not q.empty():
        From = q.get()
        for To in d[From]:
            if dist[To-1] == None:
                q.put(To)
                dist[To-1] = dist[From-1]+1
    c=Counter(dist)
    for i,m in c.items():
        ans[i]+=m


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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
ans = [0 for i in range(n-1)]
for i in range(n-1):
  for j in range(i+1, n):
    k = i + 1
    l = j + 1
    a = l - k
    b_1 = k - x
    b_2 = l - y
    c_1 = k - y
    c_2 = l - x
    if b_1 < 0:
      b_1 = - b_1
    if b_2 < 0:
      b_2 = - b_2
    if c_1 < 0:
      c_1 = - c_1
    if c_2 < 0:
      c_2 = - c_2
    b = b_1 + b_2 + 1
    c = c_1 + c_2 + 1
    if b < a:
      a = b
    if c < a:
      a = c
    ans[a-1] += 1
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, X, Y = map(int, input().split())
K = Y - X
ans = np.zeros(N-1,dtype = int)
for i in range(1, N+1):
  for j in range(i+1, N+1):
    tmp = min(j-i,abs(X-i) +1 +abs(Y-j),abs(X-j) +1 + abs(Y-i))
    ans[tmp-1] += 1
for i in range(N-1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python


n, x, y = (int(v) for v in input().split())
x -= 1
y -= 1
c = [0] * (n - 1)
for i in range(n):
    for j in range(n):
        if i == j:
            continue
        idx = min(
            abs(i - j),
            abs(i - x) + 1 + abs(j - y),
            abs(i - y) + 1 + abs(j - x)
        )
        c[idx - 1] += 1
for v in c:
    print(str(int(v / 2)))

Submission status: Time Limit Exceeded

Solution code:
from collections import*
n,x,y=map(int,input().split())
e=[[]for _ in range(n)]
for i in range(n-1):
    e[i]+=i+1,
    e[i+1]+=i,
e[x-1]+=y-1,
e[y-1]+=x-1,
a=[0]*n
for s in range(n):
    d=[-1]*n
    d[s]=0
    q=deque([s])
    while q:
        v=q.popleft()
        for w in e[v]:
            if d[w]<0:
                d[w]=d[v]+1
                q+=w,
    for i in d:a[i]+=1
print(*[i//2for i in a[1:]])

Submission status: Time Limit Exceeded

Solution code:
import sys
n, x, y = map(int, sys.stdin.readline().split())

x -= 1
y -= 1
    
final = [0]*(n-1)


for i in range(n-1):
    for j in range(i+2, n):
        if j < x or i > y:
            dist = j-i
        else:
            dist = min([j - i, abs(x-i) + 1 + abs(y-j), abs(y-i) + 1 + abs(x-j)])
        final[dist-1] += 1 
final[0] = n
res = [str(one) for one in final]
print ("\n".join(res))

Submission status: Time Limit Exceeded

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

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

ans = [0] * n
for i in range(n):
        dist = [1e5] * n
        used = [0] * n
        que = Queue()
        que.put([i, 0])
        while not que.empty():
                v, dis = que.get()
                used[v] = True
                for to in links[v]:
                        if not used[to]:
                                dist[to] = min(dist[to], dis)
                                que.put([to, dis+1])
        for a in dist:
                if a<1e5: ans[a] += 1
for i in range(n-1): print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque

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

    g = tuple(set() for _ in range(N))
    for v in range(N):
        if v > 0:
            g[v].add(v - 1)
        if v < N - 1:
            g[v].add(v + 1)

    g[X].add(Y)
    g[Y].add(X)

    ctr = [0] * N
    for v in range(N):
        dist = [-1] * N

        q = deque()
        q.append((v, 0))

        while q:
            v, d = q.popleft()
            if ~dist[v] and dist[v] < d: continue
            dist[v] = d
            for u in g[v]:
                if ~dist[u]: continue
                dist[u] = d + 1
                q.append((u, d + 1))

        for d in dist:
            ctr[d] += 1

    print(*map(lambda x: x // 2, ctr[1:]), sep='\n')


if __name__ == '__main__':
    main()