CodeForces Round #134(217B) - Blackboard Fibonacci

本題的關鍵是抓住在過程中T,B兩數的關系...如果當前的操作是'T'...那麼T=T+B..顯然T>B..如果當前操作是'B'...做的操作是B=T+B..顯然B>T...所以要是知道了最後的(T,B)..那麼就可以倒推出唯一的序列...只要判斷下T,B的大小..就知道當前是要寫'T',還是'B'了..
    枚舉最後的(T,B)...倒推..找出最優解...

Program：
[cpp]
#include<iostream> 
#include<stdio.h> 
#include<algorithm> 
#include<string.h> 
#include<math.h> 
#include<queue> 
#include<stack> 
#define ll long long 
#define oo 1000000000 
#define pi acos(-1) 
using namespace std;   
int n,m,i,l,r,ansn; 
char ans[1000006],temp[1000006]; 
void update(int t,int b) 
{  
     int len=1,i,k; 
     while (t!=b && t>=0 && b>=0) 
       if (t>b)  
       { 
             temp[len++]='T'; 
             t-=b; 
       }else 
       { 
             temp[len++]='B'; 
             b-=t; 
       } 
     if (len!=n || t!=1) return; 
     temp[len]='T'; 
     k=0; 
     for (i=1;i<len;i++) 
        if (temp[i]==temp[i+1]) k++; 
     if (k<ansn) 
     { 
            ansn=k; 
            for (i=0;i<len;i++) 
               ans[i]=temp[len-i]; 
            ans[len]='\0'; 
     } 
     return; 
} 
int main() 
{  
     while (~scanf("%d%d",&n,&m)) 
     { 
           int i; 
           ansn=oo; 
           for (i=1;i<=m;i++) 
           { 
                 update(i,m); 
                 update(m,i); 
           } 
           if (ansn==oo) printf("IMPOSSIBLE\n"); 
           else printf("%d\n%s",ansn,ans);  
     } 
     return 0; 
}