## 10940 - Throwing cards away II

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

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

### 10940 - Throwing cards away II

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
studying @ ntu csie

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Just evaluate the values upto 50. And you will get an easy sequence. If you still dont find it then I will tell you.
Last edited by Jan on Sun Oct 16, 2005 7:02 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
It's exactly the Josephus Problem. It's quite well known in the programing contest community.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan
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.
thanks jan

I found "+2 sequence"
sorry , I forgot to login
studying @ ntu csie

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

### 10940 - Throwing cards away II

got accepted
Last edited by asif_rahman0 on Sun Oct 23, 2005 9:58 pm, edited 1 time in total.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul
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.
Some Love Stories Live Forever ....

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
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
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
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
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

### Just solve

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..
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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Just solve

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..
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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Just solve

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.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

### hi

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