POJ 1920 Towers of Hanoi

OJ題目：click here~~

題目分析：三根柱子 ， n個圓盤 。給一個漢諾塔的狀態，求將所有盤挪到一個柱子上的最少步數，並給出是最後在哪個柱子上。

從給定狀態到目標狀態很復雜，但是從目標狀態到給定的狀態就很容易想了。將一個柱子上i個盤，挪到另一個柱子上，需要pow（2，i） - 1步。 顯然，最後在的那個柱子，一定是所給狀態下最大盤所在的柱子。接下來考慮第二大的盤，需要移動就移動。……詳見代碼注釋。

AC_CODE

const int mod = 1000000;
int p[100002] , s[100002];
int   main(){
      int n  , i , j , k  ,a , x[4] ;
      s[0] = 1;
      for(i = 1;i <= 100000;i++)
         s[i] = 2*s[i - 1] , s[i] %= mod;
      while(cin >> n){
          scanf("%d%d%d",&x[1],&x[2],&x[3]);
          for(i = 1;i <= 3;i++)
          for(j = 0;j < x[i];j++){//記錄所給狀態每個盤在哪個柱子
            scanf("%d",&a);
            p[a] = i;
          }
          int now = p[n];
          int need = p[n - 1];
          int ans = 0;
          for(i = n - 1;i > 0;i-- , need = p[i]){
            if(need != now){//此刻的狀態與需要的狀態不一樣，則需要移動
                ans += s[i - 1];//ans += (s[i - 1] - 1 + 1)
                ans %= mod;
                now = 6 - need - now;//盤i以上的所0有盤，先要挪到除這兩個以外的第三個柱子上。
            }
          }
          cout << p[n] << endl << ans << endl;//最後所在的柱子，一定是最大盤在的柱子
      }
      return 0 ;
}