結果

問題 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]




*/
0