题目描述:poj.org/problem?id=1012
经典Joseph 问题的加强版, 参见注释, 注释很详细.
#include <cstdio> /* 测试m是否满足要求 k: 有2k个人 m:每数到m就出局 */ bool test(int k, int m) { int i = 0, len = 2 * k; //len: 当前总人数 while(len > k) { i = (i + m - 1) % len; //每次出局人是出局前的len 个人中的第i 个, 下标从0 开始 if(i < k) return false; len--; //没出局一个,修改len } return true; } int main() { int k; int a[14] = {0}; //数组保存计算过的数据, 不保存的话会超时, //其实很无聊,就14个数据,还整这么大的数据量 while(scanf("%d", &k) && k) { if(!a[k]) { //如果a[k]为0 就进行测试 int t = k + 1; //测试从k+1开始,下于K+1的测试没必要 while(true) { if(test(k, t)) { a[k] = t; break; } else t++; if(t == 2 * k)//跳过不必要的测试 t += k + 1; } } printf("%d\n", a[k]); } return 0; }
还有"猥琐"点的做法,因为就 14个数据, 直接把数据存到数组中即可
#include <cstdio> int main() { int k,a[15]= {0, 2, 7, 5, 30, 169, 441, 1872, 7632, 1740, 93313, 459901, 1358657, 2504881, 14}; while(scanf("%d", &k), k) printf("%d\n", a[k]); return 0; }
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj pku 1981 Circle and Points 点与圆 位置关系
2011-05-26 11:29 1264题目描述: http://poj.org/problem?id ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1214题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1035题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 875题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 887题目描述: http://acm.hdu.edu.cn/sh ... -
hdoj 1207 汉诺塔II dp 动态规划
2011-05-15 21:22 1669题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2506 Tiling 递推
2011-05-15 11:18 912题目描述: http://poj.org/problem?i ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1799题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1086题目描述: http://poj.org/problem?i ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1135题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 807题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 718题目描述:http://www.poj.org/proble ... -
poj 1654 Area 多边形面积
2011-04-23 20:10 901题目描述:http://poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 670题目描述:http://poj.org/problem?id= ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 548题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 755题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 839题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1217题目描述:http://poj.org/problem?id= ...
相关推荐
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大poj1012题的代码,已经AC,请放心下载
POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析POJ 1012 约瑟夫问题的数学解法及分析
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码