(Josephus 问题) 有n个人围成一圈，依次标号0至n-1。从第0号开始，以此0，1，0，1……的顺序报数，报到1的人会离开，直至圈中只余下一个人。求最后留下的人的编号。

/*
(Josephus 问题) 有n个人围成一圈，依次标号0至n-1。从第0号开始，以此0，1，0，1……的顺序报数，
报到1的人会离开，直至圈中只余下一个人。求最后留下的人的编号。
输入格式:
n
输出格式:
最后留下的人的编号
假设输入的是 10
F[] 0 0 0 0 0 0 0 0 0 0

标记情况：
 0 1 0 1 0 1 0 1 0 1
 0 1 1 1 0 1 1 1 0 1
 1 1 1 1 0 1 1 1 1 1
*/
//整体就是遇到第一个0，就标记为1，然后计数器加1，然后p异或1，然后i加1，然后i循环，直到计数器等于n-1
//最后再遍历一遍数组，找到第一个0的下标，输出即可
#include<iostream>
using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main(){
    int n;
    cin >> n;
    int i=0,p=0,c=0;//C计数器，p标记 i下标
    while(c+1<n){
        if(F[i]==0){
            if(p){//如果p为1
                F[i]=1;//标记
                c++;//计数器加1
            }
            p^=1;//通过异或运算，使p在0和1之间切换
        }
        i=(i+1)%n; //通过i让下标循环
    }
    int ans=-1;
    for(i=0;i<n;i++)
        if(F[i]==0)
           ans=i;
    cout << ans << endl;
    return 0;
}

#include <iostream>
using namespace std;

const int MAXN = 1000000;
int F[MAXN];

int main() {
    int n;
    cin >> n; // 读取人数

    // 初始化变量
    int i = 0, p = 0, c = 0; // i: 当前下标, p: 当前报数, c: 已标记的人数

    // 遍历直到标记 n-1 个人
    while (c + 1 < n) {
        if (F[i] == 0) { // 如果当前位置为0（未标记）
            if (p == 1) { // 如果当前报数为1
                F[i] = 1; // 标记为1
                c++; // 增加已标记人数
            }
            p ^= 1; // 切换报数（0变1，1变0）
        }
        i = (i + 1) % n; // 下标循环
    }

    // 查找并输出最后剩下的人的编号
    int ans = -1;
    for (i = 0; i < n; i++) {
        if (F[i] == 0) {
            ans = i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}