結果

問題 No.1862 Copy and Paste
ユーザー vjudge1vjudge1
提出日時 2024-11-13 22:06:01
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,510 bytes
コンパイル時間 2,433 ms
コンパイル使用メモリ 203,552 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-13 22:06:05
合計ジャッジ時間 3,814 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

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