我觉得你上面的思路有错啊,p位置的牌经过k次洗牌后回到p位置,不能证明所有的牌都回到了原来的位置。
Yes, that is true. You need to prove it --- a math problem.
Thus for this problem, you only need to consider the nuber 1 --- see how it goes.
My submitted C code. I think it should be ranked #1 there.
=================================
main()
{
int n, a, c;
while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;
while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}
printf("%d\n", c);
}
}
My accepted C++ code --- completely simulates the shuffling process.
=================================================
#include <iostream>
using namespace std;
int a[200001], b[200001];
void shuffle(int*a, int *b, int n)
{
int i, i2;
for(i=1; i<=n; ++i)
{
i2=(i<<1);
b[i2] = a[i];
b[i2-1] = a[n+i];
}
}
int count(int n)
{
int i, c=0, n2=(n<<1);
bool bOrig = false;
for(i=1; i<=n2; ++i)
a[i] = i;
while(!bOrig)
{
shuffle(a, b, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(b[i] != i)
{
bOrig = false;
break;
}
}
if(bOrig)
break;
shuffle(b, a, n);
++c;
bOrig = true;
for(i=1; i<=n2; ++i)
{
if(a[i] != i)
{
bOrig = false;
break;
}
}
}
return c;
}
int main()
{
int n;
while(cin>>n)
cout<<count(n)<<endl;
return 0;
}
My submitted C code. I think it should be ranked #1 there.
=================================
main()
{
int n, a, c;
while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;
while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}
printf("%d\n", c);
}
}
NICE...
My submitted C code. I think it should be ranked #1 there.
=================================
main()
{
int n, a, c;
while(scanf("%d", &n)!=-1)
{
a = 2;
c = 1;
while(a!=1)
{
if(a<=n)
a<<=1;
else
a=2*(a-n)-1;
++c;
}
printf("%d\n", c);
}
}