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.

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.

thanks jan

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