SRM486 Div1 Easy(300) OneRegister - kusano

+はレジスタを2倍にする演算子、-はレジスタを0に、*はレジスタを2乗、/はレジスタを1に。-は使わないし、/を使うのは最初のみ。後は+と*を全探索すれば最低でも2倍になるのですぐにtの値を超えるはず。

#include <string>

using namespace std;

string proper( string a, string b )
{
    if ( a.length() < b.length() )  return a;
    if ( a.length() > b.length() )  return b;
    return min( a, b );
}

string BT( long long s, long long t )
{
    if ( s > t )   return string(100,'~');
    if ( s == t )  return "";
    if ( s == 1 )  return "+"+BT(s+s,t);
    return proper( "+"+BT(s+s,t), "*"+BT(s*s,t) );
}

class OneRegister{public:
string getProgram( int s, int t )
{
    string ans = proper( BT(s,t), "/"+BT(1,t) );
    return ans.length()<100 ? ans : ":-(";
}};