# Game mathematical derivation AC code (high precision and low precision multiplication and division comparison) + 60 code (long long) + 20 point code (Full Permutation + deep search DFS)

2020-11-08 07:14:08

NOIP 2012 Improvement group The rematch The first day The second question is King's game game   Mathematical derivation AC Code ( High precision   Low precision ride except Compare )+60 Code (long long)+20 Code division ( Full Permutation + Deep search dfs)

For the general catalogue, please refer to ：NOIP Improvement group The rematch test questions Catalog Xinao Calendar year

The mathematical derivation is as follows ：

We analyze the two points behind the king

The queue might look like this ：

* Left Right
king: a0​ b0​
p1 a1​ b1​
p2 a2​ b2​

So we can calculate that ans1​=max(a0/b1,a0*a1/b2​​)

The queue could be like this

* Left Right
king: a0​ b0​
p2 a2​ b2​
p1 a1​ b1​

So we can calculate that ans2​=max(a0/b2,a0*a2/b1​​)

consider ans1 The optimal , that ans1<ans2,

(ans1 Medium )a0/b1<(ans2 Medium )a0*a2/b1

(ans1 Medium )a0*a1/b2>(ans2 Medium )a0/b2

Make sure that ans1<ans2 It must be true , must (ans1 Medium )a0*a1/b2<(ans2 Medium )a0*a2/b1

namely a1/b2<a2/b1

namely a1*b1<a2*b2

namely , Press a*b Sort from small to large , It can be guaranteed that it is the optimal solution to the problem .

In terms of success rate , It's still highly recommended 60 Code division .

Provide a set of test data

`````` Input ：
5
9999 1
9999   1
9999 2
9999 3
9999 4
9999 5
Output ：
19990001999800009999``````

1.AC Code ( High precision   Low precision ride except Compare )

``````#include <bits/stdc++.h>
#define maxn 1010
#define BASE 10000
using namespace std;
int n,aa[maxn],an,bb[maxn],bn,cc[maxn],cn;
struct node{
int a,b,c;
}q[maxn];
int cmp(node a,node b){
return a.c<b.c;
}
void mul(int x){// High precision * Low precision
int i;
for(i=1;i<=an;i++)
aa[i]=aa[i]*x;
for(i=1;i<=an;i++){
aa[i+1]+=aa[i]/BASE;
aa[i]%=BASE;
}
//if(aa[an+1])an++; You can also write this sentence , But I don't think it's right
while(aa[an+1])an++,aa[an+1]+=aa[an]/BASE,aa[an]%=BASE;
}
void div(int x){// High precision / Low precision
int i,yu;
yu=0;
for(i=an;i>=1;i--){
bb[i]=(aa[i]+yu*BASE)/x;
yu=(aa[i]+yu*BASE)%x;
}
bn=an;
}
int compare(){
if(bn>cn)return 1;//bb>cc
if(bn<cn)return -1;//bb<cc
for(int i=bn;i>=1;i--)//bb==cc
if(bb[i]>cc[i])return 1;//bb>cc
else if(bb[i]<cc[i])return -1;//bb<cc
return 0;//bb==cc
}
int main(){
int i,j;
scanf("%d",&n);
for(i=0;i<=n;i++)scanf("%d%d",&q[i].a,&q[i].b),q[i].c=q[i].a*q[i].b;
sort(q+1,q+1+n,cmp);
aa[1]=1,an=1;
cc[1]=q[0].a/q[1].b,cn=1;
for(i=1;i<=n;i++){
mul(q[i-1].a);
div(q[i].b);
if(compare()==1){
cn=bn;
for(j=bn;j>=1;j--)cc[j]=bb[j];
}
}
printf("%d",cc[cn]);
for(i=cn-1;i>=1;i--)printf("%04d",cc[i]);
return 0;
}``````

2.60 Code (long long)

``````#include <bits/stdc++.h>
#define LL long long
#define maxn 1100
using namespace std;
struct node{
LL a,b,c;
}q[maxn];
int cmp(node a,node b){
return a.c<b.c;
}
LL mx,a=1;
int main(){
int n,i;
scanf("%d",&n);
for(i=0;i<=n;i++){
scanf("%d%d",&q[i].a,&q[i].b);
q[i].c=q[i].a*q[i].b;
}
sort(q+1,q+1+n,cmp);
for(i=1;i<=n;i++)
a*=q[i-1].a,mx=max(mx,a/q[i].b);
printf("%lld\n",mx);
return 0;
}``````

3.20 Code division ( Full Permutation + Deep search dfs)

20 Code division ( Full Permutation + Deep search dfs) as follows ：

``````#include <bits/stdc++.h>
using namespace std;
int a[15],b[15],c[15],vis[15],n,mn=2000000000;
void dfs(int step){
int i;
if(step==n+1){
int j,aa=1,mx=0;
for(j=1;j<=n;j++){
aa=aa*a[c[j-1]];
mx=max(mx,aa/b[c[j]]);
}
mn=min(mx,mn);
return;
}
for(i=1;i<=n;i++)
if(!vis[i]){
vis[i]=1;
c[step]=i;
dfs(step+1);
vis[i]=0;
}
}
int main(){
int i;
scanf("%d",&n);
for(i=0;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
dfs(1);
printf("%d\n",mn);
return 0;
} ``````