打卡信奥刷题（114）用C++工具信奥P1145[普及组/提高] 约瑟夫

约瑟夫

题目描述

n n n 个人站成一圈，从某个人开始数数，每次数到 m m m 的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人， k k k 个好人站在一起， k k k 个坏人站在一起。从第一个好人开始数数。你要确定一个最小的 m m m，使得在第一个好人被杀死前， k k k 个坏人先被杀死。

输入格式

一行一个整数 k k k。

输出格式

一行一个整数 m m m。

样例 #1

样例输入 #1

3

样例输出 #1

5

样例 #2

样例输入 #2

4

样例输出 #2

30

提示

0 < k < 14 0\lt k\lt 14 0<k<14。

C++实现

#include
#include
#include <bits/stdc++.h>

using namespace std;

int i,k,m,begin;
int check(int remain)
{
int result=(begin+m-1)%remain;
if(result>=k){
begin=result;
return 1;
}
else{return 0;}
}
int main(){
scanf("%ld",&k);
m=k;
int find =0;
while(find==0)
{
find=1;begin=0;
for(i=0;i<k;i++)
{
if(!check(2*k-i))
{
find=0;break;
}
}
m++;
}
printf("%d",m-1);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP C++考级编程题实现、白名单赛事考题实现，感兴趣的请关注，我后续将继续分享相关内容