Page 1 of 2

10940 - Throwing cards away II

Posted: Sun Oct 16, 2005 6:18 am
by 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

Posted: Sun Oct 16, 2005 6:37 am
by 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. :D

Posted: Sun Oct 16, 2005 6:40 am
by Cho
It's exactly the Josephus Problem. It's quite well known in the programing contest community.

Posted: Sun Oct 16, 2005 7:02 am
by SRX
Anonymous wrote:
Jan wrote:Just evaluate the values upto 50. And you will get a easy sequence. If you still dont find it then I will tell you. :D
thanks jan :D

I found "+2 sequence"
sorry , I forgot to login

10940 - Throwing cards away II

Posted: Sun Oct 23, 2005 7:28 pm
by asif_rahman0
got accepted

Posted: Sun Oct 23, 2005 9:15 pm
by 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.

Posted: Sun Oct 23, 2005 10:14 pm
by 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)

Posted: Sun Oct 23, 2005 10:16 pm
by Antonio Ocampo
asif_rahman0 wrote: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

Posted: Sun Oct 23, 2005 10:18 pm
by Antonio Ocampo
asif_rahman0 wrote: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

Posted: Mon Oct 24, 2005 12:55 am
by 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!!!!!

Just solve

Posted: Sun Nov 27, 2005 2:13 pm
by 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

Re: Just solve

Posted: Sat Dec 10, 2005 8:56 pm
by Martin Macko
Tanu wrote: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,...

Re: Just solve

Posted: Sat Dec 10, 2005 8:57 pm
by Martin Macko
Tanu wrote: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.

Posted: Sun Dec 11, 2005 1:05 pm
by 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)

hi

Posted: Mon Dec 12, 2005 6:48 am
by Tanu
Oh the Martin Macko siquence is OK...
I also got it...
Thanks many to Martin Macko and mf for response...
Tanvir