結果

問題 No.375 立方体のN等分 (1)
ユーザー kotarou777775
提出日時 2016-06-05 00:16:22
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 181 ms
コード長 1,536 Byte
コンパイル時間 1,022 ms
使用メモリ 1,504 KB
最終ジャッジ日時 2018-09-26 18:49:30

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
sample1.txt AC 3 ms
1,504 KB
sample2.txt AC 2 ms
1,500 KB
system_test1.txt AC 30 ms
1,500 KB
t01.txt AC 2 ms
1,500 KB
t02.txt AC 2 ms
1,500 KB
t03.txt AC 3 ms
1,504 KB
t04.txt AC 3 ms
1,504 KB
t05.txt AC 7 ms
1,500 KB
t06.txt AC 22 ms
1,504 KB
t07.txt AC 7 ms
1,500 KB
t08.txt AC 12 ms
1,500 KB
t09.txt AC 12 ms
1,500 KB
t10.txt AC 14 ms
1,500 KB
t11.txt AC 13 ms
1,500 KB
t12.txt AC 73 ms
1,500 KB
t13.txt AC 18 ms
1,500 KB
t14.txt AC 15 ms
1,500 KB
t15.txt AC 125 ms
1,500 KB
t16.txt AC 79 ms
1,504 KB
t17.txt AC 17 ms
1,504 KB
t18.txt AC 13 ms
1,504 KB
t19.txt AC 13 ms
1,504 KB
t20.txt AC 181 ms
1,504 KB
t21.txt AC 15 ms
1,504 KB
t22.txt AC 13 ms
1,496 KB
t23.txt AC 29 ms
1,504 KB
t24.txt AC 16 ms
1,500 KB
t25.txt AC 18 ms
1,500 KB
t26.txt AC 12 ms
1,500 KB
t27.txt AC 12 ms
1,504 KB
t28.txt AC 15 ms
1,500 KB
t29.txt AC 16 ms
1,500 KB
t30.txt AC 13 ms
1,504 KB
t31.txt AC 16 ms
1,500 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a,c) memset(a,c,sizeof(a))

#define DEBUG(x) cout<<"#x"<<": "<<x<<endl

using namespace std;

typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vl;

const ll INF = INT_MAX/3;
const ll MOD = 1000000007;
const double EPS = 1e-14;
const int dx[] = {1,0,-1,0} , dy[] = {0,1,0,-1};

pair<ll,ll> cal(ll n){
    pair<ll,ll> ret;
    ll sum = n*20LL;
    ll sn = sqrt( double(n) ) + 1;
    ll a,b;
    FOR(i,1,sn+1){
        if( n % ll(i) == 0){
            if(sum > i +  n/ll(i)){
                sum = i + n/ll(i);
                a = i;
                b = n/ll(i);
            }
        }
    }
    ret = MP(a,b);
    return ret;

}

int main(){
    ll n;
    cin >> n;
    ll sn = sqrt( double(n) ) + 1;
    int a,b;
    ll sum = n*20LL;
    auto hoge = cal(n);
    a = hoge.first;
    b = hoge.second;
    ll ans = n*20LL;

    FOR(i,1,sn+1){
        if( n % ll(i) == 0){
            auto temp = cal(i);
            ans = min(ans,n/ll(i)-1 + temp.first + temp.second - 2);
            temp = cal(n/ll(i));
            ans = min(ans, i-1 + temp.first + temp.second - 2);
        }
    }

    cout << ans << " " << n-1LL <<  endl;


    return 0;
}


0