結果

問題 No.1862 Copy and Paste
ユーザー vjudge1vjudge1
提出日時 2024-11-13 22:03:48
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,934 bytes
コンパイル時間 1,871 ms
コンパイル使用メモリ 172,072 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-13 22:03:51
合計ジャッジ時間 3,384 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include<bits/stdc++.h>
#define Endl putchar('\n')
#define D(x)  cerr<<"D:"<<__LINE__<<' '<<#x<<':'<<x<<endl
#define out()  cerr<<"OUT:"
typedef __int128 ll;
using namespace std;
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f;}
inline void write(ll x){if(x>9)write(x/10);putchar(x%10+'0');return;}
const int N=2e5+20;
const ll INF=9e18;
inline ll pw(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)res=res*x;
		x=x*x;
		y>>=1;
		if(res>INF||x>INF)return INF;
	}
	return res;
}
inline pair<ll,ll> _get(ll x,ll y){
	ll l=0,r=INF,res=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(pw(mid,y)==x)return {mid,mid};
		if(pw(mid,y)<x)l=mid+1;
		else r=mid-1;
	}
	return {min(l,r),max(l,r)};
}
inline ll min(ll x,ll y){
	return x>y?y:x;
}
int main(){
//	freopen("dice.in","r",stdin);
//	freopen("dice.out","w",stdout);
	ll x=read(),y=read(),n=read();
	if(n==1){
		cout<<0<<'\n';
		return 0;
	}
	n--;
	ll res=INF;
	for(int i=1;i<=64;i++){
//		if(i>n)break;
		pair<ll,ll> p=_get(n,i);
//		cout<<p.first<<' '<<p.second<<'\n';
		for(int k=p.first;k<=p.second;k++){
			for(int a=0;a<i;a++){
				ll now=0,f=1,cnt=1;
				for(int j=1;j<i;j++){
					now+=x+y*(j<=a?k-1:k);
					cnt+=f*(j<=a?k-1:k);
					f=cnt;
				}
//				cout<<"update:"<<cnt<<' '<<now<<' '<<k<<' '<<i<<' '<<f<<'\n';
				if(cnt<=n){
					now+=x+y*ceil(1.0*(n-cnt+1)/f);
					cnt+=f*ceil(1.0*(n-cnt+1)/f);
				}
//				cout<<"change"<<now<<'\n';
				res=min(res,now);
			}
			for(int a=0;a<i;a++){
				ll now=0,f=1,cnt=1;
				for(int j=1;j<i;j++){
					now+=x+y*(j>a?k+1:k);
					cnt+=f*(j>a?k+1:k);
					f=cnt;
				}
//				cout<<"update:"<<cnt<<' '<<now<<' '<<k<<' '<<i<<' '<<f<<'\n';
				if(cnt<=n){
					now+=x+y*ceil(1.0*(n-cnt+1)/f);
					cnt+=f*ceil(1.0*(n-cnt+1)/f);
				}
//				cout<<"change"<<now<<'\n';
				res=min(res,now);
			}
		}
	}
	write(res);
	return 0;
}
0