/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
1 から N までの番号がつけられた N 個の頂点を持つ無向グラフ G があります。 G には、以下のように合計 N 本の辺があります。
- i=1,2,...,N-1 について、頂点 i と頂点 i+1 の間に辺があります
- 頂点 X と頂点 Y の間に辺があります
k=1,2,...,N-1 について、以下の問題を解いてください。
- 整数の組 (i,j) (1 \leq i < j \leq N) であって、 G において頂点 i と頂点 j の最短距離が k であるようなものの数を求めてください
制約
- 3 \leq N \leq 2 \times 10^3
- 1 \leq X,Y \leq N
- X+1 < Y
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X Y
出力
k=1,2,...,N-1 に対する問題の答えを、順番に一行に出力せよ。
入力例 1
5 2 4
出力例 1
5 4 1 0
この入力中のグラフは以下のようなものです。
頂点 i と 頂点 j の距離が 1 になるような整数の組 (i,j) (1 \leq i < j \leq N) は、
(1,2)\,,(2,3)\,,(2,4)\,,(3,4)\,,(4,5) の 5 つです。
頂点 i と 頂点 j の距離が 2 になるような整数の組 (i,j) (1 \leq i < j \leq N) は、
(1,3)\,,(1,4)\,,(2,5)\,,(3,5) の 4 つです。
頂点 i と 頂点 j の距離が 3 になるような整数の組 (i,j) (1 \leq i < j \leq N) は、
(1,5) の 1 つだけです。
頂点 i と 頂点 j の距離が 4 になるような整数の組 (i,j) (1 \leq i < j \leq N) はありません。
入力例 2
3 1 3
出力例 2
3 0
この入力中のグラフは以下のようなものです。
入力例 3
7 3 7
出力例 3
7 8 4 2 0 0
入力例 4
10 4 8
出力例 4
10 12 10 8 4 1 0 0 0
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