SRM522 Div2 Hard(900) CorrectMultiplicationTwo

TopCoder

CorrectMultiplicationTwo

全部を1にすれば常に正しくなるので、答えは高々a+b+c-3。AとBの値を探索してA*Bがc+(a+b+c-3)より大きくなったら処理を打ち切るようにすれば、制限時間に間に合う。

#include <algorithm>
using namespace std;

class CorrectMultiplicationTwo{public:
int getMinimum( int a, int b, int c )
{
    int m = a+b+c;
    int ans = m;
    for ( int A=1; A<=m; A++ )
    for ( int B=1; B<=m; B++ )
    {
        int C = A*B;
        ans = min( ans, abs(A-a)+abs(B-b)+abs(C-c) );
        if ( C-c >= m )
            break;
    }

    return ans;
}};