Problem K
Ég elska hann
Languages
en
is
She let the flower decide whether she should talk to him. She started by numbering the petals from $1$ to $N$ counter-clockwise, where $N$ is the number of petals.
She starts at petal $1$ and says “He loves me”. She leaves this petal be and moves onto petal $2$. She then says “He loves me not” and rips petal $2$ off. She then moves to the third petal and says “He loves me”. She continues like this, alternating between the two, going around and around until there is only one petal left.
Can you count along with Gunna and tell her what the number of the last petal will be?
Input
The integer $1 \leq N$, the number of petals on the flower at the start.
Output
One line with the number of the petal that’s left at the end.
Exaplanation of Sample Inputs
Gunna does the following in the first sample:
-
She starts at petal $1$, and says “He loves me”.
-
She moves to petal $2$, says “He loves me not”, and rips the petal off.
-
She moves to petal $3$, and says “He loves me”.
-
She moves to petal $4$, says “He loves me not”, and rips the petal off.
-
She moves to petal $5$, and says “He loves me”.
-
She moves to petal $1$, says “He loves me not”, and rips the petal off.
-
She moves to petal $3$, which is the last petal.
Scoring
The solution will be tested on input data of varying difficulty and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.
|
Group |
Points |
Constraints |
|
1 |
20 |
$N \le 10$ |
|
2 |
40 |
$N \le 1000$ |
|
3 |
40 |
$N \le 10^6$ |
|
4 |
30 |
$N \le 10^{18}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
5 |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
10 |
5 |
