广泛组第二题,比例简化

by admin on 2019年8月22日

洛谷P2118 比例简化,洛谷p2118简化

P2118 比例简化

标题陈述

在应酬媒体上,日常拜望到针对某三个观念同意与否的民意考察以及结果。举个例子,对某一视角代表帮衬的有1498人,反对的有 902人,那么扶助与反对的比重能够省略的记为1498:902。

然而,如若把考察结果就以这种艺术展现出来,大多数人自然不会白璧微瑕。因为那个比例的数值太大,难以一眼看出它们的关系。对于地方那个例子,借使把比例记为5:3,纵然与忠实结果有断定的测量误差,但依然能够相比较标准地反映考察结果,同一时间也显示比较直观。

现给出辅助人口A,反对人数B,以及三个上限L,请你将A比B化简为A’比B’,要求在A’和B’均不高于L且A’和B’互质(多个整数的最大合同数是1)的前提下,A’/B’
≥ A/B且A’/B’ – A/B的值尽大概小。

(本标题为二〇一六NOIP普遍T2)

描述

在应酬媒体上,平日拜会到针对某二个观念同意与否的民意考查以及结果。举个例子,对某
一意见代表支持的有 1498 人,反对的有 902
人,那么协助与反对的比重可以归纳的记为1498:902。

可是,假设把调查结果就以这种情势表现出来,大好些个人自然不会大失所望。因为那些比例的数值太大,难以一眼看出它们的关系。对于地方这么些例子,假设把比例记为
5:3,纵然与
真实结果有一定的固有误差,但依旧能够相比较标准地显示考查结果,同不日常间也体现相比较直观。

现给出匡助人口 A,反对人数 B,以及叁个上限 L,请你将 A 比 B 化简为 A’比
B’,须要在 A’和 B’均不高于 L 且 A’和 B’互质(三个整数的最大左券数是
1)的前提下,A’/B’ ≥ A/B 且 A’/B’ – A/B 的值尽大概小。

标题呈报

在应酬媒体上,平常会看到针对某两个思想同意与否的民调以及结果。比如,对某一视角代表扶助的有1497个人,反对的有 902人,那么帮忙与反对的比重能够差没有多少的记为1498:902。

唯独,若是把调查结果就以这种方法表现出来,大好些个人必然不会适得其反。因为那么些比例的数值太大,难以一眼看出它们的关系。对于地点那些例子,如若把比例记为5:3,固然与真正结果有早晚的误差,但还能够相比规范地反映考察结果,同时也体现相比直观。

现给出帮助人口A,反对人数B,以及叁个上限L,请您将A比B化简为A’比B’,要求在A’和B’均不高于L且A’和B’互质(四个整数的最大公约数是1)的前提下,A’/B’
≥ A/B且A’/B’ – A/B的值尽恐怕小。

(本标题为贰零壹伍NOIP普遍T2)

难题叙述

在张罗媒体上,常常会看出针对某一个意见同意与否的民调以及结果。举个例子,对某一眼光表示帮忙的有14100人,反对的有 902人,那么帮助与反对的比例能够轻松的记为1498:902。

广泛组第二题,比例简化。可是,假诺把考查结果就以这种措施表现出来,大好多人明确不会满足。因为那几个比重的数值太大,难以一眼看出它们的涉嫌。对于地点这些事例,如若把比例记为5:3,就算与诚实结果有自然的零值误差,但还能够相比准确地展现考察结果,同期也出示比较直观。

现给出扶助人口A,反对人数B,以及一个上限L,请你将A比B化简为A’比B’,必要在A’和B’均不超越L且A’和B’互质(三个整数的最大公约数是1)的前提下,A’/B’
≥ A/B且A’/B’ – A/B的值尽只怕小。

(本标题为二〇一四NOIP普遍T2)

输入输出格式

广泛组第二题,比例简化。输入格式:

输入共一行,包涵四个整数A,B,L,每多少个整数之间用一个空格隔开分离,分别表示支持人口、反对人数以及上限。

出口格式:

出口共一行,包蕴八个整数A’,B’,中间用一个空格隔开分离,表示化简后的百分比。

格式

bf88必发唯一官网,输入输出格式

输入格式:

 

输入共一行,包涵几个整数A,B,L,每八个整数之间用一个空格隔离,分别代表协助人口、反对人数以及上限。

 

输出格式:

 

出口共一行,包涵三个整数A’,B’,中间用四个空格隔绝,表示化简后的比重。

 

输入输出格式

输入格式:

 

输入共一行,包涵多个整数A,B,L,每三个整数之间用五个空格隔开分离,分别代表接济人口、反对人数以及上限。

 

输出格式:

 

出口共一行,包括七个整数A’,B’,中间用一个空格隔断,表示化简后的比例。

 

输入输出样例

输入样例#1:复制

1498 902 10

输出样例#1:复制

5 3

输入格式

输入共一行,包蕴多少个整数
A,B,L,每四个整数之间用二个空格隔离,分别表示辅助人口、反对人数以及上限。

输入输出样例

输入样例#1: 复制

1498 902 10

出口样例#1: 复制

5 3

输入输出样例

输入样例#1: 复制

1498 902 10

输出样例#1: 复制

5 3

说明

对于100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤
L。

理当如此感觉是如何奥密的数学标题

不过看了数量之后发现L相当小,所以平昔暴力枚举就可以

#include<cstdio>#include<algorithm>const int MAXN=3*1e6+10;using namespace std;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    int x=read(),y=read(),L=read();    int ansx=233333,ansy=1;    for(int i=1;i<=L;i++)        for(int j=1;j<=L;j++)            if( (double)i/j>=(double)x/y &&  (double)i/j < (double) ansx/ansy  )                ansx=i,ansy=j;    printf("%d %d",ansx,ansy);    return 0;}

出口格式

输出共一行,包含四个整数 A’,B’,中间用三个空格隔离,表示化简后的比例。

说明

对于100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤
L。

 

 

当然感觉是何等奥密的数学难点

然而看了多少之后发掘L相当小,所以直接暴力枚举就能够

 

#include<cstdio>
#include<algorithm>
const int MAXN=3*1e6+10;
using namespace std;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    int x=read(),y=read(),L=read();
    int ansx=233333,ansy=1;
    for(int i=1;i<=L;i++)
        for(int j=1;j<=L;j++)
            if( (double)i/j>=(double)x/y &&  (double)i/j < (double) ansx/ansy  )
                ansx=i,ansy=j;
    printf("%d %d",ansx,ansy);
    return 0;
}

 

比例简化,洛谷p2118简化 标题描述
在交际媒体上,平日拜见到针对某三个观点同意与否的民意考察以及结果。比方,对某一思想表…

说明

对于100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤
L。

 枚举决断

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int a,b,A,B,L;
double ans1,ans2,minn;
int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main()
{
    A=read(),B=read(),L=read();
    ans1=1.0*A/B;minn=99999;
    for(int i=1;i<=L;i++)
     for(int j=1;j<=L;j++)
     {
         ans2=1.0*i/j;
         if(ans2<ans1) break;
        if(ans2>=ans1&&ans2-ans1<minn) 
         a=i,b=j,minn=ans2-ans1;
      } 
    printf("%d %d",a,b);
    return 0;
}

 

样例1

样例输入1

1498 902 10

样例输出1

5 3

限制

对于 100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B
≤ L。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图