結果

問題 No.375 立方体のN等分 (1)
ユーザー Grun1396Grun1396
提出日時 2017-02-25 08:46:06
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,556 bytes
コンパイル時間 559 ms
コンパイル使用メモリ 59,628 KB
実行使用メモリ 4,500 KB
最終ジャッジ日時 2023-09-02 07:56:43
合計ジャッジ時間 2,368 ms
ジャッジサーバーID
（参考情報） 		judge16 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 WA -
testcase_03 AC 1 ms
4,380 KB
testcase_04 WA -
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <math.h>
using namespace std;


//素数判定,素数でない時は割り切れる数を返す
//
int is_prime(int n){
    if(n < 2) return -1;//素数ではない
    if(n % 2==0)return 2;
    for(int d = 2; d < sqrt(n);d++){
        if(n % d == 0) return d;
    }

    return 0;//素数
}

int func(int n){
    
    int tmp = is_prime(n);
    //cout << "func_ " << n << "called" << " tmp:" <<  tmp << endl;
    if(tmp==0){
        return n-1;
    }else{
        return func(tmp) + func(n/tmp); 
    }    
}

int main(){
    int n=12;//立方体をn個の合同な直方体に分割したい。
    cin >> n;
//cout << "tes" <<endl;
/*
具体例考える
2: ある面の中心に沿って切る。　tmax:1 tmin:1
3: 上と同様？　tmax:2 tmin:2
4: 面に平行に3回切る? tmax:3 tmin:2(縦１横１)
5:上に同じ？
6: 面に平行に5回切る、 横に１回、縦に２回で３回も可能
7: n-1回
8: 面に平行に７回、x,y,z軸に平行に１回ずつで３回
9: tmin:3等分→3個(2time) -> さらに３等分(2time) ->total 4time
多分最大は必ずn-1回？　問題は最小で済ませる時。
15: tmax:14 tmin:5等分して3等分？ -> func(3) + func(15/3)

増える数について考察してみる。
Ｎ等分されているとき。。。（Ｎ＋１）個あることになる。
これを半分にすれば2(N+1)個作れる。　切る回数はN+1回か？　－＞6の場合では N=2なので3
さらに半分で4(N+1)になる？切る回数はN+2回？

切る順番に影響されるか？
横２回、縦1回について・・・
yyt -> 3*2-> 6
yty -> 2*2*...
tyy
合同にするには必ず、Ｘ→Ｙ→Ｚ軸にそって等分していかないとだめでは？
*/
    int Tmin = 0,Tmax = n-1;
    
   // cout << n << " " << Tmin  << " " << Tmax<<endl;
    if(n % 2 == 0){
        if(n==2){//１回だけ切ればいい
            Tmin = 1;
  //          Tmax = 1;
        }else if(n%4==0){
  //          Tmax = n-1;
            Tmin = 2 + func(n/4);
        }else {
            //2*素数
            Tmin = 1 + func(n/2);
        }
    }else{//奇数
        //3,5以外の素数の時はTmax = Tmin = n-1
        
        if(is_prime(n) == 0){
            Tmax = Tmin = n-1;
        }else{
        //素数ではない時は別の計算が必要だと思う
     //       Tmax = n-1; 
           // cout << is_prime(n) << ";ed22" <<endl;
            Tmin =  func(n);
        }
    }
  //  cout << n << endl;
    cout << Tmin << " " << Tmax << endl;
    
    return 0;
}
0