d030, d068 雙、三色河內塔

//GJ d068
#include<iostream>
#include<stack>
using namespace std;
int p[100]={0}; //ring  i's position is p[i]
deque<int> d[3]; //three sticks 
int t=0;

void han(int n, int st,int ed, int mi) {	//move n amount of rings from st to ed
	if( n == 1 ) {
		cout<<"ring "<<d[st].front()<<" : "<<char('A'+st)<<" => "<<char('A'+ ed)<<endl;
		t++;
		p[d[st].front()]=ed;
		d[ed].push_front(d[st].front());
		d[st].pop_front();
	} else {
		han(n-1, st, mi, ed);
		han(1, st, ed, mi);
		han(n-1, mi, ed, st);
	}
}

int main() {
	int n;
	cin>>n;
	for(int i=n;i>=1;i--) d[0].push_front(i),p[i]=0;
	for(int i=n;i>=1;i--) {
		int gl=(i-1)%3; //雙色用gl=(i+1)%2+1 
		if(p[i]!=gl) {
			if(d[p[i]].size()>1) han(d[p[i]].size()-1, p[i], 3-p[i]-gl, gl);
			han(1, p[i], gl, 3-p[i]-gl);
		}
		d[p[i]].pop_back();	//remove the ring that we dont use any more 
	}
	cout<<"共需"<<t<<"個移動\n";
	return 0;
}