Test 6.23 T1 扫雷

题目背景

题目描述

输入格式

输出格式

样例输入输出

数据范围

解析

我们设两个作弊器的参数分别为\((a_1,b_1)\)和\((a_2,b_2)\)，那么设

\[S1=\frac{a_1}{b_1},S2=\frac{a_2}{b_2}
\]

假如我们同时选择这两个作弊器，那么得到的Maxtire时间则为

\[S=\frac{a_1+a_2}{b_1+b_2}
\]

不妨设\(S1<S2\)，那么

\[S1-S2=\frac{a_2b_1-a_1b_2}{b_1b_2}>0\Rightarrow a_2b_1-a_1b_2>0
\]

所以

\[S-S1=\frac{a_2b_1-a_1b_2}{(b_1+b_2)b_1}>0\Rightarrow S>S1
\]

同理可得，\(S<S2\)。

由此类推，无论我们怎么选择，总能找到一个形如\(\frac{a_i}{b_i}\)的单个分数为最小值。这个分数即为将所有\(a_i/b_i\)排序后的最小值。由于最小值可能有多个，且多个相同的值合起来仍是相同的，所以设最小值有\(m\)个，则最后的方案数为

\[C_m^1+C_m^2+...+C_m^m=2^m-1
\]

代码

#include <iostream>

#include <cstdio>

#include <iomanip>

#include <algorithm>

#include <cmath>

#define N 1000002

using namespace std;

const int mod=998442553;

const double eps=1e-10;

int t,n,i,cnt;

double a[N],b[N],c[N];

int poww(int a,int b)

{

	long long ans=1,base=a;

	while(b){

		if(b&1) ans=ans*base%mod;

		base=base*base%mod;

		b>>=1;

	}

	return ans%mod;

}

int main()

{

	freopen("mine.in","r",stdin);

	freopen("mine.out","w",stdout);

	cin>>t;

	while(t--){

		cin>>n;

		for(i=1;i<=n;i++) cin>>a[i];

		for(i=1;i<=n;i++) cin>>b[i];

		for(i=1;i<=n;i++) c[i]=b[i]/a[i];

		sort(c+1,c+n+1);

		if(c[1]<=1.0*10000){

			cnt=1,i=2;

			while(i<=n&&fabs(c[i]-c[1])<=eps) cnt++,i++;

			cout<<setprecision(8)<<fixed<<c[1]<<' '<<(poww(2,cnt)-1)%mod<<endl;

		}

		else cout<<"Impossible"<<endl;

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

巴特西