B Hanoi tower
It has become a good tradition to solve the “Hanoi tower” puzzle at programming contests in Rybinsk. We will review the rules briefly.
2*n/3-1移到C上，再从A移动一个到B上
再把C的n/3-1移到B上，现在所有上面都是1/3了
队友得到了一个神奇的公式2^(n-n/3-1)+2^(n/3-1)-1
但是经过提交是不行的，所以暴力打表找规律
#include <stdio.h>
using namespace std;
int num[],f,f1;
int move(int n,int a,int b)
{
//printf("Move disk %d from %c to %c\n",n,a,b);
num[a]--,num[b]++;
if(num[]==num[]&&num[]==num[])return ;
return ;
}
void hanoi(int n,int a,int b,int c)
{
if(f1)return;
if(n==)
{
if(move(n,a,c))
{
printf("%d\n",f);
f1=;
return;
}
}
else
{
hanoi(n-,a,c,b);
f++;
if(move(n,a,c))
{
printf("%d\n",f);
f1=;
return;
}
hanoi(n-,b,a,c);
}
}
int main()
{
int n;
for(int n=; n<=; n+=)
{
num[]=n,num[]=num[]=f=,f1=;
hanoi(n,,,);
}
return ;
}
很快就会发现偶数的猜想是对的，所以对奇数进行讨论，发现正好是*4+2
暴力代码，交的表，因为莫名RE
import java.math.*;
import java.util.*;
public class Main
{
public static void main(String args[])
{
Scanner cin=new Scanner(System.in);
BigInteger tmp=BigInteger.ZERO;
for(int n=3; n<=300; n+=3)
{
if(n/3%2==1)
{
System.out.println("\""+tmp.multiply(BigInteger.valueOf(4))
.add(BigInteger.valueOf(2))+"\",");
}
else
{
int x=n-n/3-1;
int y=n/3-1;
tmp=cal(x).add(cal(y)).subtract(BigInteger.ONE);
System.out.println("\""+tmp+"\",");
}
}
}
static BigInteger cal(int x)
{
BigInteger ans=BigInteger.ONE;
ans=ans.shiftLeft(x);
return ans;
}
}