問題一覧 > 通常問題

No.1402 Building District

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 34
作問者 : CuriousFairy315 / テスター : ミドリムシ
お気に入りにしたユーザー ProblemId : 3094 / 自分の提出
問題文最終更新日: 2021-04-09 01:03:47
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 283 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。