SRM482 Div1 Medium(500) HanoiGoodAndBad

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;
}};