10774 - Repeated Josephus

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

10774 - Repeated Josephus

Post by Gaolious » Fri Jun 10, 2005 4:49 pm

in Problem,
Example with n = 5:
After the first elimination round, the survivor is person 3.
Elimination round each steps,

1>

1 2 3 4 5
1 3 5
3a
the survivor is person 3. is right ??
and,

1 2 3
1 3
3
and stop.


2>
1 2 3 4 5 6 7 8 9 10 11 12 13
1 3 5 7 9 11 13
3 7 11
7

suvivor person, 7. is right ??

1 2 3 4 5 6 7
1 3 5 7
3 7
7
the suvivor is person 7. and stop.


What is Elimination Rules ?

in this case,
1 2 3 4 5
1 3 5 -> even persons are die
3 -> odd persons are die

in this case,
1 2 3 4 5 6 7 8 9 10 11 12 13
1 3 5 7 9 11 13 -> even persons are die
3 7 11 -> odd persons are die
7 -> odd persons are die


i don't know that the rules.

please show me, each steps of elimination round. ( detail T_T )

Thanks for advise.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Jun 10, 2005 6:39 pm

Your elimination for 13 is wrong. You should consider the 13 numbers being in a circular array and eliminate every second remaining number.

i.e. For 1 2 3 4 5 6 7 8 9 10 11 12 13,
the elimination sequence will be 2 4 6 8 10 12 1 5 9 13 7 3.
The survivor is 11.

Repeat with 1 2 3 4 5 6 7 8 9 10 11,
the elimination sequence will be 2 4 6 8 10 1 5 9 3 11.
The survivor is 7.

Repeat with 1 2 3 4 5 6 7,
the elimination sequence will be 2 4 6 1 5 3.
The survivor is 7.

After 2 rounds, the survivor 7 is repeated. So the output is 2 7.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

I'm stupid ;;;

Post by Gaolious » Fri Jun 10, 2005 6:42 pm

EX>
1 2 3 4 5


the number of between [ ] is die

1 [2] 3 [4] 5 [1] 3 [5] -> 3 survivor
let x = 3
and
1 [2] 3 [1] -> 3 survivor and stop ( x == y )


1 [2] 3 [4] 5 [6] 7 [8] 9 [10] 11 [12] 13 [1] 3 [5] 7 [9] 11 [13] 3 [7] 11 [3] -> 11 survivor ( x = 11 )

1 [2] 3 [4] 5 [6] 7 [8] 9 [10] 11 [1] 3 [5] 7 [9] 11 [3] 7 [11] -> 7 survivor ( y = 7 )

continue , ( x != y ), and new x is y(=7)

1 [2] 3 [4] 5 [6] 7 [1] 3 [5] 7 [3]-> 7 survivor ( x == y ) and stop



.... i'm too stupid...

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

oh, Thanks for reply

Post by Gaolious » Fri Jun 10, 2005 6:43 pm

i'm late ^^;;

Thanks, i got AC,

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sat Jun 11, 2005 10:56 am

Hi,
Below is my C++ code. I am computing the value and storing it in a map.
The value is 2^m + k = 2K+1 .
Now whe m[n]!=n i increment the length . Please tell me where i am wrong.

Code: Select all

#include<iostream>
#include<map>
#include<cstdio>

using namespace std;

map < int, int >m;
map < int, int >h;

inline int
myg (int r)
{
  if (m.count (r) == 0){
      int ans, tmp = 1;
      while (r >= tmp)
	{
	  tmp = tmp * 2;
	}
      tmp = tmp / 2;
      ans = r - tmp;
      ans = (2 * ans) + 1;
      m[r] = ans;
      return m[r];
    }
  else
    return m[r];
}

inline int
compute (int n)
{
  if (m.count (n) == 1 && m[n] == n)
    return n;
  else
    {
      m[n] = myg (n);
      return m[n];
    }
}

int
main ()
{
  int a,i, z,n,no;

	for(i=1;i<=35000;i++)
	z=compute(i); /* compute values for all i and store in a map . This is correct */

scanf("%d",&no);

for(i=1;i<=no;i++)
{
  scanf (" %d", &a);
	n=a;


	int len=0;

	while(m[n]!=n) /* The length part */
	{
		len++;
		n=m[n];
	}

  printf ("Case %d: %d %d\n",i, len, n);
}
  return 0;
}


temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sat Jun 11, 2005 11:03 am

Please post more test cases.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Repeated Josephus 10744

Post by temper_3243 » Sat Jun 11, 2005 11:09 am

Hi,
Below is my C++ code. I am computing the value and storing it in a map.
The value is 2^m + k = 2K+1 .
Now when m[n]!=n i increment the length . Please tell me where i am wrong. Give me test cases for which it fails.

Code: Select all


#include<iostream>
#include<map>
#include<cstdio>

using namespace std;

map < int, int >m;
map < int, int >h;

inline int
myg (int r)
{
  if (m.count (r) == 0){
      int ans, tmp = 1;
      while (r >= tmp)
   {
     tmp = tmp * 2;
   }
      tmp = tmp / 2;
      ans = r - tmp;
      ans = (2 * ans) + 1;
      m[r] = ans;
      return m[r];
    }
  else
    return m[r];
}

inline int
compute (int n)
{
  if (m.count (n) == 1 && m[n] == n)
    return n;
  else
    {
      m[n] = myg (n);
      return m[n];
    }
}

int
main ()
{
  int a,i, z,n,no;

   for(i=1;i<=35000;i++)
   z=compute(i); /* compute values for all i and store in a map . This is correct */

scanf("%d",&no);

for(i=1;i<=no;i++)
{
  scanf (" %d", &a);
   n=a;


   int len=0;

   while(m[n]!=n) /* The length part */
   {
      len++;
      n=m[n];
   }

  printf ("Case %d: %d %d\n",i, len, n);
}
  return 0;
} 

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

test cases

Post by Gaolious » Sat Jun 11, 2005 11:36 am

input
50
50
100
150
200
250
300
350
400
450
500
550
600
650
700
750
800
850
900
950
1000
1050
1100
1150
1200
1250
1300
1350
1400
1450
1500
1550
1600
1650
1700
1750
1800
1850
1900
1950
2000
2050
2100
2150
2200
2250
2300
2350
2400
2450
2500
output
Case 1: 3 7
Case 2: 3 7
Case 3: 4 15
Case 4: 3 7
Case 5: 6 63
Case 6: 4 15
Case 7: 6 63
Case 8: 3 7
Case 9: 4 15
Case 10: 6 63
Case 11: 4 15
Case 12: 4 15
Case 13: 4 15
Case 14: 6 63
Case 15: 7 127
Case 16: 3 7
Case 17: 5 31
Case 18: 4 15
Case 19: 7 127
Case 20: 6 63
Case 21: 4 15
Case 22: 4 15
Case 23: 7 127
Case 24: 4 15
Case 25: 5 31
Case 26: 4 15
Case 27: 5 31
Case 28: 6 63
Case 29: 6 63
Case 30: 7 127
Case 31: 5 31
Case 32: 3 7
Case 33: 6 63
Case 34: 5 31
Case 35: 7 127
Case 36: 4 15
Case 37: 7 127
Case 38: 7 127
Case 39: 8 255
Case 40: 6 63
Case 41: 2 3
Case 42: 4 15
Case 43: 5 31
Case 44: 4 15
Case 45: 5 31
Case 46: 7 127
Case 47: 6 63
Case 48: 4 15
Case 49: 5 31
Case 50: 5 31

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Jun 12, 2005 6:44 am

I am getting exactly the same output that you gave for the input given. You can compile my code and see.

Well please post output for n=
1,2,3,4,5,7,8,9,15,16,17,30,31,32,33,34,
60,61,62,63,64,65,66,67,100,256,512

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Jun 12, 2005 12:03 pm

Input:
27
1
2
3
4
5
7
8
9
15
16
17
30
31
32
33
34
60
61
62
63
64
65
66
67
100
256
512
Output:
Case 1: 0 1
Case 2: 1 1
Case 3: 0 3
Case 4: 1 1
Case 5: 1 3
Case 6: 0 7
Case 7: 1 1
Case 8: 1 3
Case 9: 0 15
Case 10: 1 1
Case 11: 1 3
Case 12: 4 15
Case 13: 0 31
Case 14: 1 1
Case 15: 1 3
Case 16: 2 3
Case 17: 4 15
Case 18: 4 31
Case 19: 5 31
Case 20: 0 63
Case 21: 1 1
Case 22: 1 3
Case 23: 2 3
Case 24: 1 7
Case 25: 3 7
Case 26: 1 1
Case 27: 1 1
I'm always willing to help, if you do the same.

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Jun 12, 2005 1:46 pm

Thanks ryan,Gaolious and others. But i am getting the same answers that you having. My code is above.
Can someone please take the pains to post the output for n=1 to 31000. Please gzip and send it to temper_3243@yahoo.com

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Jun 12, 2005 5:00 pm

Can someone tell me where this code gives wrong answer ? I am unable to determine . i tried with all the given inputs and inputs by others.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sun Jun 12, 2005 9:48 pm

Just to give you some inputs of larger cases:

Input:
11
5000
10000
15000
20000
25000
29995
29996
29997
29998
29999
30000
Output:
Case 1: 5 31
Case 2: 5 31
Case 3: 7 127
Case 4: 5 31
Case 5: 6 63
Case 6: 7 511
Case 7: 8 255
Case 8: 8 511
Case 9: 9 511
Case 10: 6 1023
Case 11: 7 127
I'm always willing to help, if you do the same.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

hi..

Post by Gaolious » Mon Jun 13, 2005 3:48 pm

if you not solved this problem, then how about visit to follow page url.

http://isd.korea.ac.kr/~ajava/10774.php?n=23403

it programming by php script languagae....

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Tue Jun 14, 2005 5:01 am

Well the code you posted and ryan posted differs in output. My code produces the output exactly that ryan gave.

Btw galious, how is input for 3 a length of 1 . For n=3 my output is 0 3. For n=1 my output is 0 1. Your output is 1 1.

In problem it is stated that after the elimination round.For n=2 it is 1 1.

Post Reply

Return to “Volume 107 (10700-10799)”