No.1991 Secret Garden
タグ : / 解いたユーザー数 12
作問者 :
riano
/ テスター :
cn_449
milkcoffee
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
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もしくは右上の雲マークをクリックしてアカウントを作成してください。