10774 - Repeated Josephus

Gaolious · 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.

Cho · 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 · 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 · Post by **Gaolious** » Fri Jun 10, 2005 6:43 pm

i'm late ^^;;

Thanks, i got AC,

temper_3243 · 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 · Post by **temper_3243** » Sat Jun 11, 2005 11:03 am

Please post more test cases.

temper_3243 · 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 · 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 · 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 · 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

temper_3243 · 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 · 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 · 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

Gaolious · 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 · 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.

OJ Board

10774 - Repeated Josephus

10774 - Repeated Josephus

I'm stupid ;;;

oh, Thanks for reply

Repeated Josephus 10744

test cases

hi..