自动搬运

查看原文

来自洛谷，原作者为

	qinyiyang2012 Questa è persona

搬运于2025-08-24 23:00:05，当前版本为作者最后更新于2025-06-13 11:24:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析

设安打次数为 $p$，打击次数为 $q$，且 $p < q,q \ne 0$。 $\frac{p}{q}$ 四舍五入后为 $r$ 则意味着 $r - \frac{5}{10^{n+1}} \leqslant \frac{p}{q} < r + \frac{5}{10^{n+1}}$。

例如安达率四舍五入后为 $0.316$，则 $0.3155 \leqslant \frac{p}{q} < 0.3165$。

注意到这其实是 P5179 Fraction，我们只需要再处理一下 $r - \frac{5}{10^{n+1}} = \frac{p}{q}$ 的特殊情况即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string r;
ll qpow(ll x,ll y){
	ll res=1;
	while(y){
		if(y&1)res*=x;
		x*=x;
		y>>=1;
	}
	return res;
}
void query(ll a,ll b,ll& p,ll& q,ll c,ll d){
	if(a<b&&c>d){
		p=q=1;
		return;
	}
	query(d%c,c,q,p,b-d/c*a,a);
	q+=d/c*p;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	while(cin>>n>>r){
		ll x=0,p,q;
		for(int i=2;i<r.size();i++)x=x*10+(r[i]-'0');
		if(!x){//安达率为0记得特判
			cout<<"1\n";
			continue;
		}
		ll a=x*10-5,b=qpow(10,n+1),c=x*10+5,d=qpow(10,n+1);
    //处理取等号的情况
		ll p1=a,q1=b,g=__gcd(p1,q1);
		p1/=g,q1/=g;
		query(a,b,p,q,c,d);
		cout<<min(q,q1)<<"\n";
	}
	return 0;
}