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になる組み合わせが複数あるってこと。合計値が最小のものを記録して最後に出力する。
飼っている琉金がまた死にそうになった。これで何回目だろうか。今度こそダメかと思ったが今回も無事復活。
解速度
即