ZOJ 2072 K-Recursive Survival
2024-09-24 17:08:31
https://vjudge.net/contest/67836#problem/K
n people numbered 1 to n around a circle, we eliminate every second remaining person until only one survives. Define a function J(n), represents the survivor's original number in the circle. For example, J(2)=1, J(10)=5. Now, please calculate this nested function: J(J(J(..J(n)..)))
Input
There are multiple test cases, each with two positive numbers in one line.
The first number represents the number of the people in original cirlcle, the second one represents the times of the function nested.
All the numbers in input file will be less than 2^63-1.
Output
output the result in one line per test case.
Sample Input
2 1
10 1
10 2
Smaple Output
1
5
3
时间复杂度:$O(M * log(N))$
题解:约瑟夫环, 递归
代码:
#include <bits/stdc++.h>
using namespace std; long long J(long long n) {
if(n == 0 || n == 1)
return 1;
else if(n % 2 == 0)
return 2 * J(n / 2) - 1;
else
return 2 * J(n / 2) + 1;
} int main() {
long long N, M;
while(~scanf("%lld%lld", &N, &M)) {
for(long long i = 0; i < M; i ++) {
long long c;
c = J(N);
if(c == N) break;
N = c;
}
printf("%lld\n", N);
}
return 0;
}
最新文章
- Python快速教程目录(转)
- Python学习笔记——文件写入和读取
- poj3660 floyd
- Python基本数据结构-集合-创建/与其他类型比较
- 20145215《Java程序设计》第2周学习总结
- Xcode好用的插件
- memcpy
- smarty缓存函数
- Sublime Text—自带快捷键介绍
- 网站开发常用jQuery插件总结(一)提示插件alertify
- zabbix server is not running: the information displayed may not be current
- iOS-Core Text 入门
- 【Android进阶】获取Android软件的版本信息
- MYSQL数据库导入大数据量sql文件失败的解决方案
- hdu 1255 覆盖的面积(求覆盖至少两次以上的面积)
- Unity C# 自定义TCP传输协议以及封包拆包、解决粘包问题
- Spark源码剖析 - 计算引擎
- background-position,有逗号和没逗号:截然不同的结果
- Flask最强攻略 - 跟DragonFire学Flask - 第三篇 Flask 中的 request 之 先知道有这么个东西
- nginx:在linux上进行nginx的安装