CF 134 DIV1 B.Blackboard Fibonacci

転載は出典を明記してください、ありがとうございます http://blog.csdn.net/ACM_cxlove?viewmode=contents           by---cxlove
やっぱり暴落RATEですね...
B問題はもちろんできなかったが,YYはパスした.
検索で行い,上下境界最適化を定義することにしたが,後期はdebugに気を取らなかった.
2つの数、それから2つの操作があって、2つの数の和をその中の1つに置き換えます.順番に下りていくと、2つの操作が交代してFIB数列の構造になります.操作回数NおよびN番目のRを与え,このような数列を構築できるかどうかを尋ね,エラー回数を最小限に抑える.つまり、同じ操作で隣接する数です.
このシーケンスについては、起点は知っていますが、ステップごとに2つの選択があるので、確定しにくいです.
しかし逆に,最後の2つの数を与えると,シーケンスは逆に押し出すことができ,唯一である.
Aに対して、B(A>B)では、前は必ずA−B、Bであり、このステップの動作は必ず両者の和をA−Bに置き換える.
だから、最後から2番目の項目を列挙して、逆さまに押して、ちょうどN項目かどうか、そして間違った回数を記録すればいいのです.
1つの最適化は,GCD(I,R),すなわち逆数の2つが互いに質を持たない場合,最終的には常に2つの数が等しく,1より大きく,このときの前のステップは0,d,d>0であり,これは明らかに不可能である.
一方,A,Bという状態では,Bに移行し,A%Bに必要なステップ数も決定されたA/Bであり,エラー回数はA/B-1である.
列挙が終了すると、保存された最適状態に基づいて、もう一度逆算し、0、1の後のステップが確定した1、1このステップについては、TでもBでも結果は同じですが、エラー回数が最小であることが要求され、第1のステップとは逆の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
";
}
int main(){
    int n,r;
    while(cin>>n>>r)
        if(n==1&&r==1) cout<<"0
T
"<<endl;
        else slove(n,r);
    return 0;
}