問題一覧 > 通常問題

No.1991 Secret Garden

レベル : / AI推定難易度 : 2400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 12
作問者 : riano / テスター : cn_449 tokusakurai milkcoffee
お気に入りにしたユーザー ProblemId : 7460 / 自分の提出
問題文最終更新日: 2022-06-05 22:58:06
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 349 (順位表) の他の問題:

Problem Statement

You want to plant flowers in a row in the flower bed of your garden. The flower bed has equally spaced coordinates $x=1,2,...,N$ assigned from left to right, and you need to plant flowers of heights $h = 1,2,...,N$, with $1$ flower in each $1$ location.

There is a balcony at each end of the flower bed, and depending on how the flowers are planted, some flowers can be seen from each balcony and others cannot. Specifically, the view from a balcony is always looking down at an angle of $45$ degrees, and a flower can be seen if its "height + distance" as seen from that location is strictly greater than that of every closer flower. That is,

  • from the left balcony, you can see the flowers whose value of $h+x$ is strictly greater than that of every flower to their left
  • from the right balcony, you can see the flowers whose value of $h-x$ is strictly greater than that of every flower to their right
(See also the figure in Sample $1$ if necessary.)

When you plant $1$ flower at each of $x=1,2,...N$ in any order you like, what is the maximum possible number of flowers that cannot be seen from either balcony?

Input

$N$

  • $2\leq N \leq 10^{12}$
  • All inputs are integers.

Output

Output the answer as an integer. Print a newline at the end.

Sample

Sample 1
Input
5
Output
2

For example, consider planting the flowers so that $h$ is $(1,5,2,3,4)$ in the order $x=1,2,...,5$. In this case, as shown in the figure below, the $2$ flowers $h=2,3$ ($x=3,4$) are the "flowers that cannot be seen from either balcony". In fact, it is impossible to make $3$ or more flowers unseen, so $2$ is the answer in this case.

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