View Code of Problem 1006

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>

using namespace std;

int n,m;
int f[70][70]={{0}};
int father[70][70]={{0}};

int num[70]={0};
int hanoi[70][70]={{0}};


void prt(int s,int t,int a,int b)
{
	if(a==1)
	{
         printf("move %d from %d to %d ",hanoi[s][num[s]],s,t);
         if(num[t]!=0) printf("atop %d",hanoi[t][num[t]]);
         puts("");
         hanoi[t][++num[t]]=hanoi[s][num[s]--];
         return;
     }
     for(int i=1;i<=m;i++)
	 if(i!=s && i!=t)
	 {
         if(hanoi[i][num[i]]>hanoi[s][num[s]-father[a][b]+1])
		 {
             prt(s,i,father[a][b],b);
             prt(s,t,a-father[a][b],b-1);
             prt(i,t,father[a][b],b);
             return;
         }
     }
	return;
}

int main()
{
	cin>>n>>m;
	for(int i=0;i<70;i++)
		for(int j=0;j<70;j++)
			f[i][j]=7e8;
	for(register int i=1;i<=m;i++)
		f[1][i]=1;
	for(register int i=2;i<=n;i++)
		for(register int j=3;j<=m;j++)
		{
			for(register int p=1;p<i;p++)
			{
				int tmp=(f[p][j]<<1)+f[i-p][j-1];
				if(f[i][j]>tmp)
				{
					f[i][j]=tmp;
					father[i][j]=p;
				}
			}
		}
	cout<<f[n][m]<<endl;
	for(int i=n;i>=1;i--)
		hanoi[1][++num[1]]=i;
	for(int i=1;i<=m;i++)
		hanoi[i][0]=7e8;
	prt(1,m,n,m);
	return 0;
}