SRM522 Div1 Medium(450) CorrectMultiplication

TopCoder

CorrectMultiplication

|A-a|+|B-b|+|AB-c|

A,B≧1であることから、Aを固定してBを動かしたとき、BよりABのほうが大きく動くので、AB=cとすると値が最小になる。整数なので、その近辺の値を調べる。AとBのうち小さい方を動かすと、A, Bの最大値をnとして、O(√n)になる。

#include <algorithm>
using namespace std;

class CorrectMultiplication{public:
long long getMinimum( int a, int b, int c )
{
    long long ans = (long long)a+b+c-3;

    for ( long long x=1; (x-1)*(x-1)<=c; x++ )
    {
        ans = min( ans, abs(x-a)+abs(c/x-b)+abs(x*(c/x)-c) );
        ans = min( ans, abs(x-b)+abs(c/x-a)+abs(x*(c/x)-c) );
        ans = min( ans, abs(x-a)+abs(c/x+1-b)+abs(x*(c/x+1)-c) );
        ans = min( ans, abs(x-b)+abs(c/x+1-a)+abs(x*(c/x+1)-c) );
    }

    return ans;
}};