結果

問題 No.1862 Copy and Paste
ユーザー vjudge1
提出日時 2024-11-13 22:06:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,510 bytes
コンパイル時間 1,914 ms
コンパイル使用メモリ 195,940 KB
最終ジャッジ日時 2025-02-25 04:06:48
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define int __int128 
#define mp(x,y) make_pair(x,y)
#define se second
#define fi first
using namespace std;
typedef pair<int,int> PII; 
namespace read_and_write{
    int read(){ int x=0; bool flag=1; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} return flag? x:-x;}
    template<typename T> void read(T &x){ bool flag=1; x=0; char ch=getchar();
        while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
        while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();} x=(flag? x:-x);}
    template<typename T,typename ...Args> void read(T &Re,Args &...Res){read(Re),read(Res...);}
    template<typename T> void write(T x,bool c=0){ if(x<0){x=-x,putchar('-');}
        static short s[35],top=-1; do{s[++top]=x%10,x/=10;}while(x);
        while(~top) putchar(s[top--]+48); putchar(c? ' ':'\n');}
    template<typename T,typename ...Args> void write(T &Pr,Args &...Prs){write(Pr,1),write(Prs...);}
} using namespace read_and_write;
int ksm(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
        ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
bool check1(int a,int b,int K)//<=
{
    int ans=1;
    while(b)
    {
        if(ans>K || a>K)
        return false;
        if(b&1)
        ans=ans*a;
        a=a*a;
        b>>=1;
//      write(ans,a);
    }
    return ans<=K;
}
bool check2(int a,int b,int K)//>=
{
    int ans=1;
    while(b)
    {
        if(ans>=K || a>=K)
        return true;
        if(b&1)
        ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans>=K;
}
const int maxn=1e18+5;
const int max_xy=1e9+5;
const int INF=1e36;
int n,T[2];
namespace SubTask2
{
    int LOG_2(int n)
    {
        int left=1,right=n;
        while(left<right)
        {
            int mid=(left+right+1)>>1;
            if(check1(2,mid,n))
            left=mid;
            else
            right=mid-1;
        }
        return left;
    }
    int doit(int k)
    {
        int left=1,right=n;
        while(left<right)
        {
            int mid=(left+right)>>1;
            if(check2(mid,k,n))
            right=mid;
            else
            left=mid+1;
        }
        int i,now=left*k;
        for(i=1;i<=k;i++)
        {
            if(check2(left,k-i,n) || check2(left-1,i,n) || ksm(left,k-i)*ksm(left-1,i)>=n)
            now--;
            else
            break;
        }
        return now-k;
    }
    int solve()
    {
        int i,k=LOG_2(n),ans=INF;
//      write(k,1);
        for(i=1;i<=k+1;i++)
        ans=min(ans,i*T[0]+doit(i)*T[1]);
        return ans;
    }
}
signed main()
{
//  freopen("dice.in","r",stdin);
//  freopen("dice.out","w",stdout);
read(T[0],T[1],n);
    //read(n,T[0],T[1]);
//  write(check1(2,1000000000,2134)? 1:0);
    write(SubTask2::solve());
    return 0;
}
/*
???????????x 
          ????y
x+y       2*y
T[0]      T[1]+T[0]
*/
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0