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 queue
INF = 100100100

def put_property(q, cost, v, d) :
    if cost[v] != INF :
        return
    q.put(v)
    cost[v] = d


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

ans = [0] * n

for i in range(n) :
    q = queue.Queue()
    cost = [INF for _ in range(n)]
    put_property(q, cost,  i, 0)
    while not q.empty() :
        v = q.get()
        d = cost[v]
        #print(i, v, d, cost, 'IN')
        #print(v, d)
        if v+1 < n :
            put_property(q, cost, v+1, d+1)
        if v-1 >= 0 :
            put_property(q, cost, v-1, d+1)
        if v == x :
            put_property(q, cost, y, d+1)
        if v == y:
            put_property(q, cost, x, d+1)
        #print(i, v, d, cost)
    for j in range(n) :
        ans[cost[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#D

line = [int(x) for x in input().split()]
n = line[0]
x = line[1]
y = line[2]

results =[0]*(n+2)

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

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

Submission status: Time Limit Exceeded

Solution code:
N,X,Y=map(int,input().split())
def shortest(x,y,a,b):
    ans=min(y-x,abs(y-b)+1+abs(a-x),abs(y-a)+1+abs(b-x))
    return ans
distance=[0]*N
for x in range(1,N+1):
    for y in range(1,N+1):
        if y<=x:
            continue
        else:
            a=shortest(x,y,X,Y)
            distance[a-1]+=1
for i in range(N-1):
    print(distance[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().rstrip()

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

    ans = [0] * N
    for i in range(1, N+1):
        dist = [-1] * (N+1)
        dist[i] = 0
        q = deque()
        q.append(i)
        def push(l, m):
            if dist[l] > -1:
                return
            q.append(l)
            dist[l] = dist[m] + 1
            ans[dist[l]] += 1

        while q:
            j = q.popleft()
            if j < N: push(j+1, j)
            if j > 1: push(j-1, j)
            if j == X: push(Y, j)
            if j == Y: push(X, j)
    for i in range(1, N):
        print(ans[i]// 2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#D

line = [int(x) for x in input().split()]
n = line[0]
x = line[1]
y = line[2]

results =[0]*(n+2)

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

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

Submission status: Time Limit Exceeded

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

# N = 2000
# X = 100
# Y = 1900

X -= 1
Y -= 1


# @profile
def main(N, X, Y):
    ans = [0]*N
    for sv in range(N):
        # dist[v] = dist from sv to v
        dist = [float("inf")]*N
        visited = deque()
        dist[sv] = 0
        visited.appendleft(sv)
        while visited:
            v = visited.pop()
            d = dist[v]
            if v+1 < N and dist[v+1] == float("inf"):
                dist[v+1] = d+1
                visited.appendleft(v+1)
            if v-1 >= 0 and dist[v-1] == float("inf"):
                dist[v-1] = d+1
                visited.appendleft(v-1)
            if v == X and dist[Y] == float("inf"):
                dist[Y] = d+1
                visited.appendleft(Y)
            if v == Y and dist[X] == float("inf"):
                dist[X] = d+1
                visited.appendleft(X)
        # print(dist)
        for d in dist:
            ans[d] += 1

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


main(N, X, Y)

Submission status: Time Limit Exceeded

Solution code:
import queue

def put_property(q, cost, v, d) :
    if cost[v] != float('INF') :
        return
    q.put(v)
    cost[v] = d


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

ans = [0] * n

for i in range(n) :
    q = queue.Queue()
    cost = [float('INF') for _ in range(n)]
    put_property(q, cost,  i, 0)
    while not q.empty() :
        v = q.get()
        d = cost[v]
        #print(i, v, d, cost, 'IN')
        #print(v, d)
        if v+1 < n :
            put_property(q, cost, v+1, d+1)
        if v-1 >= 0 :
            put_property(q, cost, v-1, d+1)
        if v == x :
            put_property(q, cost, y, d+1)
        if v == y :
            put_property(q, cost, x, d+1)
        #print(i, v, d, cost)
    for j in range(n) :
        ans[cost[j]] += 1

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

Submission status: Time Limit Exceeded

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
#from collections import Counter,deque
#from operator import itemgetter,mul
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left,bisect_right
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache,reduce
#from math import factorial,hypot
#import sys
#from fractions import gcd
setrecursionlimit(10**6+1)
input=stdin.readline

n,x,y=map(int,input().split())
dis=[0]*(n-1)
for i in range(1,n+1):
    for j in range(1,n+1):
        if i>=j: continue
        now=min(abs(j-i),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y))
        #print(i+1,j+1,now,(abs(j-i),abs(i-x)+1+abs(j-y),abs(j-x)+1+abs(i-y)))
        dis[now-1]+=1

for i in dis:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue

def put_property(q, cost, v, d) :
    if cost[v] != float('INF') :
        return
    q.put(v)
    cost[v] = d


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

ans = [0] * n

for i in range(n) :
    q = queue.Queue()
    cost = [float('INF') for _ in range(n)]
    put_property(q, cost,  i, 0)
    while not q.empty() :
        v = q.get()
        d = cost[v]
        #print(i, v, d, cost, 'IN')
        #print(v, d)
        if v+1 < n :
            put_property(q, cost, v+1, d+1)
        if v-1 >= 0 :
            put_property(q, cost, v-1, d+1)
        if v == x :
            put_property(q, cost, y, d+1)
        if v == y :
            put_property(q, cost, x, d+1)
        #print(i, v, d, cost)
    for i in range(n) :
        ans[cost[i]] += 1

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

Submission status: Time Limit Exceeded

Solution code:

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

# N = 2000
# X = 100
# Y = 1900


X -= 1
Y -= 1

# @profile
def main(N, X, Y):
    ans = [0]*N
    for sv in range(N):
        # dist[v] = dist from sv to v
        dist = [float("inf")]*N
        last_visited = []
        dist[sv] = 0
        last_visited.append(sv)
        while last_visited:
            next_last_visited = []
            for v in last_visited:
                d = dist[v]
                if v+1 < N and dist[v+1] == float("inf"):
                    dist[v+1] = d+1
                    next_last_visited.append(v+1)
                if v-1 >= 0 and dist[v-1] == float("inf"):
                    dist[v-1] = d+1
                    next_last_visited.append(v-1)
                if v == X and dist[Y] == float("inf"):
                    dist[Y] = d+1
                    next_last_visited.append(Y)
                if v == Y and dist[X] == float("inf"):
                    dist[X] = d+1
                    next_last_visited.append(X)
            # print(last_visited, next_last_visited)
            last_visited = next_last_visited
        # print(dist)
        for d in dist:
            ans[d] += 1

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


main(N, X, Y)

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):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        routeC = abs(Y-i) + abs(X-j) + 1
        min_route = min(routeA, routeB, routeC)
        count[min_route - 1] += 1

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

Submission status: Time Limit Exceeded

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

K=[0]*(n-1)

for i in range(n-1):
    for j in range(i+1,n):
        K[D[i][j]-1]+=1

for k in K:
    print(k)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque, Counter
def input(): return sys.stdin.readline().rstrip()

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

    c = Counter()
    for i in range(1, N+1):
        dist = [-1] * (N+1)
        dist[i] = 0
        q = deque()
        q.append(i)
        while q:
            j = q.popleft()
            if j < N and dist[j+1] < 0:
                q.append(j+1)
                dist[j+1] = dist[j] + 1
            if j > 1 and dist[j-1] < 0:
                q.append(j-1)
                dist[j-1] = dist[j] + 1
            if j == X and dist[Y] < 0:
                q.append(Y)
                dist[Y] = dist[j] + 1
            if j == Y and dist[X] < 0:
                q.append(X)
                dist[X] = dist[j] + 1
        c += Counter(dist)
    for i in range(1, N):
        print(c[i]// 2)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

K=[0]*(n-1)

for i in range(n-1):
    for j in range(i+1,n):
        K[D[i][j]-1]+=1

for k in K:
    print(k)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

ans = [0]*n

for i in range(n):
  dist = [None]*n
  queue = []
  def push(v, d):
    if(dist[v] is not None):
      return 
    dist[v] = d
    queue.append(v)
    
  push(i, 0);
  
  while(len(queue) > 0):
    v = queue.pop(0)
    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)
  #print(dist)
  
  for j in range(n):
    ans[dist[j]] += 1
  #print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

ans = [0]*n



for i in range(n):
  dist = [None]*n
  queue = []
  def push(v, d):
    if(dist[v] is not None):
      return 
    dist[v] = d
    queue.append(v)
    
  push(i, 0);
  
  while(queue):
    v = queue.pop(0)
    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)
  #print(dist)
  for j in range(n):
    ans[dist[j]] += 1
  #print(ans)

for i in range(1, n):
  print(ans[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):
        routeA = abs(j-i)
        routeB = abs(X-i) + abs(Y-j) + 1
        routeC = abs(Y-i) + abs(X-j) + 1
        min_route = min(routeA, routeB, routeC)
        count[min_route - 1] += 1

for i in count:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

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

ans = [0]*n



for i in range(n):
  dist = [None]*n
  queue = []
  def push(v, d):
    if(dist[v] is not None):
      return 
    dist[v] = d
    queue.append(v)
    
  push(i, 0);
  
  while(queue):
    v = queue.pop(0)
    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)
  #print(dist)
  for j in range(n):
    ans[dist[j]] += 1
  #print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INF = 1e10


def main3():
    # official TLE
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    ans = [0 for _ in range(N)]
    for sv in range(N):
        dist = [INF for _ in range(N)]
        q = deque([])

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

        push(sv, 0)

        while q:
            sv = q.popleft()
            d = dist[sv]
            if sv > 0:
                push(sv-1, d+1)
            if sv < N-1:
                push(sv+1, d+1)
            if sv == X:
                push(Y, d+1)
            if sv == Y:
                push(X, d+1)

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

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

main3()

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n=int(s[0])
x=int(s[1])-1
y=int(s[2])-1
inf=float('inf')
map=[]
for i in range(n):
    for j in range(i+1,n):
        map.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(map.count(i))

Submission status: Time Limit Exceeded

Solution code:
s = input().split()
n=int(s[0])
x=int(s[1])-1
y=int(s[2])-1
inf=float('inf')
map=[[0]*n for i in range(n)]
map[x][y]=1
for i in range(n):
    for j in range(i+1,n):
        map[i][j]=min(abs(j-i),abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
for i in range(1,n):
    count=0
    for j in map:
        count+=j.count(i)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,x,y=map(int,input().split())
t=deque()
for i in range(1,n+1):
    for j in range(i+1,n+1):
        t.append(min(abs(j-i),abs(i-x)+abs(j-y)+1))



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

Submission status: Time Limit Exceeded

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



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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import collections

# 標準入力 <int><int>
N, X, Y = map(int, input().split())

br = []

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

c = collections.Counter(br)

for k, v in c.items():
  print(v)

for _ in range(N - 1 - len(c)):
  print(0)

Submission status: Time Limit Exceeded

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

# N = 7
# X = 3
# Y = 7

ans = [0]*N

for sv in range(N):
    # dist[v] = dist from sv to v
    dist = [float("inf")]*N
    last_visited = []
    dist[sv] = 0
    last_visited.append(sv)
    while last_visited:
        next_last_visited = []
        for v in last_visited:
            if v+1 < N and dist[v+1] == float("inf"):
                dist[v+1] = dist[v]+1
                next_last_visited.append(v+1)
            if v-1 >= 0 and dist[v-1] == float("inf"):
                dist[v-1] = dist[v]+1
                next_last_visited.append(v-1)
            if v == X-1 and dist[Y-1] == float("inf"):
                dist[Y-1] = dist[v]+1
                next_last_visited.append(Y-1)
            if v == Y-1 and dist[X-1] == float("inf"):
                dist[X-1] = dist[v]+1
                next_last_visited.append(X-1)
        # print(last_visited, next_last_visited)
        last_visited = next_last_visited
    # print(dist)
    for d in dist:
        ans[d] += 1

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
INF = int(1e9) + 7
n, x, y = map(int, input().split())
x -= 1
y -= 1
d = [[INF] * n for i in range(n)]
ans = [0] * (n+1)
def bfs(i):
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    que = deque([i])
    d[i][i] = 0

    while len(que) != 0:
        val = que.popleft()
        #print(val)
        if val-1 >= 0 and d[i][val-1] == INF:
            que.append(val-1)
            d[i][val-1] = d[i][val] + 1
        if val+1 < n and d[i][val+1] == INF:
            que.append(val+1)
            d[i][val+1] = d[i][val] + 1
        if val == x and d[i][y] == INF:
            que.append(y)
            d[i][y] = d[i][val] + 1
        if val == y and d[i][x] == INF:
            que.append(x)
            d[i][x] = d[i][val] + 1
    return d[i]

for i in range(n-1):
    val = bfs(i)
    #print(val)
    for j in range(i+1,n):
        ans[val[j]] += 1
for i in range(1, n):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# 入力
N, X, Y = map(int, input().split())
Graph = [[] for _ in range(N)]
for i in range(N):
    if i < N - 1:
        Graph[i].append(i + 1)
        Graph[i + 1].append(i)
    if X == i:
        Graph[X - 1].append(Y - 1)
        Graph[Y - 1].append(X - 1)
# print(Graph)
ans = [0] * (N - 1)
from collections import deque
# 全ての点からDFSを行い、最短距離を求める
for i in range(N):
    dist = [-1]*N
    que = deque([i])
    dist[i] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in Graph[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    # print(dist)
    # 最短距離の個数をansに格納する
    for d in dist:
        if d > 0:
            ans[d - 1] += 1
# 全ての点からの最短距離を格納した。
# 条件1 <= i < j <= Nより、1 => 2はカウントするが、2 => 1はカウントしない。
# そのため、2で割って帳尻合わせを行う。
for a in ans:
    print(a // 2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = [0]*n
for i in range(1, n+1):
  for j in range(i, n+1):
    if i <= j:
      ji = j - i
      xi = i - x
      jy = y - j
      l = [ji,  np.abs(xi) + 1 + np.abs(jy)]
      m = min(l)
      ans[m] += 1
      
print(*ans[1:], sep = '\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

ans = [0] * (N)
X -= 1
Y -= 1

for i in range(N):
    dist = [None] * N
    q = deque()
    def push(v, d):
        if(dist[v] is not None):
            return;
        dist[v] = d
        q.append(v)
    push(i, 0)
    while(len(q)>0):
        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 j in range(N):
        ans[dist[j]]+=1

for i, d in enumerate(ans):
    if i != 0:
        print(int(d/2.))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D - Line++
# 標準入力の取得
N,X,Y = list(map(int, input().split()))

# 求解
# (i, j)間の最短距離はmin{|j-i|, |X-i|+1+|j-Y|, |Y-i|+1+|j-X|}であるため、
# (i, j)が決まれば、最短距離はO(1)で決まる。したがって、全(i, j)について、最短距離を求める。
k_list = [0 for i in range(1,N)]
for i in range(1, N):
    for j in range(i+1, N+1):
        min_path = min([abs(j-i), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)])
        k_list[min_path-1] += 1

# 結果出力
for k in k_list:
    print(k)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# D - Line++
# モジュールのインポート
import itertools

# 標準入力の取得
N,X,Y = list(map(int, input().split()))

# 求解
# (i, j)間の最短距離はmin{|j-i|, |X-i|+1+|j-Y|, |Y-i|+1+|j-X|}であるため、
# (i, j)が決まれば、最短距離はO(1)で決まる。したがって、全(i, j)について、最短距離を求める。
k_list = [0 for i in range(1,N)]
for i,j in itertools.product(range(1,N+1), range(1,N+1)):
    # 1 <= i < j <= Nでなければ、何もしない
    if i >= j:
        continue

    min_path = min([abs(j-i), abs(X-i)+1+abs(j-Y), abs(Y-i)+1+abs(j-X)])
    k_list[min_path-1] += 1


# 結果出力
for k in k_list:
    print(k)

Submission status: Time Limit Exceeded

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

dis = []

for i in range(1, N):
    for j in range(i + 1, N + 1):
        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)

        dis.append(d)

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

Submission status: Time Limit Exceeded

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

dis = dict(zip(range(1, N), [0 for _ in range(1, N)]))

for i in range(1, N):
    for j in range(i + 1, N + 1):
        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)

        dis[d] += 1

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

Submission status: Time Limit Exceeded

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

dis = {}
for k in range(1, N):
    dis[k] = 0

for i in range(1, N):
    for j in range(i + 1, N + 1):
        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)

        dis[d] += 1

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

Submission status: Time Limit Exceeded

Solution code:
n, x, y = map(int, input().split())
anslist = [0] * n
list = []
for m in range(1, n + 1):
    for n in range(m, n + 1):
        if m != n:
            list.append([m, n])
while len(list) != 0:
    dis = list[0][1] - list[0][0]
    warpdis = (abs(x - list[0][0])) + (abs(list[0][1] - y)) + 1
    anslist[min(dis, warpdis)] += 1
    list.pop(0)
for i in range(1, n):
    print(anslist[i])

Submission status: Time Limit Exceeded

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

g = [[] for _ in range(N)]
for i in range(N - 1):
    u = i
    v = i + 1
    g[u].append(v)
    g[v].append(u)
g[X - 1].append(Y - 1)
g[Y - 1].append(X - 1)

from collections import deque
dis = [[0] * N for _ in range(N)]
def bfs(i):
    visited = [False] * N
    que = deque([i])
    dis[i][i] = 0
    visited[i] = True
    
    while que:
        p = que.popleft()
        for new in g[p]:
            if visited[new]:
                continue
            else:
                visited[new] = True
                que.append(new)
                dis[i][new] = dis[i][p] + 1
                count[dis[i][new] - 1] += 1

count = [0] * (N - 1)
for i in range(N):
    bfs(i)

for i in range(N - 1):
    print(count[i] // 2)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from queue import deque


def push(d, v, n, q, dist):
    if v < 0 or n <= v:
        return
    if dist[v] is not None:
        return
    dist[v] = d
    q.append(v)


def main():
    n, x, y = [int(x) for x in stdin.readline().rstrip().split()]
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        dist = [None] * n
        q = deque()

        push(0, i, n, q, dist)
        while len(q):
            v = q.popleft()
            d = dist[v]
            push(d + 1, v - 1, n, q, dist)
            push(d + 1, v + 1, n, q, dist)
            if v == x:
                push(d + 1, y, n, q, dist)
            if v == y:
                push(d + 1, x, n, q, dist)

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

    ans = [x // 2 for x in ans]
    print(*ans[1:], sep='\n')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = []
for i in range(1, n+1):
  for j in range(i, n+1):
    ji = j - i
    xi = x - i
    jy = j - y
    l = [ji,  np.abs(xi) + 1 + np.abs(jy)]
    m = min(l)
    ans.append(m)
      
    
for k in range(n-1):
  print(ans.count(k+1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = []
for i in range(1, n+1):
  for j in range(i, n+1):
    ji = i - j
    xi = i - x
    jy = y - j
    l = [np.abs(ji),  np.abs(xi) + 1 + np.abs(jy)]
    m = min(l)
    ans.append(m)
      
    
for k in range(n-1):
  print(ans.count(k+1))

Submission status: Time Limit Exceeded

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

for i in range(1, n):
    for j in range(i + 1, n + 1):
        diff1 = j - i
        diff2 = x + y - i - j + 1
        if i <= x and j >= y:
            diff2 = x - y - i + j + 1
        elif x <= i <= y and x <= j <= y:
            diff2 = -x + y + i - j + 1
        elif x < i < y and j > y:
            diff2 = -x - y + i + j + 1
        if diff2 < 1:
            diff2 = diff1
        diff = min(diff1, diff2)
        ans.append(diff)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k, a in enumerate(visited):
        if k > i:
            if a >= 1:
                distance[a-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = []
for i in range(1, n+1):
  for j in range(i, n+1):
    ji = i - j
    xi = i - x
    jy = y - j
    yi = i - y
    jx = x - j
    l = [np.abs(ji),  np.abs(xi) + 1 + np.abs(jy)]
    m = min(l)
    ans.append(m)
      
    
for k in range(n-1):
  print(ans.count(k+1))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from queue import deque


def main():
    n, x, y = [int(x) for x in stdin.readline().rstrip().split()]
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        dist = [None] * n
        q = deque()

        def push(d, v):
            if v < 0 or n <= v:
                return
            if dist[v] is not None:
                return
            dist[v] = d
            q.append(v)

        push(0, i)
        while len(q):
            v = q.popleft()
            d = dist[v]
            push(d + 1, v - 1)
            push(d + 1, v + 1)
            if v == x:
                push(d + 1, y)
            if v == y:
                push(d + 1, x)

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

    ans = [x // 2 for x in ans]
    print(*ans[1:], sep='\n')


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

ans = []
for i in range(1, n+1):
  for j in range(1, n+1):
    if i <= j:
      ji = i - j
      xi = i - x
      jy = y - j
      yi = i - y
      jx = x - j
      l = [np.abs(ji),  np.abs(xi) + 1 + np.abs(jy)]
      m = min(l)
      ans.append(m)
      
    
for k in range(n-1):
  print(ans.count(k+1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
if True:
    n,x,y = map(int, input().split())


else:
    # n=5
    # x=2
    # y=4
    # n=3
    # x=1
    # y=3
    n=7
    x=3
    y=7

# print(n)
# print(x)
# print(y)
#
ret = [0] * (n-1)
for i in range(1, n):
    for j in range(i+1, n+1):
        # print(str(i) + "," + str(j))
        p =[]
        p.append(j - i)
        p.append(abs(i - x) + 1 + abs(j - y))
        p.append(abs(i - y) + 1 + abs(j - x))

        # print(p)
        # print(min(p))
        ret[min(p)-1] += 1

# print(ret)
# print("=======")
for data in ret:
    print(data)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

f_inf = float('inf')

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

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

ans = [0]*n
for sv in range(n):
    dist = [f_inf] * n
    que = deque([])
    push(sv, 0)

    while que:
        v = que.popleft()
        d = dist[v]+1
        if v-1 >= 0: push(v-1, d)
        if v+1 < n: push(v+1, d)
        if v == x: push(y, d)
        if v == y: push(x, d)

    for i in range(n):
        ans[dist[i]] += 1
        
for i in range(n):
    ans[i] = ans[i]//2

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from queue import Queue


def main():
    n, x, y = [int(x) for x in stdin.readline().rstrip().split()]
    x -= 1
    y -= 1
    ans = [0] * n
    for i in range(n):
        dist = [None] * n
        q = Queue()

        def push(d, v):
            if v < 0 or n <= v:
                return
            if dist[v] is not None:
                return
            dist[v] = d
            q.put(v)

        push(0, i)
        while not q.empty():
            v = q.get()
            d = dist[v]
            push(d + 1, v - 1)
            push(d + 1, v + 1)
            if v == x:
                push(d + 1, y)
            if v == y:
                push(d + 1, x)

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

    ans = [x // 2 for x in ans]
    print(*ans[1:], sep='\n')


if __name__ == "__main__":
    main()