問題概要
Alice は,2 つの正整数 からなる数式 をコンピュータに入力しようとしたが,'+' キーが壊れていて数字のみが入力されてしまった.彼女が入力した(数字のみからなる)文字列 が与えられる.元の数式 の値として有り得るものの内,最大のものを求めよ.
解法
題意より, は,2 つの文字列 によって と表されます(ここで演算 は文字列の連結を表す).このとき, のそれぞれが表す整数値の和が,Alice が入力しようとした数式の値になります.
制約より, を 2 つの文字列に分割する方法は高々 7 通りしかありません.従って, の分割を全通り試し,そのそれぞれについて数式の値を計算する処理はごく短時間で完了します.従って,この方法で問題を解くことができます.
コード
template < typename T = int > using LIM = numeric_limits< T >; template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }; #define REP( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) class ForgetfulAddition { public: int minNumber( string expression ) { const int L = expression.size(); int res = LIM<>::max(); REP( i, 1, L ) { res = min( res, fromString< int >( expression.substr( 0, i ) ) + fromString< int >( expression.substr( i ) ) ); } return res; } };