SRM482 Div1 Medium(500) HanoiGoodAndBad
問題文中のアルゴリズムを実装し、1手動かすごとに各円盤がどの棒にあるかを出力するようにして、法則を探した。
#include <vector> using namespace std; class HanoiGoodAndBad{public: int moves( int N, int Dave ) { vector<int> disk( N ); int d[2][6] = { { 0, 1, 1, 2, 2, 0 }, { 0, 2, 2, 1, 1, 0 } }; for ( int i=0; i<N; i++ ) { disk[i] = d[(N-i)%2][Dave%6]; Dave /= 2; } int t = 0; int ans = 0; for ( int i=N-1; i>=0; i-- ) ans = ans*3 + ( t%2==0 ? disk[i] : 2-disk[i] ), t += disk[i]; return ans; }};