問題一覧 > 通常問題

No.1402 ビル街

レベル : / 実行時間制限 : 1ケース 3.153秒 / メモリ制限 : 315 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 30
作問者 : CuriousFairy315CuriousFairy315 / テスター : ミドリムシ+ミドリムシ+
2 ProblemId : 3094 / 出題時の順位表
問題文最終更新日: 2021-02-19 23:25:23

問題文

315国の首都はビル街になっており、大通りには道路に面するように一直線上に $N+2$ 個のビルが並んでいます。
ビルの高さを左から順に $a_1, a_2, \cdots, a_{N+2}$ とするとき、現在のビルの高さは $a_1=a_{N+2}=2 \cdot 10^9, a_i=1(1 < i < N+2)$ となっています。
315国は普段から人の通りが多く混雑しており、原因を調査したところビル間を移動する人々が大通りを利用することが原因でした。
そこで、ビルを増築し、間に遊歩道を作ることで混雑を緩和しようとしました。
ビルの増築は、以下の手順で行います。
まず、 $1 < i < N+2$ を満たす各 $i$ について、 $i$ 番目のビルの高さ $a_i$ を $1$ 以上 $10^9$ 以下の値だけ増やします。
その後、各ビルについて自分より左側と右側にある自分以上の高さを持つビルのうち、一番近いビルとの間に遊歩道を作ります。この遊歩道は2つのビル間を双方向に移動することができます。
さて、今ビル $i$ から最小の数の遊歩道のみを使ってビル $j$ に向かうときに使った遊歩道の数を $d_{ij}$ とすると、混雑度は $\sum_{i=2}^{N+1} \sum_{j=2}^{N+1} d_{ij}$ で表されます。
このとき、混雑度が最小になるようなビルの建て方を一つ出力してください。

入力

$N$

  • $1 \leq N \leq 2000$

出力

増築後の各ビルの高さを空白区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
1
出力
2000000000 1000000001 2000000000

両端のビルを忘れないようにしてください。

サンプル2
入力
2
出力
2000000000 315 36000 2000000000

混雑度は2であり、これが最小です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。