朝日新聞2006年9月8日のパズル横丁問題

問題

N等分した5個のケーキがある。5個それぞれでNの値は違うものとする。

それぞれから1辺ずつ取り出し集めると一つのケーキになる。分割の方法は？

但し分割の総数が最小のものを答えとする。

解答への道(ヒント)

相変わらず生活は夏休みの宿題状態。悲惨な状況が続く。こんな時に星3つ問題かよーと思いきや，プログラマにはありがたい問題。

以下の数式を満たすa,b,c,d,eを求めれば良い。

通分すれば

分母と分子を別々に計算して一致すればOK。100位まで廻せば十分でしょう。プログラムは以下のようになる。

  int m = 100;
  for( int a=2; a< m; a++) {
    for( int b=a+1; b< m; b++) {
      for( int c=b+1; c< m; c++) {
        for( int d=c+1; d< m; d++) {
          for( int e=d+1; e< m; e++) {
            int T1 = b*c*d*e + a*c*d*e + a*b*d*e + a*b*c*e + a*b*c*d; // 分子
            int T2 = a*b*c*d*e; // 分母
            if( T1 < T2) {
              // 結果は1未満,これ以上探しても更に小さい数になるので探索終了
              break;
            }
            else if( T1 == T2) { // T1 / T2 = 1
              // 見つけた
            }
          }
        }
      }
    }
  }
  // 最小のa+b+c+d+eを出力する。

注意すべきは答えが1になる組み合わせが複数あるってこと。合計値が最小のものを記録して最後に出力する。

飼っている琉金がまた死にそうになった。これで何回目だろうか。今度こそダメかと思ったが今回も無事復活。

解速度

即