結果

問題 No.375 立方体のN等分 (1)
コンテスト
ユーザー Grun1396
提出日時 2017-02-25 08:51:07
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other MLE * 1 -- * 31
権限があれば一括ダウンロードができます

ソースコード

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