問題一覧 > 通常問題

No.831 都市めぐり

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 119
作問者 : Shuz*Shuz* / テスター : 👑 tatyamtatyam
4 ProblemId : 2444 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-24 23:48:28

問題文

ふーりぇ君はShuz国の都市めぐりをしています。
Shuz国には、 $N$ 個の都市があり、それぞれ $1,\ 2,\ 3,\ ...,\ N$ の番号がつけられています。
すべての $2$ 都市間は高速道路で結ばれており、$i \neq j$ のとき、都市 $i,\ j$ 間を移動するのに片道 $(i \times j)$ 円の基本料金がかかります。
また、都市 $i$ から都市 $j$ へ移動するのに、 $i \lt j$ のときは $(j-i)$ 円の追加料金が発生し、 $i \gt j$ のときは $(i-j)$ 円割引されます。
つまり、 $i \neq j$ のとき、都市 $i$ から都市 $j$ へ移動するのに合計 $(i \times j)+(j-i)$ 円かかります。
ふーりぇ君は、好きな都市から始めて、高速道路を使ってShuz国の都市を一周したいです。
ふーりぇ君が、 $N$ 個すべての都市を $1$ 回ずつめぐり最初にいた都市へ戻ってくるために最低限必要な料金を求めて下さい。

制約

  • $1 \le N \le 2 \times 10^6$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

ふーりぇ君がすべての都市を $1$ 回ずつめぐるために最低限必要な料金を出力せよ。

サンプル

サンプル1
入力
3
出力
11

例えば、最も料金の少ない順路の一つは、
都市 $2$ から都市 $1$ まで $1$ 円
都市 $1$ から都市 $3$ まで $5$ 円
都市 $3$ から都市 $2$ まで $5$ 円
合計 $11$ 円
なので、合計料金である $11$ を出力します。

サンプル2
入力
1
出力
0

$1$ つしか都市がない場合は都市をめぐる必要がないので、料金はかかりません。

サンプル3
入力
200
出力
1353499

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