首页 > 试题广场 >

幸存者游戏

[编程题]幸存者游戏

热度指数：170 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

有n个同学围成一圈，其id依次为1，2，3...n（n号挨着1号）。现在从1号开始报数，第一回合报到m的人就出局，第二回合从出局的下一个开始报数，报到m^2的同学出局。
以此类推直到最后一个回合报到m^(n-1)的人出局，直到剩下最后一个同学。输出这个同学的编号。n<=15,m<=5

输入描述:

每一行第一个数字代表n，第二个数字代表m

输出描述:

输出最后剩下同学的编号

示例1

输入

5 2

输出

算法知识视频讲解

牛客2816108号

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
       if (n<1 || m<1) return -1;
    int circle=pow(m,n-1);
    int f=0;
    for(int i=2;i<=n;++i)
    {
        f=(f+circle)%i;
        circle/=m; // 调整为当前的 m，因为 m 有做关于 n 的次方
    }
    cout<<f+1<<endl;
    return 0;
}

发表于 2019-06-16 10:19:11 回复(0)

地沟油

n, m = [int(x) for x in input().split()]
ans = 1
for i in range(2, n+1):
    ans = (ans + m**(n-i+1)) % i
    if ans == 0:
        ans = i
print(ans)

编辑于 2019-09-11 00:03:39 回复(0)

neekity

用PHP语言的array_values()函数

<?php
fscanf(STDIN, "%d %d", $n, $m);
$num=array();
$num[0]=0;
for ($i=1;$i<=$n;++$i) $num[$i]=$i;
$i--;
$j=1;
$pre=0;
while ($i>1){
    $j*=$m;
    $outid***re)%$i;
    if ($outidx==0) $outidx=$i;
    $pre=$outidx-1;
    //echo $num[$outidx]."\n";
    unset($num[$outidx]);
    $num=array_values($num);
    //var_dump($num);
    $i--;
}
echo $num[1];
?>

发表于 2019-05-21 17:35:34 回复(0)