2025年 北马其顿编程竞赛 (Macedonian programming contests 2025)

赛事等级： 社区与地区级竞赛 (Community and Regional competition)
内容类型： 竞赛题目 (Competition tasks)

题目名称：机器人包装 (Пакување роботчиња)

题目描述

在一个漫长工作日的尽头，工厂流水线上还剩下 $N$ 个机器人（位置编号从 $1$ 到 $N$），米勒（Mile）和埃米尔（Emil）需要将它们打包。

米勒位于流水线的起点（位置 $1$），而埃米尔位于流水线的终点（位置 $N$）。为了让工作更有趣，他们决定按照以下算法进行打包：

1. 米勒先开始：从他所在的一侧（起点）出发，打包剩余机器人中的每第二个。
2. 接着轮到埃米尔：从他所在的一侧（终点）出发，打包剩余机器人中的每第二个。
3. 循环往复：米勒再次从起点开始……然后是埃米尔，依此类推，直到打包完最后一个机器人。

你的任务是确定最后一个被打包的机器人在原始流水线上的位置。

输入格式

• 第一行包含一个整数 $N$ ($1 \le N \le 10^{16}$)，代表机器人的总数。

评分说明：

• 50% 的分数满足：$1 \le N \le 10,000$。
• 其余分数满足最大数据范围限制。

输出格式

• 输出一个整数，代表最后一个被打包机器人的原始位置编号。

限制条件

• 时间限制： 100 毫秒
• 内存限制： 64 MB

样例说明

输入：

10

输出：

9

过程解析：

• 初始状态：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• 米勒从左起（每第二个）： 打包 2, 4, 6, 8, 10。剩余：[1, 3, 5, 7, 9]
• 埃米尔从右起（每第二个）： 剩余列表倒序为 [9, 7, 5, 3, 1]，打包 7, 3。剩余：[1, 5, 9]
• 米勒从左起（每第二个）： 打包 5。剩余：[1, 9]
• 埃米尔从右起（每第二个）： 剩余列表倒序为 [9, 1]，打包 1。剩余：[9]
• 最后剩下的位置是 9。

在米勒完成第一次打包后（当米勒从左向右经过后）：

在埃米尔完成第一次打包后（当埃米尔从右向左经过后）：

在米勒完成第二次打包后（当米勒再次从左向右经过后）：

在埃米尔完成第二次打包后（当埃米尔再次从右向左经过后）：

最后剩下的是位于位置 9 的机器人。

版权信息

• 项目： Macedonian Programming Contests 2025
• 赛事： 社区与地区级竞赛 (Community and Regional competition)
• 版权方： ZIM (北马其顿计算机科学家协会)