QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#293705#4003. Rounding Master雷神之怒#AC ✓1ms4092kbC++141.8kb2023-12-29 16:44:312023-12-29 16:44:32

Judging History

This is the latest submission verdict.

  • [2023-12-29 16:44:32]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 4092kb
  • [2023-12-29 16:44:31]
  • Submitted

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define int __int128
#define se second
#define double long double

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

int n,k;

#define EPS 1e-7
int dcmp(double x){
	if(fabs(x)<EPS)return 0;
	if(x>0)return 1;
	return -1;
}
signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	int x=1;
	n=read(),k=read();
	double L=1.5;
	auto to=[&](int t,double v){
		double tt=t;
		tt=tt*v;
		return ((int)(tt+0.5));
	};
	double R=n;
	if(n==1)return puts("0.5"),0;
	if(k==1){
		cout<<fixed<<setprecision(6)<<R-0.5<<endl;
		return 0;
	}
	if(k>=200)return puts("1.5"),0;
	while(dcmp(R-L)>0){
		double mid=(L+R)/2.000;
		// cout<<"L,R = "<<L<<" "<<R<<endl;
		// cout<<"mid = "<<fixed<<setprecision(6)<<mid<<endl;
		int cur=x;bool chk=0;
		for(int i=1;i<=k;i++){
			cur=to(cur,mid);
			if(cur>=n){chk=1;break;}
		}
		// cout<<"chk = "<<chk<<" -> L,R = "<<L<<" "<<R<<endl;
		if(chk)R=mid;
		else L=mid;
	}
	cout<<fixed<<setprecision(6)<<L<<endl;
	// int cnt=0;
	// while(x<n)cnt++,x=to(x,L);
	// cout<<"cnt = "<<cnt<<endl;

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3944kb

input:

18 4

output:

2.125000

result:

ok found '2.1250000', expected '2.1250000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

1 1

output:

0.5

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

1000000000000000000 1000000000000000000

output:

1.5

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

2 100000

output:

1.5

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

1 1000000000000000000

output:

0.5

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

1000000000000000000 1

output:

999999999999999999.500000

result:

ok found '1000000000000000000.0000000', expected '1000000000000000000.0000000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

2 1000000000000000000

output:

1.5

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

1000000000000000000 2

output:

1000000000.000000

result:

ok found '1000000000.0000000', expected '1000000000.0000000', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

265714758284843011 6476356347841896

output:

1.5

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3916kb

input:

266540997167959139 92

output:

1.541667

result:

ok found '1.5416670', expected '1.5416667', error '0.0000002'

Test #11:

score: 0
Accepted
time: 0ms
memory: 4076kb

input:

998169857863230070 46

output:

2.474067

result:

ok found '2.4740670', expected '2.4740667', error '0.0000001'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

762322967106512617 94

output:

1.544288

result:

ok found '1.5442880', expected '1.5442884', error '0.0000003'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

494087735053841727 1

output:

494087735053841726.500000

result:

ok found '494087735053841728.0000000', expected '494087735053841728.0000000', error '0.0000000'

Test #14:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

58564077538358873 97

output:

1.500000

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #15:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

518101003270379436 40

output:

2.769995

result:

ok found '2.7699950', expected '2.7699947', error '0.0000001'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

278796295010358752 12

output:

28.469745

result:

ok found '28.4697450', expected '28.4697449', error '0.0000000'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

679814304673935850 67

output:

1.842437

result:

ok found '1.8424370', expected '1.8424368', error '0.0000001'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

963457718519969787 22

output:

6.547315

result:

ok found '6.5473150', expected '6.5473154', error '0.0000001'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

267367244641009859 41

output:

2.652951

result:

ok found '2.6529510', expected '2.6529507', error '0.0000001'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

740983904691688417 65

output:

1.877597

result:

ok found '1.8775970', expected '1.8775968', error '0.0000001'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

941365965213552512 82

output:

1.655317

result:

ok found '1.6553170', expected '1.6553168', error '0.0000001'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

284337374294498000 38

output:

2.872202

result:

ok found '2.8722020', expected '2.8722016', error '0.0000001'

Test #23:

score: 0
Accepted
time: 0ms
memory: 4088kb

input:

812120465372795700 38

output:

2.956315

result:

ok found '2.9563150', expected '2.9563155', error '0.0000002'

Test #24:

score: 0
Accepted
time: 0ms
memory: 3808kb

input:

564561304973603673 7

output:

343.500000

result:

ok found '343.5000000', expected '343.5000000', error '0.0000000'

Test #25:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

333368798444245171 30

output:

3.834613

result:

ok found '3.8346130', expected '3.8346128', error '0.0000000'

Test #26:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

959976653971901732 69

output:

1.817051

result:

ok found '1.8170510', expected '1.8170508', error '0.0000001'

Test #27:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

268193483524125987 37

output:

2.954568

result:

ok found '2.9545680', expected '2.9545683', error '0.0000001'

Test #28:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

260425914665370955 71

output:

1.752992

result:

ok found '1.7529920', expected '1.7529920', error '0.0000000'

Test #29:

score: 0
Accepted
time: 0ms
memory: 4012kb

input:

897036930760783895 17

output:

11.404000

result:

ok found '11.4040000', expected '11.4040000', error '0.0000000'

Test #30:

score: 0
Accepted
time: 0ms
memory: 4088kb

input:

74587017830121569 24

output:

5.051587

result:

ok found '5.0515870', expected '5.0515873', error '0.0000001'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3912kb

input:

565676857502199822 83

output:

1.634508

result:

ok found '1.6345080', expected '1.6345080', error '0.0000000'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

834393643531603718 27

output:

4.595588

result:

ok found '4.5955880', expected '4.5955882', error '0.0000000'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

611313338732907397 47

output:

2.396552

result:

ok found '2.3965520', expected '2.3965517', error '0.0000001'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3856kb

input:

269019726702209411 91

output:

1.549135

result:

ok found '1.5491350', expected '1.5491351', error '0.0000001'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3864kb

input:

779867924639053494 90

output:

1.575774

result:

ok found '1.5757740', expected '1.5757741', error '0.0000001'

Test #36:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

76079933162791087 6

output:

650.935259

result:

ok found '650.9352590', expected '650.9352593', error '0.0000000'

Test #37:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

864836661365745138 48

output:

2.370549

result:

ok found '2.3705490', expected '2.3705488', error '0.0000001'

Test #38:

score: 0
Accepted
time: 0ms
memory: 4016kb

input:

319233245336636649 83

output:

1.622558

result:

ok found '1.6225580', expected '1.6225576', error '0.0000002'

Test #39:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

880853945234827955 98

output:

1.518748

result:

ok found '1.5187480', expected '1.5187481', error '0.0000001'

Test #40:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

269845965585325539 86

output:

1.590214

result:

ok found '1.5902140', expected '1.5902140', error '0.0000000'

Test #41:

score: 0
Accepted
time: 0ms
memory: 3880kb

input:

299309934612736033 50

output:

2.247161

result:

ok found '2.2471610', expected '2.2471614', error '0.0000002'

Test #42:

score: 0
Accepted
time: 0ms
memory: 3980kb

input:

31750903004989766 46

output:

2.289217

result:

ok found '2.2892170', expected '2.2892174', error '0.0000002'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3984kb

input:

878458341756144515 26

output:

4.898750

result:

ok found '4.8987500', expected '4.8987503', error '0.0000001'

Test #44:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

72789637466040772 32

output:

3.377803

result:

ok found '3.3778030', expected '3.3778033', error '0.0000001'

Test #45:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

270672213058376259 95

output:

1.520106

result:

ok found '1.5201060', expected '1.5201065', error '0.0000003'

Test #46:

score: 0
Accepted
time: 0ms
memory: 4092kb

input:

42123981441194380 57

output:

1.954219

result:

ok found '1.9542190', expected '1.9542195', error '0.0000002'

Test #47:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

423890230884993629 93

output:

1.541686

result:

ok found '1.5416860', expected '1.5416857', error '0.0000002'

Test #48:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

668707985291768083 4

output:

28596.337030

result:

ok found '28596.3370300', expected '28596.3370297', error '0.0000000'

Test #49:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

271498451941492387 52

output:

2.168649

result:

ok found '2.1686490', expected '2.1686493', error '0.0000001'

Test #50:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

561565987119909623 68

output:

1.818750

result:

ok found '1.8187500', expected '1.8187500', error '0.0000000'

Test #51:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

166464870954228340 74

output:

1.708105

result:

ok found '1.7081050', expected '1.7081047', error '0.0000002'

Test #52:

score: 0
Accepted
time: 0ms
memory: 4088kb

input:

272324690824608515 48

output:

2.308422

result:

ok found '2.3084220', expected '2.3084215', error '0.0000002'

Test #53:

score: 0
Accepted
time: 0ms
memory: 3920kb

input:

81007997093592161 28

output:

4.018877

result:

ok found '4.0188770', expected '4.0188771', error '0.0000000'

Test #54:

score: 0
Accepted
time: 0ms
memory: 3944kb

input:

273150934002691939 102

output:

1.500000

result:

ok found '1.5000000', expected '1.5000000', error '0.0000000'

Test #55:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

1000000000000000000 101

output:

1.500195

result:

ok found '1.5001950', expected '1.5001951', error '0.0000001'