結果

問題 No.375 立方体のN等分 (1)
ユーザー Grun1396Grun1396
提出日時 2017-02-25 08:51:07
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,599 bytes
コンパイル時間 575 ms
コンパイル使用メモリ 59,568 KB
実行使用メモリ 814,208 KB
最終ジャッジ日時 2024-06-11 14:52:41
合計ジャッジ時間 2,194 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

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


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

    return 0;//素数
}

long long func(long long n){
    
    long long 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(){
    long long n;//立方体を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
合同にするには必ず、Ｘ→Ｙ→Ｚ軸にそって等分していかないとだめでは？
*/
    long long 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