問題一覧 > 通常問題

No.1991 Secret Garden

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : rianoriano / テスター : cn_449cn_449 tokusakuraitokusakurai milkcoffeemilkcoffee
2 ProblemId : 7460 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-05 22:58:06

問題文

あなたは、庭の花壇に一列に花を植えたいと考えています。 花壇には左から順に等間隔に $x=1,2,...,N$ と座標が振られており、高さ $h = 1,2,...,N$ の花を $1$ つの場所に $1$ つずつ植える必要があります。

また、花壇の両端にはバルコニーがあり、植え方によってそれぞれから見ることのできる花と見ることのできない花ができます。 具体的には、バルコニーからは常に $45$ 度の角度で見下ろしており、 それぞれの場所から見た「高さ+距離」が、それより近い花全てより真に大きい花を見ることができます。 すなわち、

  • 左側のバルコニーからは、 $h+x$ の値がその花より左側の花全てより真に大きい花
  • 右側のバルコニーからは、 $h-x$ の値がその花より右側の花全てより真に大きい花
を見ることができます。（必要に応じて、サンプル $1$ の図も参照してください。）

$x=1,2,...N$ に自由な並びで $1$ 本ずつ花を植えるとき、どちらのバルコニーからも見ることのできない花の本数は最大で何本でしょうか。

入力

$N$

  • $2\leq N \leq 10^{12}$
  • 入力は全て整数である

出力

答えを整数で出力してください。 最後に改行してください。

サンプル

サンプル1
入力
5
出力
2

例えば $x=1,2,...,5$ の順に、$h$ が $(1,5,2,3,4)$ となるように花を植えた場合を考えます。 このとき、下の図のように $h=2,3$ ($x=3,4$) の $2$ 本が「どちらのバルコニーからも見えない花」となります。 実は $3$ 本以上を見えなくすることはできませんので、$2$ 本がこの場合の答えです。

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