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: Accepted

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

# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
G = [[] for i in range(N)]
G[X - 1].append(Y - 1)
for i in range(N - 1):
    G[i].append(i + 1)
    G[i + 1].append(i)
# print(G)


def bfs(start):
    dist = [-1] * N
    que = deque([start])
    dist[start] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            que.append(w)
    return dist


ans = [0] * N

for i in range(N - 1):
    # print(bfs(i))
    for ele in bfs(i)[i + 1:]:
        ans[ele] += 1
for a in ans[1:]:
    print(a)

Submission status: Accepted

Solution code:
N, X, Y = [int(i) for i in input().split()]
li = [0]*(N-1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        k = 0
        if(i<X and j<X):
            k = j-i
        if(i<X and X<=j<=Y):
            k = min(j-i, X-i+1+Y-j)
        if(i<X and Y<j):
            k = X-i+1+j-Y
        if(X<=i<=Y and X<=j<=Y):
            k = min(j-i, i-X+1+Y-j)
        if(X<=i<=Y and Y<j):
            k = min(j-i, i-X+1+j-Y)
        if(Y<i and Y<j):
            k = j-i
        li[k-1] += 1

for i in li:
    print(i)

Submission status: Accepted

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

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

import heapq

def dijkstra(start, edge, n):

    dist = [float('inf')] * n
    dist[start] = 0

    pq = [(dist[start], start)]

    while len(pq):
        d, frm = heapq.heappop(pq)
        if dist[frm] < d:
            continue
        for to, cost in edge[frm]:
            if dist[frm] + cost < dist[to]:
                dist[to] = dist[frm] + cost
                heapq.heappush(pq, (dist[to], to))

    return dist

cnt = [0] * n

for i in range(n):
    dist = dijkstra(i, edges, n)
    for d in dist:
        cnt[d] += 1

cnt2 = []
for c in cnt:
    c //= 2
    cnt2.append(c)

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

Submission status: Accepted

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

d=[[10**9]*N for _ in range(N)]

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

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

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

Submission status: Accepted

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

x -= 1
y -= 1

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

l = [0 for _ in range(n)]
for i in range(n-1):
    for j in range(i+1, n):
        if j <= x or y <= i:
            k = j - i
        elif i <= x and y <= j:
            k = g[j] - g[i]
        else:
            # 通常
            k = j - i
            # i -> x, j -> y経由
            _k = abs(x - i) + abs(y - j) + 1
            k = min(k, _k)
        l[k] += 1

for k in l[1:]:
    print(k)

Submission status: Accepted

Solution code:
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def dijkstra(start):
    INF = 10 ** 10
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0,start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

N, X, Y = lr()
answer = [0] * N # 1-indexed
graph = [[] for _ in range(N+1)] # 1-indexed
for i in range(1, N):
    graph[i].append(i+1)
    graph[i+1].append(i)
graph[X].append(Y)
graph[Y].append(X)

dist_X = dijkstra(X)
dist_Y = dijkstra(Y)
for i in range(1, N):
    for j in range(i+1, N+1):
        d = min(j-i, dist_X[i] + dist_X[j], dist_Y[i] + dist_Y[j])
        answer[d] += 1

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

Submission status: Accepted

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

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

# 各頂点同士の距離を求める
for i in range(1, N):
    for j in range(i+1, N + 1):
        if i <= X and Y <= j:
            distance = (X-i) + 1 + (j-Y)
        if i <= X and j < Y:
            distance = (X-i) + min(j-X, 1+(Y-j))
        if X < i and Y <= j:
            distance = min(Y-i, i-X+1) + (j-Y)
        if X < i and j < Y:
            distance = min(j-i, (i-X)+(Y-j)+1)

        distance_counter[distance-1] += 1

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

Submission status: Accepted

Solution code:
#どっちで出すか注意, rstrip注意
#提出前に見返すこと！
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    inf = 10**17
    #mod = 10**9 + 7

    def dijkstra_heap(start,edge):
        #始点から各頂点への最短距離(頂点番号:0~N-1)
        d = [inf]*N
        used = [False]*N
        d[start] = 0
        used[start] = True
        edgelist = []
        #a:重み(//), b:次の頂点(%)
        for a,b in edge[start]:
            heapq.heappush(edgelist,a*(10**6)+b)

        while len(edgelist):
            #まだ最短距離が決まっていない頂点の中から最小の距離のものを探す
            minedge = heapq.heappop(edgelist)
            if used[minedge%(10**6)]:
                continue
            node = minedge%(10**6)
            d[node] = minedge//(10**6)
            used[node] = True

            for e in edge[node]:
                if not used[e[1]]:
                    heapq.heappush(edgelist,(e[0]+d[node])*(10**6)+e[1])
        return d

    #N:頂点数   W:辺数
    N, X, Y = map(int, input().split())
    edge = [[] for i in range(N)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(N-1):
        edge[i].append((1,i+1))
    for i in range(Y-1, X-1, -1):
        edge[i].append((1, i-1))
    edge[X-1].append((1, Y-1))
    res = [0]*N
    for k in range(N):
        d = dijkstra_heap(k, edge)
        for i in d[k+1:]:
            res[i] += 1
    for r in res[1:]:
        print(r)

            


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X,Y=map(int,input().split())
G=[[0 for i in range(N)] for i in range(N)]
for i in range(0, N):
    for j in range(0, N-i):
        G[i][i+j]=j
G[X-1][Y-1]=1
for i in range(Y-1,N-1):
    G[X-1][i+1]=G[X-1][i]+1
for i in range(0,N):
    if G[X-1][Y-2-i]<G[X-1][Y-1-i]+1:
        break
    else:
        G[X-1][Y-2-i]=G[X-1][Y-1-i]+1
for i in range(0, N):
    #a=G[i][X-1]
    a=abs(i-(X-1))
    for j in range(i,N-1):
        G[i][j+1]=min(G[i][j+1], a+G[X-1][j+1])
ans=[0 for i in range(N)]
for i in range(0,N):
    for j in range(0,N-i):
        ans[G[i][i+j]]+=1
for i in range(N-1):
    print(ans[i+1])

Submission status: Accepted

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

res = {}
for i in range(1, N):
    res[i] = 0

for i in range(1, N):
    for j in range(i+1, N+1):
        if i <= X and j >= Y:
            min_dis = min(j-i, (X-i)+(j-Y)+1)
        elif i <= X and j < Y:
            min_dis = min(j-i, (X-i)+(Y-j)+1)
        elif i > X and j >= Y:
            min_dis = min((j-i), (i-X)+(j-Y)+1)
        elif i > X and j < Y:
            min_dis = min((j-i), (i-X)+(Y-j)+1)

        res[min_dis] += 1

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

Submission status: Accepted

Solution code:
import heapq
import sys

input = sys.stdin.readline

def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

################################
n,s,t = map(int,input().split()) #n:頂点数　w:辺の数
w=n-1

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y=i,i+1 #0-indexed
    edge[x].append([1,y])
    edge[y].append([1,x]) 
edge[s-1].append([1,t-1])
edge[t-1].append([1,s-1]) 

distance=dijkstra_heap(0,edge)
memo=[0]*n

for i in range(n-1):#i to j
    for j in range(i+1,n):
        if s-1<i<t-1:#s==2,t==4
            tmp=min(j-i,distance[i]+distance[j]-distance[s-1]*2)
        else:
            tmp=distance[j]-distance[i]

        memo[tmp]+=1
for i in range(1,n):
    print(memo[i])

Submission status: Accepted

Solution code:
from itertools import combinations
def Main(N, X, Y):
    ar = range(N)
    X -= 1
    Y -= 1
    comb = combinations(ar, 2)
    ans = {i:0 for i in range(N-1)}
    for i, j in comb:
        dist = 0
        if i <= X and Y <= j:
            dist = X - i + j - Y + 1
        elif i > X and Y <= j:
            dist = min(i-X + 1 + j-Y, j-i)
        elif i <= X and Y > j:
            dist = min(X-i + 1 + Y-j, j-i)
        else:
            dist = min(i-X + 1 + Y-j, j-i)
        ans[dist-1] += 1
    return ans.values()

def main():
    N, X, Y = map(int, input().split())
    out = Main(N, X, Y)
    for e in out:
        print(e)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def f(N,X,Y):
  for i in range(1,N):
    for j in range(i+1,N+1):
      if i <= X and j <= X:
        dic = j-i
      elif i >= Y and j >= Y:
        dic = j-i
      elif i <= X and j >= Y:
        dic = (j-i)-(Y-X)+1
      elif X < i < Y and j >= Y:
        dic = min(i-X+1,Y-i)+(j-Y)
      elif i<=X and X < j < Y:
        dic = (X-i)+min(Y-j+1,j-X)
      elif X < i < Y and X < j < Y:
        dic = min(j-i,(i-X+1)+(Y-j))
      ans[dic-1] = ans[dic-1]+1
  
f(n,x,y)
for ret in ans:
  print(ret)

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
ans = [0] * (N - 1)
X, Y = X - 1, Y - 1
Z = Y - X - 1

for i in range(N):
  if i <= X:
    for j in range(i + 1, Y):
      p = min(j - i - 1, abs(i - X) + Y - j)
      ans[p] += 1
    for l in range(Y, N):
      ans[l - i - Z - 1] += 1
      
  elif (X < i) and (i < Y - 1):
    for j in range(i + 1, N):
      p = min(j - i - 1, abs(i - X) + abs(Y - j))
      ans[p] += 1  
      
  else:#Y <= i
    for j in range(i + 1, N):
      ans[j - i - 1] += 1
  #print(ans)
for i in range(N - 1):
  print(ans[i])

Submission status: Accepted

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

def f(i,j):
  if j <= X:
    return j-i
  elif Y <= i:
    return j-i
  elif X <= i and j <= Y:
    return min(j-i,(i-X)+1+(Y-j))
  elif i <= X and Y <= j:
    return (X-i)+1+(j-Y)
  elif i <= X and X <= j and j <= Y:
    return (X-i)+min(j-X,1+(Y-j))
  else:
    return (j-Y)+min(Y-i,(i-X)+1)

A = [0]*(N-1)

for k in range(1,N,1):
  for l in range(k+1,N+1,1):
    A[f(k,l)-1] += 1

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

Submission status: Accepted

Solution code:
import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

N, X, Y = mi()

dp = [0]*(N)

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

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

Submission status: Accepted

Solution code:
from collections import deque
from collections import Counter
N, X, Y = map(int, input().split())
X -= 1
Y -= 1
dis_lis = deque()
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i-j)==1:
            dis_lis.append(1)
        else:
            min1 = abs(i-j)
            min2 = abs(i-X)+abs(j-Y)+1
            min3 = abs(i-Y)+abs(j-X)+1
            dis_lis.append(min(min1, min2, min3))
c = Counter(dis_lis)
for i in range(1, N):
    print(c[i])

Submission status: Accepted

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


ans = [0] * N
for i in range(1, N+1):
    for j in range(i+1, N+1):
        d = 0
        if i <= X and j <= X:
            d = j - i
        elif i <=X and j > X and j <= Y:
            d = min(j-i, X-i+1+Y-j)
        elif i <= X and j > Y:
            d = X - i + 1 + j - Y
        elif i > X and i <= Y and j > X and j <= Y:
            d = min(j-i, i-X+1+Y-j)
        elif i > X and i <= Y and j > Y:
            d = min(j-i, i-X+1+j-Y)
        elif i > X and j > Y:
            d = j - i
        ans[d] += 1

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

Submission status: Accepted

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

for frm in range(N-1):
    for to in range(frm+1, N):
        key = min(to-frm, abs((X-1) - frm) + 1 + abs((Y-1) - to))
        #print(frm, to, key)
        count[key] += 1
# print(count)
print(*[count[i] for i in range(1, N)], sep='\n')

Submission status: Accepted

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

ans = [0 for i in range(N+1)]

for i in range(1,N+1):
  for j in range(i+1,N+1):
    if i < X :
      if j < X:
        a = j - i
        ans[a] += 1
      elif j >= X and j < Y:
        a = j - i
        b = (X-i) + 1 + (Y-j)
        c = min(a,b)
        ans[c] += 1
      else:
        a =  (X-i)+ 1 + (j - Y)
        ans[a] += 1
        
    elif i >= X and i < Y:
      if j < Y:
        a = j - i
        b = (i-X) + 1 + (Y-j)
        c = min(a,b)
        ans[c] += 1
      else:
        a = j -i
        b =  (i-X) + 1 + (j - Y)
        c = min(a,b)
        ans[c] += 1
        
    else:
      a = j - i
      ans[a] += 1
        
for i in range(1,N):
  print(int(ans[i]))

Submission status: Accepted

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

    count = {i: 0 for i in range(1, n)}
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            # i, j <= X, or Y <= i, j
            if (i <= x and j <= x) or (x <= i and y <= j):
                d = j - i
            
            # X < i, j < Y
            if x < i and j < y:
                d = min(j - i, i - x + 1 + y - j)
            
            # i <= X and X < j < Y
            if i <= x and x < j < y:
                d = min(j - i,
                        x - i + 1 + y - j)            

            # X < i < Y and Y <= j
            if x < i < y and y <= j:
                d = min(j - i,
                        j - y + 1 + i - x)

            if i <= x and y <= j:
                d = min(j - i,
                        x - i + j - y + 1)
            count[d] += 1            
            

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

submit()

Submission status: Accepted

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

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

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

for i in range(1,X+1):
  for j in range(X+1,Y):
    d=j-i
    e=(X-i)+1+(Y-j)
    f=min(d,e)
    A[f]+=1

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

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

Submission status: Accepted

Solution code:
import sys
INPUT=input().split()
N=int(INPUT[0])
X=int(INPUT[1])
Y=int(INPUT[2])
LENGTH=[0]*(N-1)
for i_a in range(1,N):
    for i_b in range(i_a+1,N+1):
        way_a=i_b-i_a
        way_b=abs(X-i_a)+abs(Y-i_b)+1
        LENGTH[min(way_a,way_b)-1]+=1

for _ in range(N-1):
    print(LENGTH[_])

Submission status: Accepted

Solution code:
from collections import deque
n,x,y=map(int,input().split())
edge=[[] for _ in range(n)]
edge[x-1].append(y-1)
edge[y-1].append(x-1)
for i in range(n-1):
  edge[i].append(i+1)
  edge[i+1].append(i)
visited=[[-1]*n for _ in range(n)]
def bfs(s):
  q=deque([s])
  visited[s][s]=0
  while q:
    x=q.popleft()
    for nx in edge[x]:
      if visited[s][nx]==-1:
        visited[s][nx]=visited[s][x]+1
        q.append(nx)
for i in range(n):
  bfs(i)
ans=[0]*n
for i in range(n):
  for j in range(n):
    if i<j:
      continue
    if visited[i][j]>=1:
      ans[visited[i][j]]+=1
for i in range(1,n):
  print(ans[i])

Submission status: Accepted

Solution code:
N, X, Y = map(int, input().split())
dist = [[0] * (N+1) for _ in range(N+1)]
cnt = [0] * N
for i in range(1, N):
    for j in range(i + 1, N+1):
        dist = min(j - i, abs(i - X) + 1 + abs(j - Y), abs(i - Y) + 1 + abs(j - X))
        cnt[dist] += 1
print(*cnt[1:], sep='\n')

Submission status: Accepted

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

result={}
for i in range(1,n):
    result[i]=0

for i in range(1,n):
    for j in range(i+1,n+1):
        #print(i,j)
        if j-i==1:
            result[1]+=1
        else:
            temp=min(j-i,abs(x-i)+1+abs(j-y))
            result[temp]+=1
for i in range(1,n):
    print(result[i])

Submission status: Accepted

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

ans = [0] * n 
for i in range(1, n + 1):
  # D[j]はiとjの最短距離
  D = [0] * (n  + 1)
  for j in range(i, n + 1):
    D[j] = min(j - i, abs(x - i) + abs(y - j) + 1)
  for d in D:
    ans[d] += 1
    
for a in ans[1:]:
  print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def shortcut_path(src, dst, x, y):
    path = abs(src - x)
    path += 1 # shortcut
    path += abs(dst - y)
    return path

def normally_path(src, dst):
    return dst - src

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

for i in range(1, N):
    for j in range(i+1, N+1):
        np = normally_path(i, j)
        sp = shortcut_path(i, j, X, Y)
        path = min(np, sp)
        if path in shortest_paths:
            shortest_paths[path] += 1
        else:
            shortest_paths[path] = 1

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

Submission status: Accepted

Solution code:
n, x, y = list(map(int, input().split(' ')))
k = n - 1
result = [0] * k

for i in range(n):
    for j in range(i + 1, n):
        if j <= x - 1or x >= y - 1:
            result[j - i - 1] += 1
        else:
            r1 = j - i
            r2 = abs(i - (x - 1)) + 1 + abs((y - 1) - j)

            v = min([r1, r2])
            result[v - 1] += 1
        
for i in result:
    print(i)

Submission status: Accepted

Solution code:
def main():
    n,x,y=map(int,input().split())
    Ans=[0]*n
    for i in range(1,n):
        for j in range(i+1,n+1):
            if i<=x and y<=j:
                d=x-i+j-y+1
            elif i<=x and x<=j<=y:
                d=min(j-i,x-i+1+y-j)
            elif x<=i<=y and j>=y:
                d=min(j-i,i-x+1+j-y)
            elif x<=i<=y and x<=j<=y:
                d=min(j-i,i-x+1+y-j)
            else:
                d=j-i
            #print(i,j,d)
            Ans[d]+=1
    for ans in Ans[1:]:
        print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

answer = [0 for _ in range(n-1)]
for i in range(1, n+1):
    for j in range(i+1, n+1):
        tmp = abs(i-x) + abs(j-y) + 1
        _id = min(j-i, tmp)
        answer[_id-1] += 1
for a in answer:
    print(a)

Submission status: Accepted

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):
    d_o=j-i
    if i<=x and i<=y and j<=x and j<=y:
      d_d=10**4
    elif i>=x and i>=y and j>=x and j>=y:
      d_d=10**4
    elif i<=x and i<=y and j>=x and j>=y:
      d_d=x-i+1+j-y
    elif i<=x and i<=y and x<=j<=y:
      d_d=x-i+1+(y-j)
    elif x<=i<=y and j>=x and j>=y:
      d_d=i-x+1+j-y
    elif x<=i<=y and x<=j<=y:
      d_d=i-x+1+y-j
    else:
      print("###")
    tmp=min(d_o,d_d)
    ans[tmp-1]+=1

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
# print('input >>')
N, X, Y = map(int,(input().split()))
ans = [0] * N

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

# print('-----output-----')
for ans_e in ans[1:]:
    print(ans_e)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    readline=stdin.readline
    N,X,Y=map(int,readline().split())
    X-=1
    Y-=1
    k=[0]*N
    for a in range(N-1):
        for b in range(a+1,N):
            if a<=X and Y<=b:
                k[X-a+b-Y+1]+=1
            else:
                c=min(b-a,abs(X-a)+1+abs(Y-b))
                k[c]+=1

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

import heapq

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

def warshall_floyd(n,d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d





n,x,y = m()

dp = [[mod for i in range(n)] for j in range(n)]

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

for i in range(n-1):
    dp[i][i+1] = 1
for i in range(1,n):
    dp[i][i-1] = 1

dp[x-1][y-1] = 1

dp[y-1][x-1] = 1


po = dijkstra(x-1,n,n,dp)

ppo = dijkstra(y-1,n,n,dp)

ans = [0 for i in range(n)]

for i in range(n):
    for j in range(n):
        on = min(abs(i-j),po[i]+po[j],ppo[i]+ppo[j],po[i]+ppo[j] + 1,ppo[i]+po[j] + 1)
            #print(i,j,on)
            #print(ppp[i][j])
        ans[on] += 1
for i in range(1,n):
    print(ans[i]//2)

Submission status: Accepted

Solution code:
from collections import defaultdict
from heapq import heappush, heappop
from collections import deque
n, x, y = list(map(int, input().split()))
G = [[]*n for _ in range(n)]

for i in range(n-1):
    G[i].append((i+1, 1))
    G[i+1].append((i, 1))
G[x-1].append((y-1, 1))
G[y-1].append((x-1, 1))
# print(G)
INF = 10**30
N = n


# s: 開始頂点
# N: 頂点数
# G: グラフ
# G[v][i] = (w, d): 辺v-wのコストは d (0 or 1)
dd = []
for i in range(n):
    s = i
    dist = [10**9] * N
    S = deque([s])
    T = deque()
    dist[s] = 0

    d = 0
    while S:
        while S:
            v = S.popleft()
            for w, c in G[v]:
                if d+c < dist[w]:
                    dist[w] = d+c
                    if c:
                        T.append(w)
                    else:
                        S.append(w)
        S, T = T, S
        d += 1
    dd.append(dist)

ans = defaultdict(lambda: 0)
for dist in dd:
    for t in dist:
        ans[t] += 1
for i in range(n-1):
    print(ans[i+1]//2)

Submission status: Accepted

Solution code:
import heapq
INFTY = 10**4
N,X,Y = map(int,input().split())
G = {1:[2],N:[N-1]}
for i in range(2,N):
    G[i] = [i-1,i+1]
G[X].append(Y)
G[Y].append(X)
dist = [[INFTY for _ in range(N+1)] for _ in range(N+1)]
for s in range(1,N):
    hist = [0 for _ in range(N+1)]
    heap = [(0,s)]
    dist[s][s] = 0
    hist[s] = 1
    while heap:
        d,x = heapq.heappop(heap)
        if d>dist[s][x]:continue
        hist[x] = 1
        for y in G[x]:
            if hist[y]==0 and dist[s][y]>d+1:
                dist[s][y] = d+1
                heapq.heappush(heap,(d+1,y))
C = {k:0 for k in range(1,N)}
for i in range(1,N):
    for j in range(i+1,N+1):
        C[dist[i][j]] += 1
for k in range(1,N):
    print(C[k])

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
n,x,y=map(int,sys.stdin.readline().split())
dis=defaultdict(lambda:10000)
dis=[[0 for _ in range(n)] for a in range(n)]
dis[x-1][y-1]=1
x-=1
y-=1
#print(x,'x',y,'y')
k=[0 for _ in range(n-1)]
for i in range(n):
    for j in range(i+1,n):
        dis[i][j]=j-i
        if i<=x:
            dis_x=x-i
        else:
            dis_x=i-x
        if j<=y:
            dis_y=y-j
        else:
            dis_y=j-y
        dis[i][j]=min(dis[i][j],dis_x+dis_y+1)
        k[dis[i][j]-1]+=1
#print(dis,'dsi')
for i in range(n-1):
    print(k[i])
'''dis[(x-1,y-1)]=1
for i in range(n):
    dis[(i,i)]=0
d=defaultdict(int)
for i in range(n-1,-1,-1):
    for j in range(i+1,n):
        dis[(i,j)]=min(dis[(i,j)],dis[(i+1,j)]+1,dis[(i,j-1)]+1,dis[(i-1,j)]+1,dis[(i,j+1)]+1)
        d[dis[(i,j)]]+=1
#print(dis,'dis')
for i in range(1,n):
    print(d[i])'''

Submission status: Accepted

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

def add_dic(p):
    if not p in distance_dic:
        distance_dic[p] = 1
    else:
        distance_dic[p] += 1

for i in range(x):
    for j in range(i+1,x):
        add_dic(j-i)
    for j in range(x,y):
        add_dic(min(j-i, x+y+1-i-j))
    for j in range(y,n):
        add_dic(x-y+1+j-i)
for i in range(x,y):
    for j in range(i+1,y):
        add_dic(min(j-i, y-x+1+i-j))
    for j in range(y, n):
        add_dic(min(j-i, -x-y+1+i+j))
for i in range(y,n-1):
    for j in range(i+1,n):
        add_dic(j-i)

for k in range(1, n):
    if k in distance_dic:
        print(distance_dic[k])
    else:
        print(0)

Submission status: Accepted

Solution code:
def kyori(a, b, x, y):
    if a > b:
        a, b = b, a
    return min(abs(b - a), abs(x - a) + abs(b - y) + 1)


n, x, y = map(int, input().split())
ans = [0] * (n)

for i in range(1, n + 1):
    for j in range(i + 1, n + 1):
        # print(i, j, kyori(i, j, x, y))
        ans[kyori(i, j, x, y)] += 1
# print(ans)
for i in range(1, n):
    print(ans[i])

Submission status: Accepted

Solution code:
import heapq
# 単一始点最短経路。2地点間ではなく、始点が一つで各点へのコストを計算する
# eは隣接リストでe[v] = [(u1,cost1), (u2,cost2)]みたいな形を想定
# 辺の重みは正である必要がある
# O(ElogV)
def dijkstra(e,n,s):
    inf = 10**18
    d = [inf]*n
    d[s] = 0

    q = [(d[s],s)] # priority queueのソートキーが第一要素
    heapq.heapify([q])
    while len(q)>0:
        _,v = heapq.heappop(q)
        for u,c in e[v]:
            if d[v]+c>=d[u]:
                continue
            d[u] = d[v] + c
            heapq.heappush(q, (d[u],u))
    return d

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

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

res = [0]*n
for i in range(n):
    d = dijkstra(g,n,i)
    for j in range(i+1,n):
        res[d[j]] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,x,y = inpl()
x -= 1; y -= 1
ans = [0] * (n-1)
for i in range(n-1):
    for j in range(i+1,n):
        if i == j: continue
        res = j - i 
        res = min(res, abs(x-i) + abs(y-j) + 1)
        ans[res-1] += 1
print(*ans)

Submission status: Accepted

Solution code:
n,x,y = map(int,input().split())
sc = y - x - 1
nl = [0]*(n-1)
for i in range(1,n+1):
    for j in range(1,n+1):
        if i < j:
            dis = j - i
            if i <= x and j >= y:
                dis -= sc
            elif i >= x and j <= y:
                dis = min(dis,i-x + y-j  +1)
            elif i <= x and j >= x and j <= y:
                dis = min(dis,y-i-sc+y-j)
            elif i >= x and i <= y and j >= y:
                dis = min(dis,j-x-sc+i-x)
            nl[dis-1] += 1
for i in nl:
    print (i)