POJ 1012 Joseph

Joseph

Time Limit: 1000MS

Memory Limit: 10000K

Total Submissions: 53862

Accepted: 20551

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

Source

Central Europe 1995

题意:同样的约瑟夫问题,只是现在有K个好人,K个坏人,确定一个步长,是的在第一个好人被清除之前所有坏人都被清除干净。

题解:

1.坏人被清除掉的先后顺序无关紧要,知道下一个除掉的是好人还是坏人就行了。
2.由于好人一直都是k个,每除掉一个坏人,坏人数-1,所以队列的总数每次-1但是好人一直是前k个
3.下一个被清除的人在队列中的“相对”序号为 s = (s+m-1)%(n-i);

4.只要s>=k,那么下一个被除掉的就是坏人

5.接下来说说m的取值范围:我们考察一下只剩下k+1个人时候情况,即坏人还有一个未被处决,那么在这一轮中结束位置必定在最后一个坏人,那么开始位置在哪呢?这就需要找K+2个人的结束位置,然而K+2个人的结束位置必定是第K+2个人或者第K+1个人,这样就出现两种顺序情况:GGGG.....GGGXB 或  GGGG......GGGBX (X表示有K+2个人的那一轮退出的人)所以有K+1个人的那一轮的开始位置有两种可能即第一个位置或K+1的那个位置,限定m有两种可能:t(k+1) 或 t(k+1)+1; t>=1; 若遍历每一个m必定超时,避免超时则需要打表和限制m的范围。

下面给出AC代码:

 1 #include <cstdio>
 2 //#include <bits/stdc++.h>
 3 using namespace std;
 4 int a[14];
 5 int f(int k,int m)
 6 {
 7     int n,i,s;
 8     n=2*k;
 9     s=0;
10     for(i=0;i<k;i++)
11     {
12         s=(s+m-1)%(n-i);
13         if(s<k) return 0;
14     }
15     return 1;
16 }
17 int main()
18 {
19     int i,k,n;
20     for(k=1;k<=14;k++)
21     {
22         i=k+1;
23         while(1)
24         {
25             if(f(k,i))
26             {
27                 a[k]=i;
28                 break;
29             }
30             else if(f(k,i+1))
31             {
32                 a[k]=i+1;
33                 break;
34             }
35             i+=k+1;
36         }
37     }
38     while(scanf("%d",&n)&&n)
39     printf("%d\n",a[n]);
40     return 0;
41 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

    A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

    Angel_Kitty
  • Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力,B.优先队列,C.dp乱搞)

    A. Carrot Cakes time limit per test:1 second memory limit per test:256 megabytes...

    Angel_Kitty
  • AIM Tech Round 4 (Div. 2)(A,暴力,B,组合数,C,STL+排序)

    A. Diversity time limit per test:1 second memory limit per test:256 megabytes in...

    Angel_Kitty
  • POJ-2585-Window Pains

    Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

    某些人
  • 周练19.11.03/10

    它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。

    AngelNH
  • POJ-1276-Cash Machine(多重背包)

    Cash Machine Time Limit: 1000MS Memory Limit: 10000K Total Submissions:...

    ShenduCC
  • CodeForces 157A Game Outcome

    A. Game Outcome time limit per test 2 seconds memory limit per test 256 me...

    ShenduCC
  • hdu---(1800)Flying to the Mars(trie树)

    Flying to the Mars Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768...

    Gxjun
  • Codeforces Round #410 (Div. 2)(A,字符串,水坑,B,暴力枚举,C,思维题,D,区间贪心)

    A. Mike and palindrome time limit per test:2 seconds memory limit per test:256 m...

    Angel_Kitty
  • Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力,B.优先队列,C.dp乱搞)

    A. Carrot Cakes time limit per test:1 second memory limit per test:256 megabytes...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券