10940 - Throwing cards away II

[SRX]

my method is
if n ==6
then
1. 1 2 3 4 5 6
( n=6=even , so copy ar[1]..ar[3] to ar[0].., then n/=2 )
2. 2 4 6
( n==3==odd , so copy ar[end] to ar[0] , then copy ar[1]..a[3]....to ar[
1]... )
3 6 4
4 4

but it is too slow
can someone give me some hint , thanks

[Jan]

Just evaluate the values upto 50. And you will get an easy sequence. If you still dont find it then I will tell you.

[Cho]

It's exactly the Josephus Problem. It's quite well known in the programing contest community.

[SRX]

Just evaluate the values upto 50. And you will get a easy sequence. If you still dont find it then I will tell you.

thanks jan

I found "+2 sequence"

sorry , I forgot to login

[asif_rahman0]

got accepted

[Raj Ariyan]

HI asif_rahman0,
Did u noticed abt ur time complexity ? n ≤ 500000 and also there are 500000 lines of input. Actually the problem doesnt need array. Its a well known Josephus problem. So it will be helpful if u read those things. Hope it helps. Good Luck.

[asif_rahman0]

hi Raj_ariyan u r right. i also know that.
but i always try something different.ok

first time i was bit complex with my code...but after ur wrote i thought
another different way... & finaly i got accepted(0.56sec).
may be its too much but i think its creative:)

am i right ????

my algo is:

1) find power of 2^(0<i<20)that is smaller than the given number
2) then calculate power of 2^(i-1)
3) then minus this number from given value (eg. n=19 value=19-16=3
so 3*2=6 result is 6)

[Antonio Ocampo]

my algo is:

1) find power of 2^(0<i<20)that is smaller than the given number
2) then calculate power of 2^(i-1)
3) then minus this number from given value (eg. n=19 value=19-16=3
so 3*2=6 result is 6)

Hi, what happened when n-2^(i-1)=0??

Hope it helps

[Antonio Ocampo]

my algo is:

1) find power of 2^(0<i<20)that is smaller than the given number
2) then calculate power of 2^(i-1)
3) then minus this number from given value (eg. n=19 value=19-16=3
so 3*2=6 result is 6)

Hi, what happened when n-2^(i-1)=0??

Hope it helps

[asif_rahman0]

hi antonio,
look at my code segment ...ok:

for(i=0;i<20;i++){
v=pow(2.00,(double)i);
if(no<=v){
break;
}
}
double f=pow(2.00,(double)i-1.00);

hope it works:)...kemon!!!!!

[Tanu]

Hi solvers I've just solve this problem....
I found a sequence...
from starting at n=2
2,2,4,2,4,8,10,12,14,16,2,4,8,10,12,14,16,18,20,22,24,26,28,30,32,2,4,...........
And only exception if n=1..
answer=1...
It seems very interesting to me....
Why it works(accepted)....
would anyone make answer this through mathmatical prove...
I'm curiously waiting...
...Tanu

[Martin Macko]

Hi solvers I've just solve this problem....
I found a sequence...
from starting at n=2
2,2,4,2,4,8,10,12,14,16,2,4,8,10,12,14,16,18,20,22,24,26,28,30,32,2,4,...........
And only exception if n=1..
answer=1...

Actually it is: (1,)2,2,4,2,4,6,8,2,4,6,8,10,12,14,16,2,4,6,8,10,12,14,16,18,20,22,24,26,28,...

[Martin Macko]

It seems very interesting to me....
Why it works(accepted)....
would anyone make answer this through mathmatical prove...
I'm curiously waiting...
...Tanu

Maybe you can get it from these recurences:

Code: Select all

f(1)=1
f(2*k)=2*f(k)
f(2*k+1)=2*g(k)

g(1)=1
g(2*k)=2*g(k)-1
g(2*k+1)=2*f(k+1)-1

Where f(a) is the number of the last card after performing described algorithm starting with n cards. And g(a) is the number of the last card after a similar algorithm starting with n cards. In this similar algorithm you put the topmost card to the bottom of the deck and then throw away the card.

[mf]

In fact, you can do a little better:
f(1) = 1
f(2n) = 2 f(n)
f(2n+1) = 2 + 2(f(n) mod n)

[Tanu]

Oh the Martin Macko siquence is OK...
I also got it...
Thanks many to Martin Macko and mf for response...
Tanvir