Type: Default

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【西双版纳的孔雀舞】

题目背景

在美丽的西双版纳，一年一度的孔雀舞选拔赛正在举行。来自各个村寨的 $N$ 名舞者排成一排，每位舞者都有一个初始编号，从左往右依次为 $1, 2, 3, \dots, N$ 。为了选出最优秀的“孔雀王”，评审团制定了一套独特的淘汰规则。

选拔赛按轮次进行，每一轮都会淘汰掉当前队列中一半左右的舞者。具体规则如下：

第一轮：从左往右进行。淘汰掉当前序列中的第 $1$ 个舞者，然后每隔一个舞者淘汰一个（即淘汰第 $1, 3, 5, \dots$ 个舞者）。
第二轮：从右往左进行。淘汰掉当前序列中从右数起的第 $1$ 个舞者，然后每隔一个舞者淘汰一个（即从右往左数，淘汰第 $1, 3, 5, \dots$ 个舞者）。
第三轮：再次从左往右进行，淘汰规则同第一轮。
第四轮：再次从右往左进行，淘汰规则同第二轮。

如此往复，淘汰方向在“从左往右”和“从右往左”之间轮流切换。直到队列中只剩下最后一名舞者。这名舞者将获得“孔雀王”的称号。

给定舞者的总人数 $N$ ，请你计算出最终剩下的这名舞者的原始编号是多少。

输入仅一行，包含一个正整数 $N$ 。

输出一个整数，表示最后剩下的那名舞者的原始编号。

样例 1 输入：

样例 1 输出：

样例 2 输入：

样例 2 输出：

对于样例 1 ( $N=9$ )：

第一轮（左 $\to$ 右）：初始序列为 $[1, 2, 3, 4, 5, 6, 7, 8, 9]$ 。淘汰第 $1, 3, 5, 7, 9$ 个，剩下 $[2, 4, 6, 8]$ 。
第二轮（右 $\to$ 左）：当前序列为 $[2, 4, 6, 8]$ 。从右往左数，第 $1$ 个是 $8$ ，第 $3$ 个是 $4$ 。淘汰 $8, 4$ ，剩下 $[2, 6]$ 。
第三轮（左 $\to$ 右）：当前序列为 $[2, 6]$ 。从左往右数，第 $1$ 个是 $2$ 。淘汰 $2$ ，剩下 $[6]$ 。
最终结果为 $6$ 。