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:
import sys
sys.setrecursionlimit(10**7)
n,x,y = map(int,input().split())
g = [[]for i in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(1,n-1):
  g[i].append(i-1)
  g[i].append(i+1)
ans = [0]*(n-1)
def dfs(b,c):
  for i in g[b]:
    if a[i] > c+1:
      a[i] = c+1
      dfs(i,c+1)
    
for i in range(n):
  a = [999999999]*n
  a[i] = 0
  dfs(i,0)
  for j in a:
    if j == 0:
      continue
    ans[j-1] += 1
for i in ans:
  print(i//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def dijkstra(s,n,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')]*N for _ in range(N)]
for i in range(1,N):
    cost[i-1][i] = 1
    cost[i][i-1] = 1
for i in range(N):
    cost[i][i] = 0
cost[X-1][Y-1] = 1
cost[Y-1][X-1] = 1

d = defaultdict(int)
d[float('inf')] = 0
for i in range(N):
    tmp = dijkstra(i,N,cost)
    d[i] += 0
    for j in tmp:
        d[j] += 0.5
del d[0], d[float('inf')]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = [0] * (n+1)
INF = 10 ** 10

for i in range(n):
    distance = [INF] * n
    q = deque([])
    distance[i] = 0
    q.append(i)
    while len(q) > 0:
        v = q.popleft()
        if v - 1 >= 0:
            if distance[v-1] == INF:
                q.append(v-1) 
                distance[v-1] = distance[v] + 1
        if v + 1 < n:
            if distance[v+1] == INF:
                q.append(v+1)
                d = distance[v] + 1
                distance[v+1] = distance[v] + 1
        if v == x:
            if distance[y] == INF:
                q.append(y)
                distance[y] = distance[v] + 1
        if v == y:
            if distance[x] == INF:
                q.append(x)
                distance[x] = distance[v] + 1
    for i in range(n):
        ans[distance[i]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, X, Y= map(int, input().split(' '))
 
node = []
for k in range(1, N+1):
    for v in range(k, N+1):
       node.append(min([abs(k-v), abs(X-k)+abs(v-Y)+1, abs(Y-k)+abs(X-v)+1]))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

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

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

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

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

count = defaultdict(int)


def bfs(start):
    dist = [10**4] * n
    dist[start] = 0
    todo = deque([])
    for to in edges[start]:
        todo.append([1, to])

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

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


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

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

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import Counter

def main():
    N,X,Y=map(int,input().split())
    q=queue.Queue()
    c=Counter()

    for i in range(1,N+1):
        dist=[-1]*(N+1)#indexと頂点の番号を合わせる
        q=queue.Queue()
        q.put([i,0])
        dist[i]=0
        while not q.empty():
            j,kyori=q.get()

            if j-1>=1:
                if dist[j-1]==-1:
                    q.put([j-1,kyori+1])
                    dist[j-1]=kyori+1

            if j+1<=N:
                if dist[j+1]==-1:
                    q.put([j+1,kyori+1])
                    dist[j+1]=kyori+1
            
            if j == X and dist[Y]==-1:
                q.put([Y,kyori+1])
                dist[Y]=kyori+1

            if j == Y and dist[X]==-1:
                q.put([X,kyori+1])
                dist[X]=kyori+1

        c.update(Counter(dist[1:]))

    ans=list(c.items())
    ans.sort()
    lenans=len(ans)
    for i in range(1,N):
        if i<=lenans-1:
            print(ans[i][1]//2)
        else:
            print(0)
main()

Submission status: Time Limit Exceeded

Solution code:
import queue
from collections import Counter

N,X,Y=map(int,input().split())
q=queue.Queue()
c=Counter()

for i in range(1,N+1):
    dist=[-1]*(N+1)#indexと頂点の番号を合わせる
    q=queue.Queue()
    q.put([i,0])
    dist[i]=0
    while not q.empty():
        j,kyori=q.get()

        if j-1>=1:
            if dist[j-1]==-1:
                q.put([j-1,kyori+1])
                dist[j-1]=kyori+1

        if j+1<=N:
            if dist[j+1]==-1:
                q.put([j+1,kyori+1])
                dist[j+1]=kyori+1
        
        if j == X and dist[Y]==-1:
            q.put([Y,kyori+1])
            dist[Y]=kyori+1

        if j == Y and dist[X]==-1:
            q.put([X,kyori+1])
            dist[X]=kyori+1

    c.update(Counter(dist[1:]))

ans=list(c.items())
ans.sort()
lenans=len(ans)
for i in range(1,N):
    if i<=lenans-1:
        print(ans[i][1]//2)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y=map(int,input().split())
array=[]
array=np.array(array)
for i in range(1,n):
    for j in range(i+1,n+1):
        array=np.append(array,(min(abs(j-i),abs(x-j)+1+abs(y-i),abs(y-j)+1+abs(x-i))))
#array=np.array(array)
for i in range(1,n):
    print(np.sum(array==i))

Submission status: Time Limit Exceeded

Solution code:
from collections import *

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

x-=1
y-=1

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

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

  que=deque()
  que.append(i)

  while que:
    p=que.popleft()
    for j in tree[p]:
      if dist[j]==-1:
        que.append(j)
        dist[j]=dist[p]+1
      else:
        continue
  ans+=dist

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

Submission status: Time Limit Exceeded

Solution code:
#BFS
n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0] * (n)
for i in range(n):
    q = [i]
    alr = []
    d = {i:0}
    while not len(q) == 0:
        v = q.pop(0)
        alr.append(v)
        def count(a, b):
            q.append(a)
            if not a in d:
                d[a] = d[b] + 1
            else:
                d[a] = min(d[a], d[b]+1)
        if v-1 >= 0 and not v-1 in alr:
            count(v-1, v)
        if v+1 < n and not v+1 in alr:
            count(v+1, v)
        if v == x and not y in alr:
            count(y, v)
        if v == y and not x in alr:
            count(x, v)
    for value in d.values():
        ans[value] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#BFS
n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0] * (n)
for i in range(n):
    q = [i]
    alr = []
    d = {i:0}
    while not len(q) == 0:
        v = q.pop(0)
        alr.append(v)
        def count(a, b):
            q.append(a)
            if not a in d:
                d[a] = d[b] + 1
            else:
                d[a] = min(d[a], d[b]+1)
        if v-1 >= 0 and not v-1 in alr:
            count(v-1, v)
        if v+1 < n and not v+1 in alr:
            count(v+1, v)
        if v == x and not y in alr:
            count(y, v)
        if v == y and not x in alr:
            count(x, v)
    for value in d.values():
        ans[value] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#BFS
n, x, y = map(int, input().split())
x -= 1
y -= 1
ans = [0] * (n)
for i in range(n):
    q = [i]
    alr = []
    d = {i:0}
    while not len(q) == 0:
        v = q.pop(0)
        alr.append(v)
        def count(a, b):
            q.append(a)
            if not a in d:
                d[a] = d[b] + 1
            else:
                d[a] = min(d[a], d[b]+1)
        if v-1 >= 0 and not v-1 in alr:
            count(v-1, v)
        if v+1 < n and not v+1 in alr:
            count(v+1, v)
        if v == x and not y in alr:
            count(y, v)
        if v == y and not x in alr:
            count(x, v)
    for value in d.values():
        ans[value] += 1
        
for j in range(1, n):
    print(ans[j]//2)

Submission status: Time Limit Exceeded

Solution code:
import queue
import itertools

def bfs(top_dict, first, end):
    q = queue.Queue()
    visited = []
    
    dist = {}
    for i in range(1, end+1):
        dist[i] = 0 
    q.put(first)
    
    while not q.empty():
        label = q.get(0)
        if label not in visited:
            visited.append(label)
            for i in top_dict[label]:
                if dist[i] != 0 or i== first:
                    continue
                dist[i] =  dist[label] +1
                q.put(i)
    return dist  

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

top_dict = {}
for i in range(1, N+1):
    if i == N:
        top_dict[i] = [i-1]
    elif i==1:
        top_dict[i] = [i+1]
    else:
        top_dict[i] = [i-1, i+1]


top_dict[X].append(Y)
top_dict[Y].append(X)
res = list(itertools.chain(*[bfs(top_dict, i, N).values() for i in range(1, N+1)]))

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


def get_adj_list(num_nodes, data, undirected=True):
    # adj_list ex) {1:[2,3,4], 2:[1,4,5], 3:[1,4], 4:[1,2,3,5], 5:[2,4]}
    graph = {}
    for i in range(num_nodes):
        graph[i+1] = []
    for val in data:
        x, y = val
        graph[x] = graph[x] + [y]
        if undirected:
            graph[y] = graph[y] + [x]
    return graph


def breadth_first_search(adj_list, start_node):
    dist = {}
    queue = deque([(start_node, 0)])
    while len(queue) > 0:
        v, d = queue.popleft()
        if v in dist: continue
        dist[v] = d
        for u in adj_list[v]:
            if u not in dist:
                queue.append((u, d+1))
    return dist

# bfs
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_list = []
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist_list.append(breadth_first_search(adj_list, i+1))
    for i in range(N):
        for j in range(i, N):
            dist_cnt[dist_list[i][j+1]] += 1
    for i in range(1, N):
        print(dist_cnt[i])

# 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque


def get_adj_list(num_nodes, data, undirected=True):
    # adj_list ex) {1:[2,3,4], 2:[1,4,5], 3:[1,4], 4:[1,2,3,5], 5:[2,4]}
    graph = {}
    for i in range(num_nodes):
        graph[i+1] = []
    for val in data:
        x, y = val
        graph[x] = graph[x] + [y]
        if undirected:
            graph[y] = graph[y] + [x]
    return graph


def breadth_first_search(adj_list, start_node):
    dist = {}
    queue = deque([(start_node, 0)])
    while len(queue) > 0:
        v, d = queue.popleft()
        if v in dist: continue
        dist[v] = d
        for u in adj_list[v]:
            if u not in dist:
                queue.append((u, d+1))
    return dist

# bfs
def get_result(data):
    N, X, Y = data
    _data = [[i, i+1] for i in range(1, N)]
    _data += [[X, Y]]
    adj_list = get_adj_list(N, _data)
    dist_cnt = [0 for i in range(N)]
    for i in range(N):
        dist = breadth_first_search(adj_list, i+1)
        for j in range(i, N):
            dist_cnt[dist[j+1]] += 1
    for i in range(1, N):
        print(dist_cnt[i])

# 解説のコード
# def get_result(data):
#     N, X, Y = data
#     dist_cnt = [0 for i in range(N)]
#     for i in range(1, N+1):
#         for j in range(i+1, N+1):
#             min_dist = min([j-i, abs(X-i) + 1 + abs(Y-j), abs(Y-i) + 1 + abs(X-j)])
#             dist_cnt[min_dist] += 1
#     for i in range(1, N):
#         print(dist_cnt[i])


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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,x,y=map(int,input().split())
array=[]
for i in range(1,n):
    for j in range(i+1,n+1):
        array.append(min(abs(j-i),abs(x-j)+1+abs(y-i),abs(y-j)+1+abs(x-i)))
array=np.array(array)
for i in range(1,n):
    print(np.sum(array==i))

Submission status: Time Limit Exceeded

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

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

  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


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


N, X, Y = readints()

ans = [0] * N

for i in range(N):
    visited = [False]*(N+1)
    dist = [10000000]*(N+1)
    dist[i+1] = 0
    Q = deque()
    Q.append(i+1)

    while len(Q) != 0:
        node = Q.popleft()
        if visited[node]:
            continue
        visited[node] = True
        if node == 1:
            dist[2] = min(dist[2], dist[node]+1)
            Q.append(2)
        elif node == N:
            dist[N-1] = min(dist[N-1], dist[node]+1)
            Q.append(N-1)
        else:
            dist[node-1] = min(dist[node-1], dist[node]+1)
            dist[node+1] = min(dist[node+1], dist[node]+1)
            Q.append(node-1)
            Q.append(node+1)
        if node == X:
            dist[Y] = min(dist[Y], dist[node]+1)
            Q.append(Y)
        if node == Y:
            dist[X] = min(dist[X], dist[node]+1)
            Q.append(X)
    for d in dist[i+1:]:
        # print(d)
        ans[d] += 1
for c in ans[1:]:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
n,x,y = map(int,input().split())
edges = [[] for i in range(n)]
for i in range(n):
  if i == 0:
    edges[i].append([1,1])
  elif i == n - 1:
    edges[i].append([i - 1,1])
  else:
    edges[i].append([i - 1, 1])
    edges[i].append([i + 1,1])
edges[x-1].append([y - 1,1])
edges[y-1].append([x - 1,1])
import heapq

def dijkstra(edges,num_v,start):
    dist = [float("inf")] * num_v
    dist[start] = 0
    q = []
    heapq.heappush(q,[0,start])#[0,0]とは1番目に頂点のインデックス、0番目に頂点までのコストを格納する
    
    while len(q) >0:
        #ヒープから取り出し
        _,u = heapq.heappop(q)
        for i in edges[u]:
            if dist[i[0]] > dist[u] + i[1]:
                #頂点までのコストが更新できれば更新してヒープに登録
                dist[i[0]] = dist[u] + i[1]
                heapq.heappush(q,[dist[u] + i[1],i[0]])
    return dist
result_list = []
for i in range(n):
  result_list.append(dijkstra(edges,n,i))
ans_list = [0 for i in range(n)]
for result in result_list:
  for _ in result:
    ans_list[_] += 1
for i in range(1,n):
  print(ans_list[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = map(int, input().split())
for k in range(1,N):
    d = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if k==min(j-i, abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)):
                d+=1
    print(d)

Submission status: Time Limit Exceeded

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

n, x, y = map(int, input().split())
x -= 1
y -= 1
INF = 10010101010101
ans = [0]*n
def put(v, d):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)
for sv in range(n):
    q = queue.Queue()
    dist = [INF for _ in range(n)]
    put(sv, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v-1 >= 0:
            put(v-1, d+1)
        if v+1 < n:
            put(v+1, d+1)
        if v == x:
            put(y, d+1)
        if v == y:
            put(x, d+1)
    for i in range(n):
        ans[dist[i]] += 1
for i in range(n):
    ans[i] = int(ans[i] / 2)

print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

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

n, x, y = map(int, input().split())
x -= 1
y -= 1
INF = 10010101010101
ans = [0 for _ in range(n)]
def put(v, d):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)
for sv in range(n):
    q = queue.Queue()
    dist = [INF for _ in range(n)]
    put(sv, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v-1 >= 0:
            put(v-1, d+1)
        if v+1 < n:
            put(v+1, d+1)
        if v == x:
            put(y, d+1)
        if v == y:
            put(x, d+1)
    for i in range(n):
        ans[dist[i]] += 1
for i in range(n):
    ans[i] = int(ans[i] / 2)

print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

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

n, x, y = map(int, input().split())
x -= 1
y -= 1
INF = 10010101010101
ans = [0 for _ in range(n)]
def put(v, d):
    if dist[v] != INF:
        return
    dist[v] = d
    q.put(v)
for sv in range(n):
    q = queue.Queue()
    dist = [INF for _ in range(n)]
    put(sv, 0)
    while not q.empty():
        v = q.get()
        d = dist[v]
        if v-1 >= 0:
            put(v-1, d+1)
        if v+1 < n:
            put(v+1, d+1)
        if v == x:
            put(y, d+1)
        if v == y:
            put(x, d+1)
    for i in range(n):
        ans[dist[i]] += 1
for i in range(n):
    ans[i] = int(ans[i] / 2)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,x,y = list(map(int, input().split()))

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

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)
dist_matrix= floyd_warshall(csgraph=graph, directed=False)

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

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall
n,x,y = list(map(int, input().split()))

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

graph[x-1][y-1] = 1
graph[y-1][x-1] = 1

graph = csr_matrix(graph)
dist_matrix, predecessors = floyd_warshall(csgraph=graph, directed=False, return_predecessors=True)

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

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

Submission status: Time Limit Exceeded

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

cnt = [0]*N
for i in range(N):
    for j in range(N):
        if j >= i:
            continue
        dist = min(abs(i-j),
                   abs(X-i) + abs(Y-j) + 1,
                   abs(X-j) + abs(Y-i) + 1)
        cnt[dist] += 1

print(*cnt[1:], sep='\n')

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

L=[[0]*n for i in range(n)]
for i in range(n-1):
	L[i][i+1]=L[i+1][i]=1
L[x-1][y-1]=L[y-1][x-1]=1

R=[0]*n

def bfs(j):
	V=[-1]*n
	que=deque([])
	que.append(j)
	V[j]=0
	while que:
		p=que.popleft()
		for i in range(n):
			if V[i]==-1 and L[p][i]==1:
				que.append(i)
				V[i]=V[p]+1
	for i in range(n):
		R[V[i]]+=1
	
for j in range(n):
	bfs(j)
for i in range(1,n):
	print(R[i]//2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
n, x, y = map(int, input().split())
ans = [0] * (n-1)
for i in range(1, n+1):
    for j in range(1, n+1):
        if i < j:
            # iとjを固定、rangeでi<jを表現
            d = min(j-i, abs(x-i)+abs(j-y)+1, abs(y-i)+abs(x-j)+1)
            # 長さを示すところに+１
            ans[d-1] += 1
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
ans = [0] * (n-1)
for i in range(1, n+1):
    for j in range(1, n+1):
        if i < j:
            # iとjを固定、rangeでi<jを表現
            d = min(j-i, abs(x-i)+abs(j-y)+1, abs(y-i)+abs(x-j)+1)
            # 長さを示すところに+１
            ans[d-1] += 1
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from collections import defaultdict


class Graph(object):
    """
    隣接リストによる無向グラフ
    重み無しで距離は１
    """

    def __init__(self):
        self.graph = defaultdict(list)

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

    def add_edge(self, src, dst):
        self.graph[src].append(dst)
        self.graph[dst].append(src)

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


if __name__ == "__main__":
    n, x, y = map(int, input().split())
    x -= 1
    y -= 1

    g = Graph()
    for i in range(n-1):
        g.add_edge(i, i+1)
    g.add_edge(x, y)

    ans = [0] * (n-1)

    # BFSによる解法
    for i in range(n-1):
        # 始点からの距離
        # -1を未訪問とする
        dist = [-1] * n

        # 初期条件
        # 今回は頂点iから探索を行う
        dist[i] = 0
        que = deque([i])

        while len(que) != 0:
            vertex = que.popleft()
            for v in g.graph[vertex]:
                if dist[v] != -1:
                    pass
                else:
                    tmp = dist[vertex] + 1
                    dist[v] = tmp
                    if v > i:
                        ans[tmp-1] += 1
                    que.extend(g.graph[vertex])

    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = 10 ** 18


dist = [INF] * N
ans = [0] * N


for sv in range(N):
    dist = [INF] * N
    q = deque()

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

    push(sv, 0)
    while 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
for i in range(1, N):
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

dis = [[float('inf')] * n for _ in range(n)]
ans = [0] * (n-1)
for i in range(n):
    for j in range(n):
        if abs(i - j) == 1:
            dis[i][j] = 1
dis[x-1][y-1] = 1
dis[y-1][x-1] = 1

for i in range(n):
    d = dijkstra(i, n, n, dis)
    for j in d:
        if j > 0:
            ans[j-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y = map(int, input().split())
X = X-1
Y = Y-1
kyori  = []
for i in range(N):
    for j in range(i,N):
        l = min(abs(i-j), abs(i-X)+1+abs(j-Y), abs(i-Y)+1+abs(j-X))
        kyori.append(l)
for k in range(1,N):
    print(kyori.count(k))

Submission status: Time Limit Exceeded

Solution code:
N, X, Y = list(map(int, input().split()))
result = {N-i:0 for i in range(1, N)}

for i in range(1, N):
  for j in range(i + 1, N + 1):
    dis = min([j - i, abs(j - Y) + abs(i - X) + 1, abs(j - X) + abs(i - Y) + 1])
    result[dis] += 1
print("\n".join(list(map(str, result.values()))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
q = deque()
# 更新されない時はqに追加しない
for i in range(N):
    distant = [N]*N
    q.append(i)  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = min(distant[v]+1, distant[e])
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict

N, X, Y = map(int, input().split())
# 全探索でいけるのでは？
# 有向グラフとしてN回幅優先すれば良いのでは？
tree = [[] for _ in range(N)]
for i in range(N-1):
    tree[i].append(i+1)
    tree[i+1].append(i)
tree[X-1].append(Y-1)
tree[Y-1].append(X-1)
ans = defaultdict(int)
# 更新されない時はqに追加しない
for i in range(N):
    distant = [float("inf")]*N
    q = deque([i])  # 始まりのノード
    distant[i] = 0
    while len(q):
        # vは数字, 親のノードのインデックス
        v = q.pop()
        for e in tree[v]:
            if distant[e] < distant[v]+1:  # 到達済みなら次のノードへ
                continue
            distant[e] = min(distant[v]+1, distant[e])
            q.append(e)
    for d in distant:
        ans[d] += 1
for i in range(1, N):
    print(ans[i]//2)

Submission status: Time Limit Exceeded

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

dist_list = [-1 for _ in range(n*n)]
for i in range(n-1):
  for j in range(i+1,n):
    dist_list[i * n + j] = min(j - i, abs(x - i) + 1 + abs(y - j))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, Counter

INF = float("inf")

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

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

C = Counter()
for s in range(1, N + 1):
    dist = [INF] * (N + 1)
    dist[s] = 0
    Q = deque([s])
    while Q:
        p = Q.popleft()
        for c in E[p]:
            if dist[c] > dist[p] + 1:
                dist[c] = dist[p] + 1
                Q.append(c)
    C.update(dist)

for k in range(1, N):
    print(C[k] // 2)

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):
    for j in range(N):
        dist[(min(abs(i-j),abs(i-Y)+abs(X-j)+1,abs(i-X)+abs(Y-j)+1))]+=1
for d in range(1,N):
    print(dist[d]//2)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as combi
N, X, Y = map(int, input().split())

main_list = list(combi(list(range(1, N + 1)), 2))
dis_list = [0] * (N - 1)

for c in main_list:
    if c[0] <= X or c[1] >= Y or (c[0] > X and c[1] < Y):
        dis = min(c[1] - c[0], abs(X - c[0]) + 1 + abs(c[1] - Y))
    else:
        dis = c[1] - c[0]
    dis_list[dis - 1] += 1

for c in range(N - 1):
    print(dis_list[c])

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as combi
N, X, Y = map(int, input().split())

main_list = list(combi(list(range(1, N + 1)), 2))
dis_list = [0] * (N - 1)

for c in main_list:
    if c[0] <= X or c[1] >= Y or (c[0] > X and c[1] < Y):
        dis = min(c[1] - c[0], abs(X - c[0]) + 1 + abs(c[1] - Y))
    else:
        dis = c[1] - c[0]
    dis_list[dis - 1] += 1

for c in dis_list:
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations as combi
N, X, Y = map(int, input().split(" "))

main_list = list(combi(list(range(1, N + 1)), 2))
dis_list = [0] * (N - 1)

for c in main_list:
    x = c[0]
    y = c[1]
    if x <= X or y >= Y or (x > X and y < Y):
        dis = min(y - x, abs(X - x) + 1 + abs(y - Y))
    else:
        dis = y - x
    dis_list[dis - 1] += 1

for c in dis_list:
    print(c)