2を2個,5を5個使い答えが2005になる演算式を作成する。条件は以下の通り。
ありゃ,今日も解答付きじゃん。やる気が…
今日が今年の最終問題日だと思ったけど,12月30日(金)が最終問題日か。
答えが載っているので解くのは止めようと思ったけど,10月28日の問題に似ているし,チョチョイと解いちゃいましょうと思った。
10月28日の問題を見ると,そちらは数字が固定になっている。
ありゃ?そのまま利用はできないぞ。
ただ,式は括弧を使っても良いので,逆ポーランド記法の演算式を作成するアプローチを取る。
その結果が2005になる場合を探す。結果を普通の演算式にするのは人間が行う。
数字と演算子を組み合わせて全て虱潰す。
2と5の利用数が2,5を越えてもダメだし,演算子が3個超になったところでも打ち切りできるし,爆発はしそうにないのでこれで良いかな?
実際は2,5の数字の並びが25か2と5の2つの数字の可能性があるので,上図の演算子の部分に以下の場合を追加する。
こうすると虱潰すプログラムは以下のようになる。
int num[] = { 2, 5}; // 使える数 int ope[] = { 0, 1/*Push*/, -1/*+*/, -2/*−*/, -3/*×*/, -4/*÷*/}; // 演算子, 0:何もしない,1:スタックに積む int used[] = {0,0}; // 数字を何個使ったか int mnum[] = { 2, 5}; // 2は2個,5は5個使える int mope = 3; // 演算子使用最大数 int nope = 0; // 演算子数 int main( int argc, cstring argv[]) { int buf[30]; for( int a=0; a< 2; a++) { used[a]++; buf[0] = num[a]; for( int b=0; b< 6; b++) { if( ope[b] < 0 && nope >= mope) continue; if( ope[b] < 0) nope++; buf[1] = ope[b]; for( int c=0; c< 2; c++) { if( used[c] >= mnum[c]) continue; used[c]++; buf[2] = num[c]; for( int d=0; d< 6; d++) { if( ope[d] < 0 && nope >= mope) continue; if( ope[d] < 0) nope++; buf[3] = ope[d]; for( int e=0; e< 2; e++) { if( used[e] >= mnum[e]) continue; used[e]++; buf[4] = num[e]; for( int f=0; f< 6; f++) { if( ope[f] < 0 && nope >= mope) continue; if( ope[f] < 0) nope++; buf[5] = ope[f]; for( int g=0; g< 2; g++) { if( used[g] >= mnum[g]) continue; used[g]++; buf[6] = num[g]; for( int h=0; h< 6; h++) { if( ope[h] < 0 && nope >= mope) continue; if( ope[h] < 0) nope++; buf[7] = ope[h]; for( int i=0; i< 2; i++) { if( used[i] >= mnum[i]) continue; used[i]++; buf[8] = num[i]; for( int j=0; j< 6; j++) { if( ope[j] < 0 && nope >= mope) continue; if( ope[j] < 0) nope++; buf[9] = ope[j]; for( int k=0; k< 2; k++) { if( used[k] >= mnum[k]) continue; used[k]++; buf[10] = num[k]; for( int l=0; l< 6; l++) { if( ope[l] < 0 && nope >= mope) continue; if( ope[l] < 0) nope++; buf[11] = ope[l]; for( int m=0; m< 2; m++) { if( used[m] >= mnum[m]) continue; used[m]++; buf[12] = num[m]; for( int n=0; n< 6; n++) { if( ope[n] < 0 && nope >= mope) continue; if( ope[n] < 0) nope++; buf[13] = ope[n]; if( nope != 0) { checkprint( buf); // 演算子は一つは無いとダメ } if( ope[n] < 0) nope--; } used[m]--; } if( ope[l] < 0) nope--; } used[k]--; } if( ope[j] < 0) nope--; } used[i]--; } if( ope[h] < 0) nope--; } used[g]--; } if( ope[f] < 0) nope--; } used[e]--; } if( ope[d] < 0) nope--; } used[c]--; } if( ope[b] < 0) nope--; } used[a]--; } return 0; }
後はcheckprint()を以下のようにすれば完成。
void checkprint( int buf[]) { // buf[]に入っている数字と演算子をスタックに積んで逆ポーランド記法と見なし計算する int n = 0; int ical = 0; int cal[30]; for( int i=0; i< 14; i++) { if( buf[i] == 1) { cal[ical++] = n; // 現在値をスタックに積む n = 0; } else if( buf[i] > 0) { n *= 10; // 数字は前の数字と合わせて新しい値になる n += buf[i]; } else if( buf[i] < 0) { // 演算子が出現した cal[ical++] = n; // 演算子の前の数字をスタックに積み, cal[ical++] = buf[i]; // 演算子もスタックに積む n = 0; // } } calcRPN( cal, ical); }
calcRPN()は10月28日版を流用する(ちょっと修正が必要)。
答えは2件出力されるが,a+bとb+aの違いなので実質1件。
ダイエットは何とか継続中。
ズボンのベルトをしないとズボンがそのまま脱げてしまうようになった(ずり落ちても腰で止まらない)。
これにはビックリした。
そういえば,今週は応募数と正解者数が載っていない。
解速度
1.2秒(PentiumV500MHz)