SRM 522 DIV1 Middle - CorrectMultiplication （復習×××）
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11604&rd=14547
正の整数a,b,cが与えられる。
正の整数A,B,Cがa,b,cをそれぞれ増減した値であるとき
A*B=Cが成り立つ、|A-a|+|B-b|+|C-c|の最小値を求める。
解き方
Cの値の最大値がわからないと手掛かりがないため、まずはCの最大値を求める。
答えは|A-a|+|B-b|+|C-c|であることから最小である答えが1*1=1であるとき
答えの最大値はa+b+c-3となる。
つまり、Cの最大値はc+a+b+c-3となる。
次に、Aを１から調べていく。
Ｂも同様に調べることで対称性があるので、ＡはＡ＊Ａ＜＝Ｃの最大値まで調べればよい。
Ａが決まったとき、Ｂはc/Aの±１の範囲で最適なCが存在するのでそれぞれの場合について|A-a|+|B-b|+|C-c|の最小値を更新していくことで答えが求まる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CorrectMultiplication {
public: long long getMinimum(int a, int b, int c) {
long long ret=1e+18;
long long maxans=(long long)a+b+c-3;
for(long long A=1;A<=(maxans+c)/A;A++){
for(int p=-1;p<=1;p++){
long long B=c/A+p;
if(B>=1){
long long C=A*B;
ret=min(ret,(long long)(labs(A-a)+labs(B-b)+labs(C-c)));
}
}
}
for(long long B=1;B<=(maxans+c)/B;B++){
for(int p=-1;p<=1;p++){
long long A=c/B+p;
if(A>=1){
long long C=A*B;
ret=min(ret,(long long)(labs(A-a)+labs(B-b)+labs(C-c)));
}
}
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CorrectMultiplication {
public: long long getMinimum(int a, int b, int c) {
long long ret=1e+18;
long long maxans=(long long)a+b+c-3;
for(long long A=1;A<=(maxans+c)/A;A++){
for(int p=-1;p<=1;p++){
long long B=c/A+p;
if(B>=1){
long long C=A*B;
ret=min(ret,(long long)(labs(A-a)+labs(B-b)+labs(C-c)));
}
}
}
for(long long B=1;B<=(maxans+c)/B;B++){
for(int p=-1;p<=1;p++){
long long A=c/B+p;
if(A>=1){
long long C=A*B;
ret=min(ret,(long long)(labs(A-a)+labs(B-b)+labs(C-c)));
}
}
}
return ret;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CorrectMultiplication {
public: long long getMinimum(int a, int b, int c) {
long long ret=(long long )a+b+c-3;
for(long long x=1;(x-1)*(x-1)<=c;x++){
ret=min(ret,(long long)(labs(x-a)+labs(c/x-b)+labs(x*(c/x)-c)));
ret=min(ret,(long long)(labs(x-a)+labs(c/x-1-b)+labs(x*(c/x-1)-c)));
ret=min(ret,(long long)(labs(x-a)+labs(c/x+1-b)+labs(x*(c/x+1)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x-a)+labs(x*(c/x)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x-1-a)+labs(x*(c/x-1)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x+1-a)+labs(x*(c/x+1)-c)));
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CorrectMultiplication {
public: long long getMinimum(int a, int b, int c) {
long long ret=(long long )a+b+c-3;
for(long long x=1;(x-1)*(x-1)<=c;x++){
ret=min(ret,(long long)(labs(x-a)+labs(c/x-b)+labs(x*(c/x)-c)));
ret=min(ret,(long long)(labs(x-a)+labs(c/x-1-b)+labs(x*(c/x-1)-c)));
ret=min(ret,(long long)(labs(x-a)+labs(c/x+1-b)+labs(x*(c/x+1)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x-a)+labs(x*(c/x)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x-1-a)+labs(x*(c/x-1)-c)));
ret=min(ret,(long long)(labs(x-b)+labs(c/x+1-a)+labs(x*(c/x+1)-c)));
}
return ret;
}
};
