poj-1012-约瑟夫问题

简介: Description The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, .

Description

The Joseph's problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved.

Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy.

Input

The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14.

Output

The output file will consist of separate lines containing m corresponding to k in the input file.

Sample Input

3
4
0

Sample Output

5
30
题目大意:
有k个好人和k个坏人,从第一个人开始循环报数(即报到m后从1开始报),报到m的人被处死,要求全部的坏人都处死,好人留下,求出m。
这个代码就是有点慢,所以我打了个表


#include<iostream> using namespace std; int main() { int k; while(cin>>k) { if(!k) break; int m=1; int ans[30]={0}; for(int i=1;i<=k;i++) { ans[i]=(ans[i-1]+m-1)%(2*k-i+1); if(ans[i]<k) { i=0;m++; } } cout<<m<<endl; } return 0; } } sort(yes,yes+n,cmp); sort(no,no+n,cmp); cout<<yes[n-1]<<" "<<no[n-1]<<endl; return 0; }

  

#include<stdio.h>
int main()
{
	int k;
	int Joseph[14]={0,2,7,5,30,169,441,1872,7632,1740,93313,459901,1358657,2504881};
	while(scanf("%d",&k),k)
		printf("%d\n",Joseph[k]);
	return 0;
}

  

相关文章
|
人工智能 算法 Java
AI:互联网程序设计竞赛之蓝桥杯大赛的简介、奖项设置、大赛内容以及蓝桥杯与ACM(ICPC)的四个维度对比之详细攻略
AI:互联网程序设计竞赛之蓝桥杯大赛的简介、奖项设置、大赛内容以及蓝桥杯与ACM(ICPC)的四个维度对比之详细攻略
AI:互联网程序设计竞赛之蓝桥杯大赛的简介、奖项设置、大赛内容以及蓝桥杯与ACM(ICPC)的四个维度对比之详细攻略
|
12月前
|
安全 数据挖掘 API
快手小店详情API接口的获取与应用
在数字化时代,电商平台竞争激烈,API接口作为连接不同系统和服务的桥梁,已成为电商生态中不可或缺的一部分。本文详细介绍快手小店详情API接口的获取与应用,帮助开发者和企业提升业务效率和用户体验。涵盖API接口定义、主要应用场景、注册与认证流程、调用方法及实际应用案例,提供最佳实践建议。
428 1
|
12月前
|
关系型数据库 MySQL 数据库
mysql关系型数据库的学习
mysql关系型数据库的学习
130 0
|
数据挖掘
SPSS平均值检验
SPSS平均值检验
273 0
|
安全 Shell 网络安全
vulnhub|渗透测试tomato
vulnhub|渗透测试tomato
|
机器学习/深度学习 编解码 人工智能
优酷发布最大工业级超高清视频数据集,超分辨率算法大赛落幕
在这场算法挑战赛上,不仅有刚刚出现在 CVPR 2019 的最新算法,还出现了年仅 18 岁的获奖选手。
1069 0
优酷发布最大工业级超高清视频数据集,超分辨率算法大赛落幕
|
移动开发 人工智能 算法
生成n个数的全排列【递归、回溯】
下面讨论的是n个互不相同的数形成的不同排列的个数。毕竟,假如n个数当中有相同的数,那n!种排列当中肯定会有一些排列是重复的,这样就是一个不一样的问题了。/*===================================== 数的全排列问题。
1185 0
poj 1948 Triangular Pastures(二维0/1背包)
点击打开链接poj 1948 思路: 二维0/1背包 分析: 1 题目要求从n个木棒里面选出m个组成一个三角形,使得三角形的面积最大 2 对于三角形来说知道了两条边和周长就可以求面积,按照0/1背包的思想dp[i][j][k]表示前i个木棒能否组成第一条边为长度j,第二条长度为k。
928 0