A〜Jに0〜9の数字を割り当て以下の計算式を成り立つようにする。
AB + CDEFG / HIJ = 100
但しCは0では無い。ABが最大になる式を求める。
数字の割り当て問題は人間にとっては計算量が多いかも知れないが,コンピュータを使えば大した問題で無い。4月3日の問題に似ている。
C,D,E,F,G,H,I,J に0〜9の数字を割り当てる。
コードは以下の通り。
for( int c=1; c<= 9; c++) { // cは0でないことは判っている
used[c] = YES;
for( int d=0; d<= 9; d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=0; e<= 9; e++) {
if( used[e]) continue;
used[e] = YES;
for( int f=0; f<= 9; f++) {
if( used[f]) continue;
used[f] = YES;
for( int g=0; g<= 9; g++) {
if( used[g]) continue;
used[g] = YES;
for( int h=0; h<= 9; h++) {
if( used[h]) continue;
used[h] = YES;
for( int i=0; i<= 9; i++) {
if( used[i]) continue;
used[i] = YES;
for( int j=0; j<= 9; j++) {
if( used[j]) continue;
used[j] = YES;
int v = c * 10000 + d * 1000 + e * 100 + f * 10 + g;
int u = h * 100 + i * 10 + j;
if( (v % u) == 0) { A,B を求め AB + CDEFG/HIJ=100
を満たす最大のABを出力する }
used[j] = NO;
}
used[i] = NO;
}
used[h] = NO;
}
used[g] = NO;
}
used[f] = NO;
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
ABの求め方
int a = -1, b = -1;
for( int k=0; k< 10; k++) {
if( !used[k]) { a=b; b=k;}
}
used[ ]のうちNOなのは2つしかないので,A,Bを求めるには上記コードで良い。
AB+CDEFG/HIJ=100を満たす最大のAB
A,Bに2つの数字を割り当てたら,式が成立するか判断する。
if( (a * 10 + b + v / u) == 100) {
maxab = max( maxab, a*10+b);
if( (a*10+b) == maxab) ps( "%d%d + %d%d%d%d%d / %d%d%d = 100\n", a,b,c,d,e,f,g,h,i,j);
}
A,BはAとBを入れ替えても良いので入れ替えて,式が成立するか判断する。
swap( a, b);
if( (a * 10 + b + v / u) == 100) {
maxab = max( maxab, a*10+b);
if( (a*10+b) == maxab) ps( "%d%d + %d%d%d%d%d / %d%d%d = 100\n", a,b,c,d,e,f,g,h,i,j);
}
式が成立し過去の最大値よりも大きな値が出現したら式を出力する。
複数の結果が出力されると思ったが一つしか出力されなかった。上記コードでは最初に大きな数字が出現したためである。
100になる場合を全て出力するように変更したところ9件出力された。そのうち最初に出力された式が答えになる。
解速度
即