P1080 King Game

Transfer

The minimum and maximum value is two points at a glance. qwq

span>

But the goose doesn’t know how to check, so we change our thinking

We ask for The minimum and maximum values ​​must be related to the arrangement of ministers. Will there be any rules?

Look at the situation with only two ministers first

Arrangement: 1 2, ans1=max{a₀/b₁,a₀a₁/b₂}

Arrangement: 2 1, ans2=max{a₀/b₂,a₀a₂/b₁}

Apparently a₀/b₁0a₂/b_1,a0/b20a₁/b₂, so the maximum value depends on a₀a₁/b₂ and a₀a₂ /b₁

In order to minimize the maximum value, when ans1>ans2, we will switch the order of 1, 2

So it is a₀a₁/b₂>a₀a₂/ b₁, which is a₁b₁>a₂b₂ It will be changed in time.

To sum up, it is possible to sort by a*b from small to large

In fact, the difficulty of this question is not in the sorting idea, but in high precision.

a,b<10000,n<1000, the worst case ans=10000¹⁰⁰⁰, cool

It is recommended to combine the code to eat

#include

#define ll long long

using namespace std;

ll read()

{

 char ch=getchar();

 ll x=0;bool f=0;

 while(ch<'0'||ch>' 9')

 {

 if(ch=='-')f=1 ;

 ch=getchar();

}

 while(ch>='0'&&ch<=' 9')

 {

 x=(x<<3)+(x<<1 )+(ch^48);

 ch=getchar();

}

 return f?-x:x;

}

struct rr

{

 ll a,b;

}ren[1009];

ll n,aa,bb,sa[7009],now[ 7009],ma[7009],lenm=1,lens= 1,lenn=1; //sa records the product of the numbers on the left hand of the ministers, now records the current minister’s gold coins, and ma records the maximum value

bool cmp(rr t,rr w)

{

 return t.a*t.bw.b;

}

//The following is high-precision

void cheng(ll k)//High precision multiplication

{

 sa[1]*=k;

 for(int i=2;i<=lens;i++)

 {

 sa[i]=sa[i-1]/10< /span>+sa[i]*k;

 sa[i-1]%=10< span style="color: #000000;">;

}

 while(sa[lens]>=10< span style="color: #000000;">)

 {

 lens++;

 sa[lens]=sa[lens-1]/10< /span>;

 sa[lens-1]%=10< span style="color: #000000;">;

}

}

void chu(ll k)

{

 int j=0,x=0;

 memset(now,0,sizeof(now));

 for(int i=lens;i>= 1;i--)

 {

 j++;

 x=x*10+sa[i];

 now[j]=x/k;

 x=x-now[j]*k;

}

 for(int i=1;i<=j/2;i++) //Because the high-precision except single-precision is from the first position to the high position, so you need to reverse now, pay attention to i<=j/2, not i <=j

 {

 int tmp=now[i];

 now[i]=now[j-i+1];

 now[j-i+1]=tmp;

}

 while(now[j]==0&&j >1)

 j--;

 lenn=j;

}

void max_()//Compare

{

 if(lenn>lenm)

 {

 for(int i=lenn;i>= 1;i--)

 ma[i]=now[i];

 lenm=lenn;//Don’t miss it

 return;

}

 if(lennreturn;

 for(int i=lenn;i>= 1;i--)

 {

 if(now[i]<ma[i])

 break;

 if(now[i]>ma[i])// Find the first bit smaller than the corresponding bit of ma

 {

 for(int j=i;j>= 1;j--)

 {

 ma[j]=now[j];

}

 return;

}

}

 return;

}

int main()

{

 sa[1]=1;

 n=read();ren[0].a=read();ren[0].b=read();

 for(int i=1;i<=n;i++)

 ren[i].a=read(),ren[i].b=read();

 sort(ren+1,ren+1+< span style="color: #000000;">n,cmp);

 for(int i=1;i<=n;i++)

 {

 cheng(ren[i-1].a);

 chu(ren[i].b);

 max_();

}

 for(int i=lenm;i>= 1;i--)

 printf("%lld",ma[i]);

}

#include

#define ll long long

using namespace std;

ll read()

{

 char ch=getchar();

 ll x=0;bool f=0;

 while(ch<'0'||ch>' 9')

 {

 if(ch=='-')f=1 ;

 ch=getchar();

}

 while(ch>='0'&&ch<=' 9')

 {

 x=(x<<3)+(x<<1 )+(ch^48);

 ch=getchar();

}

 return f?-x:x;

}

struct rr

{

 ll a,b;

}ren[1009];

ll n,aa,bb,sa[7009],now[ 7009],ma[7009],lenm=1,lens= 1,lenn=1; //sa records the product of the numbers on the left hand of the ministers, now records the current minister’s gold coins, and ma records the maximum value

bool cmp(rr t,rr w)

{

 return t.a*t.bw.b;

}

//The following is high-precision

void cheng(ll k)//High precision multiplication

{

 sa[1]*=k;

 for(int i=2;i<=lens;i++)

 {

 sa[i]=sa[i-1]/10< /span>+sa[i]*k;

 sa[i-1]%=10< span style="color: #000000;">;

}

 while(sa[lens]>=10< span style="color: #000000;">)

 {

 lens++;

 sa[lens]=sa[lens-1]/10< /span>;

 sa[lens-1]%=10< span style="color: #000000;">;

}

}

void chu(ll k)

{

 int j=0,x=0;

 memset(now,0,sizeof(now));

 for(int i=lens;i>= 1;i--)

 {

 j++;

 x=x*10+sa[i];

 now[j]=x/k;

 x=x-now[j]*k;

}

 for(int i=1;i<=j/2;i++) //Because the high-precision except single-precision is from the first position to the high position, so you need to reverse now, pay attention to i<=j/2, not i <=j

 {

 int tmp=now[i];

 now[i]=now[j-i+1];

 now[j-i+1]=tmp;

}

 while(now[j]==0&&j >1)

 j--;

 lenn=j;

}

void max_()//Compare

{

 if(lenn>lenm)

 {

 for(int i=lenn;i>= 1;i--)

 ma[i]=now[i];

 lenm=lenn;//Don’t miss it

 return;

}

 if(lennreturn;

 for(int i=lenn;i>= 1;i--)

 {

 if(now[i]<ma[i])

 break;

 if(now[i]>ma[i])// Find the first bit smaller than the corresponding bit of ma

 {

 for(int j=i;j>= 1;j--)

 {

 ma[j]=now[j];

}

 return;

}

}

 return;

}

int main()

{

 sa[1]=1;

 n=read();ren[0].a=read();ren[0].b=read();

 for(int i=1;i<=n;i++)

 ren[i].a=read(),ren[i].b=read();

 sort(ren+1,ren+1+< span style="color: #000000;">n,cmp);

 for(int i=1;i<=n;i++)

 {

 cheng(ren[i-1].a);

 chu(ren[i].b);

 max_();

}

 for(int i=lenm;i>= 1;i--)

 printf("%lld",ma[i]);

}