시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB79252430.769%

문제

Julia wants to celebrate her birthday in a very special way this year -- she wants to invite her friends to an amusement arcade and play all the awesome video arcade games from her childhood with them!

For this purpose she rented a venue with $n$ arcades where all machines are arranged in one straight line. Some of her friends are very vivid players who tend to scream whenever they manage to beat the game. As this is very distracting for the others, Julia rented a venue that is so large that in case the very first and very last machine is occupied, everyone else can be seated such that there is always exactly one empty seat between any two neighbouring players.

Her friends, however, arrive at the amusement arcade one by one and do not know how many people will come in total. To sit as comfortable as possible, they always choose an arcade that is maximally far away from any other player. In case there are multiple machines that are equally secluded, they choose one of them uniformly at random. After having taken a seat, they will stay there until the end of the party.

As the host, Julia is the first person to arrive at the venue. Now she is wondering where she should take a seat such that all of her friends find an arcade to play and there is exactly one empty seat between neighbouring players once everyone is seated.

입력

The input consists of:

  • One line with an integer $n\ (1 \le n \le 10^{18})$, the number of arcades at the venue. The arcades are labelled from $1$ to $n$.

It is guaranteed that $n$ is an odd number.

출력

If it is impossible to find a valid seating, output impossible. Otherwise, output an integer $a$ ($1 \le a \le n$), the label of the arcade at which Julia starts playing. In case there exist multiple valid solutions, any of them will be accepted.

예제 입력 1

7

예제 출력 1

3

예제 입력 2

15

예제 출력 2

impossible

노트

In the first sample there are $n=7$ seats. There will be $4$ players in total, i.e., Julia and three guests. Julia takes a seat on machine $3$. Her first guest will choose machine $7$ as this machine is maximally far away from Julia. Her second guest will either choose machine $1$ or $5$ as both are equally secluded from the other players. Regardless of this choice, the last guest will choose the other of these two machines in both cases. In the end, machines $1$, $3$, $5$, and $7$ are occupied and there is one empty machine between any two neighbouring players.

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > German Collegiate Programming Contest > GCPC 2021 A번

  • 문제를 만든 사람: Gregor Schwarz