No.1402 Building District
タグ : / 解いたユーザー数 34
作問者 :
CuriousFairy315
/ テスター :
Problem Statement
The capital of Country 315 is a district of buildings, and along its main street, $N+2$ buildings stand in a straight line facing the road.
Let the heights of the buildings be $a_1, a_2, \cdots, a_{N+2}$ from left to right. The current heights are $a_1=a_{N+2}=2 \cdot 10^9, a_i=1(1 < i < N+2)$.
Country 315 is usually crowded with heavy foot traffic, and an investigation found that the cause was people using the main street to move between buildings.
Therefore, the country decided to relieve the congestion by extending the buildings and constructing promenades between them.
The buildings are extended by the following procedure.
First, for each $i$ satisfying $1 < i < N+2$, increase the height $a_i$ of the $i$-th building by a value between $1$ and $10^9$, inclusive.
Then, for each building, among the buildings of height greater than or equal to its own on its left side and on its right side, a promenade is constructed between it and the nearest such building. Each promenade allows movement in both directions between the 2 buildings.
Now, let $d_{ij}$ be the number of promenades used when going from building $i$ to building $j$ using only promenades and using the minimum number of them. The congestion degree is expressed as $\sum_{i=2}^{N+1} \sum_{j=2}^{N+1} d_{ij}$.
Output one way of constructing the buildings that minimizes the congestion degree.
Input
$N$
- $1 \leq N \leq 2000$
Output
Output the height of each building after the extension, separated by spaces.
Print a newline at the end.
Sample
Sample 1
Input
1
Output
2000000000 1000000001 2000000000
Do not forget the buildings at both ends.
Sample 2
Input
2
Output
2000000000 315 36000 2000000000
The congestion degree is 2, and this is the minimum.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。