CF 134 DIV1 B.Blackboard Fibonacci

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

果然是暴跌RATE啊。。。

B题当然时没搞出来，YY了通项。

决定用搜索来做，界定上下界优化，结果后期没有心思debug了。

题目是说：两个数，然后有两种操作，将两个数的和替换掉其中一个。依次下去，两种操作轮流，就是FIB数列的构造。给出操作次数N以及第 N项R，问能不能构造出这样的数列，而且要求错误次数最少。也就是相同操作相邻的数量。

对于这个序列，起点是知道的，但是每一步都有两种选择，所以不好确定。

但是反过来，如果给出最后两个数，序列是可以倒推出来的，而且是唯一的。

对于A,B（A>B）那么前一个必然是A-B,B，而且这一步的操作必然是将两者之和替换A-B。

所以做法便是枚举倒数第二项，然后倒推回来，是否刚好N项而且记录错误的次数即可。

有一个优化，便是如果GCD(I,R)，即倒数两项并非互质的话，最终总是推出两个数相等，而且大于1，这时候的前一步便是0，d,而且d>0，这是显然不可能的。

而对于A,B这个状态，转移到B,A%B需要的步数也是确定的A/B，错误次数便是A/B-1

枚举结束之后，就是根据保存的最优状态，再倒推一遍，0，1后一步是确定的1，1对于这一步，不管是T还是B操作，结果一样，但是要求错误次数最小，肯定会选择和第一步相反的B操作。

#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<sstream>
#include<cassert>
#define LL long long
#define eps 1e-7
#define inf 1<<30
using namespace std;
int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}
void calc(int a,int b,int &mis,int &step){
    if(b==1){mis+=a-1;step+=a;return;}
    step+=a/b;      //需要多少步
    mis+=a/b-1;     //错误次数为步数减1
    calc(b,a%b,mis,step);
}
void get_ope(int a,int b,string &s){
    //很显然，第一步是T，之后变成了1，1，这时候不管是T,还是B，效果是一样的
    //需要错误次数最小的话，肯定就选B了
    if(b==1){for(int i=1;i<a;i++) s+='B'; return;}
    get_ope(b,a%b,s);
    //大小改变之后，操作刚好相反
    char ch=s[s.size()-1]=='T'?'B':'T';
    for(int i=0;i<a/b;i++) s+=ch;
}
void slove(int n,int r){
    int mistake=inf;  //最优的错误次数
    int num;   //最优解时的倒数第二个数
    for(int i=r-1;i>=1;i--){
        if(gcd(i,r)==1){
            int mis=0;
            int step=0;
            calc(r,i,mis,step);
            if(step==n&&mis<mistake){num=i;mistake=mis;}
        }
    }
    if(mistake!=inf){
        cout<<mistake-1<<endl;
        string s="T";
        get_ope(r,num,s);
        cout<<s<<endl;
    }
    else
        cout<<"IMPOSSIBLE\n";
}
int main(){
    int n,r;
    while(cin>>n>>r)
        if(n==1&&r==1) cout<<"0\nT\n"<<endl;
        else slove(n,r);
    return 0;
}