Skip to content

11038: 【原1038】二哥的约瑟夫

题目

题目描述

author: 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1038

Description

话说二哥当年学习数据结构的时候遇到了那道猴子报数的题目,其实这就是经典的约瑟夫问题。

可是当年的二哥还是个毛头小子,只会用模拟的方法,而其他同学却使用了一些令二哥完全摸不到头脑的方法。

……二哥一怒之下改了题目……

话说当年花果山的猴子要选大王,选举办法如下:

所有猴子按1-M编号围坐一圈,二哥站在圈中心,由二哥指定一个整数Kn,

之后猴子们从1号开始按顺序报数,报到Kn的猴子退出到圈外,二哥再报出一个整数Kn+1,

然后由刚刚退出的猴子的下一只猴子再开始报数,如此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王。

由于二哥希望通过此种方法控制花果山,所以现在二哥把他制定的整数序列告诉你,希望你帮他预先算出那只猴子会成为大王。

Input Format

第一行 一个整数M,表示一共有M只猴子

第二行到第M行,每行一个整数 表示二哥即将指定的M-1个整数。这些数都大于0。

Output Format

一个整数,表示最后剩下那只猴子的编号。

Hint

对于40%的数据,M<=1000, K<=1000

对于70%的数据,M<=10000, K<=10000

对于100%的数据,M<=10000, K<=100000000

Sample Input

5
1
2
3
4

Sample Output

4

FineArtz's solution

/* 二哥的约瑟夫 */
#include <iostream>
using namespace std;

int main(){
    int m, k[10005];
    cin >> m;
    for (int i = 1; i < m; ++i)
        cin >> k[i];
    int ans = 0;
    for (int i = 2; i <= m; ++i)
        ans = (ans + k[m - i + 1]) % i;
    cout << ++ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "vector"

using namespace std;

int main() {
    int M, data[20000];
    vector<int> monkeyList;
    cin >> M;
    for (int i = 0; i < M-1; i++)
        cin >> data[i];
    for (int i = 0; i < M; i++)
        monkeyList.push_back(i+1);

    for (int i = 0,current=0,len=M; i < M - 1; i++,len--) {
        int temp = (data[i]+current-1) % len;
        monkeyList.erase(monkeyList.begin()+temp);
        current = temp;
    }

    cout << monkeyList.back();

    return 0;
}

Neight99's solution

#include <iostream>

using namespace std;

int main() {
    int M, *Kn, n = 0;

    cin >> M;
    Kn = new int[M];

    Kn[0] = 0;
    for (int i = 1; i < M; i++) {
        cin >> Kn[i];
    }

    for (int i = 2; i < M + 1; i++) {
        n = (n + Kn[M - i + 1]) % i;
    }

    cout << n + 1 << endl;

    return 0;
}

WashSwang's solution

#include <iostream>
using namespace std;
int k[30000],t,f[30000];
int main() {
    cin>>t;
    f[1]=0;
    for (int i=0;i<t-1;++i) cin>>k[i];
    for (int i=2;i<=t;++i)
        f[i]=(f[i-1]+k[t-i])%i;
    cout<<f[t]+1;
}

yyong119's solution

#include <iostream>
using namespace std;
int K[10000]={0};
int main()
{
    int M;
    cin>>M;
    int ans = 0;

    for (int i = 1; i <= M-1; ++i){
        cin>>K[i];
    }

    for (int i = 2; i <= M; ++i)
    {
        ans = (ans+K[M-i+1]) % i;
    }    
    cout<<ans+1<<endl;
    return 0;
}