首页 > 代码库 > ACdream1020:The Game about KILL
ACdream1020:The Game about KILL
Problem Description
Teacher HU and his 40 students were trapped by the brigands. To show their power, the head of the brigands want to select one people to kill.
Teacher HU and his 40 students will stand in a circle, and every second person would leave, and the last people in the circle would be killed. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 will be killed. To make his students alive, teacher HU calculated the position to be the last man standing, and sacrifice himself.
Now we consider a more common condition, if teacher HU has N - 1 students, which place should he stand to be the last person.
Teacher HU and his 40 students will stand in a circle, and every second person would leave, and the last people in the circle would be killed. For example, if there are 5 persons in the circle, counting proceeds as 2, 4, 1, 5 and person 3 will be killed. To make his students alive, teacher HU calculated the position to be the last man standing, and sacrifice himself.
Now we consider a more common condition, if teacher HU has N - 1 students, which place should he stand to be the last person.
Input
There are multiple test cases.
Each test case only contains an integer N. (1 <= N <= 1,000,000,000)
Each test case only contains an integer N. (1 <= N <= 1,000,000,000)
Output
For each test case, output an integer indicating which place should teacher HU stand.
Sample Input
2 3
Sample Output
1 3
约瑟夫环,n太大,首先可以想到打表找看有没有规律
可以发现时有规律的
可以看到,只要是2的i次幂,那么存活的是1,后面的依次加2
例如4为1,5就是3,6->5,7->7,8->1
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define ll long long ll f[50],n; int main() { int i; f[0] = 1; for(i = 1; i<31; i++) f[i] = f[i-1]*2; while(~scanf("%lld",&n)) { for(i = 1; i<31; i++) { if(n<f[i]) break; } printf("%lld\n",1+2*(n-f[i-1])); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。