题目描述
N只猴子选大王。选举办法如下:从头到尾1、2、3报数,凡报3的退出,余下的从尾到头1、2、3报数,凡报3退出;余下的又从头到尾报数,还是报3的退出;依此类推,当剩下的两只猴子时,取这时报数报1的为王。若想当猴王,请问当初应占据什么位置?
输入
猴子总数N,N<1000。
输出
猴王所在的位置。
样例输入
10
样例输出
8
提示
【样例分析】:十只猴子1-10编号,则出圈的次序为
猴子编号:1 2 3 4 5 6 7 8 9 10
出圈次序:3 6 9 7 2 5 4 10 剩下8和1时,8号猴子报1为大王
别忘点赞哦
#include <iostream>
#include <cmath>
using
namespace
std;
#define N 10005
bool
a[N];
int
main() {
int
n, len, s;
cin >> n, len = n;
while
(len >= 2) {
s = 0;
for
(
int
i = 1; i <= n; i++) {
if
(a[i] ==
false
) {
s++;
//队伍中的monkey报数
}
if
(s == 3) {
a[i] =
true
;
s = 0;
len--;
}
}
s = 0;
for
(
int
i = n; i >= 1; i--) {
if
(a[i] ==
false
) {
s++;
//队伍中的monkey报数
}
if
(len == 2 && s == 1) {
cout << i << endl;
return
0;
}
if
(s == 3) {
a[i] =
true
;
s = 0;
len--;
}
}
}
return
0;
}