noip2014普及组 比例简化

简介: 题目描述 在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有1498 人,反对的有 902人,那么赞同与反对的比例可以简单的记为1498:902。 不过,如果把调查结果就以这种方式呈现出来,大多数人肯定不会满意。

题目描述

在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有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的值尽可能小。

输入格式:
输入共一行,包含三个整数A,B,L,每两个整数之间用一个空格隔开,分别表示支持人数、反对人数以及上限。
输出格式:
输出共一行,包含两个整数A’,B’,中间用一个空格隔开,表示化简后的比例。

输入样例:
1498 902 10
输出样例:
5 3

说明

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

 

解题思路:

在1到L范围内分别枚举A‘和B’的组合,然后逐一检验是否所要找的解即可。注意:输入的数据是整数,题目判断大小关系的地方多数是用浮点数判断,要加以转换。

代码:

 1 #include<stdio.h>
 2 int gcd(int a,int b);
 3 int main()
 4 {
 5     int a,b,L;
 6     int i,j;
 7     int mina,minb;
 8     double  min,tt,t;
 9     //freopen("ratio.in","r",stdin);
10     //freopen("ratio.ans","w",stdout);
11     scanf("%d%d%d",&a,&b,&L);
12     t=a*1.0/b;
13     min=200;
14     for(i=1;i<=L;i++)
15     {
16         for(j=1;j<=L;j++)
17         {
18             tt=i*1.0/j;
19             if(tt>=t&&tt<min&&gcd(i,j)==1)
20             {
21                 min=tt;
22                 mina=i;
23                 minb=j;
24             }
25         }
26     }
27     printf("%d %d\n",mina,minb);
28     return 0;
29 }
30 int gcd(int a,int b)
31 {
32     int t;
33     if(a<b)
34     {
35         t=a;a=b;b=t;
36     }
37     /*if(b==0) return a;
38     else return gcd(b,a%b);*/
39     t=a%b;
40     while(t!=0)
41     {
42         a=b;
43         b=t;
44         t=a%b;
45     }
46     return b;
47 }
View Code

 

相关文章
|
边缘计算 安全 物联网
【网卡可能存在的后门】以太网控制器IP核中的潜在安全威胁与自主化思考
本文探讨了2011年作者在FPGA上开发以太网控制器时发现的一个潜在后门。该后门利用以太网协议的特性,通过特定数据触发网卡进入死亡模式,持续产生中断,导致设备无法正常关闭,对无操作系统的嵌入式设备构成威胁。尽管有操作系统的设备受此影响较小,但WiFi网卡可能因广播攻击而受影响。作者强调网卡安全的重要性,认为其比CPU更需自主化,并指出防止CPU后门的关键在于确保驱动和代码无后门,而非仅仅自主化CPU。
|
IDE Unix 开发工具
Solaris中查看硬件信息常用命令
Solaris中查看硬件信息常用命令
326 1
|
运维 监控 Ubuntu
Python实现ubuntu系统进程内存监控
Python实现ubuntu系统进程内存监控
152 1
|
人工智能 安全 API
发现一款提高工作效率的利器——ONLYOFFICE办公软件
发现一款提高工作效率的利器——ONLYOFFICE办公软件
495 1
|
存储 前端开发 JavaScript
Retool 是什么,怎么样? Retool 低代码工具测评
Retool 是面向企业的低代码开发平台。使用 Retool 可快速搭建后台管理工具,比如快速构建 admin 后台管理、销售 ERP、客户 CRM、数据分析看板、amazon 云端文件上传管理等基于数据库或 API 的企业工具。 新事物刚出现,没亲身体验前,总是很难理解。我们总会把新事物与我们已认知的东西来做对比,有人说 Retool 是帮你配置好的 Vue & React 、是可视化拖拽编程平台、是在线前端生成器(并不是)。这些说法都只描述了 Retool 很小的一个点,Retool 是新一代低代码开发平台,是程序员的新效率工具,是历史上不曾有的新工具,拿旧地图看新世界总会有很大偏差,建
1206 0
|
SQL 分布式计算 关系型数据库
来自DBMS大牛分享 - MapReduce: 一个巨大的倒退
前言 2011年历史的大数据&数据库论 databasecolumn 的数据库大牛们(其中包括PostgreSQL的最初伯克利领导:Michael Stonebraker)最近写了一篇评论当前如日中天的MapReduce 技术的文章,引发剧烈的讨论。我抽空在这儿翻译一些,一起学习。 译者注:这种 Tanenbaum vs. Linus 式的讨论自然会导致非常热烈的争辩。但是老实说,从 Tanenbaum vs. Linus 的辩论历史发展来看,Linux是越来越多地学习并以不同方式应用了 Tanenbaum 等 OS 研究者的经验(而不是背弃); 所以 MapReduce vs. DBMS
423 0
|
人工智能 索引
洛谷P1005 [NOIP2007 提高组] 矩阵取数游戏
洛谷P1005 [NOIP2007 提高组] 矩阵取数游戏
|
Shell Linux 开发工具
linux ulimit 调优
概要:linux系统默认open files数目为1024, 有时应用程序会报Too many open files的错误,是因为open files 数目不够。这就需要修改ulimit和file-max。
4743 0
|
负载均衡 NoSQL 算法
初探-Discovery开源框架-gateway灰度方案
Discovery 框架比较成熟的开源框架,可以参考里面实现方案。Discovery实现了Eureka、Nacos等等注册中心灰度,以及通过redis、Nacos、Etcd来实现配置中心(为了网关动态配置)还有类似apm全链路变量传递功能,以及改写fegin、resttemplate负载均衡
1046 0
初探-Discovery开源框架-gateway灰度方案
|
存储 数据格式 Python
再见 CSV,速度提升 150 倍!
我的原计划是输出100个,目前来看可能最终不一定会到100个,但每个都是超实用且平时经常会遇到的问题。pandas的用法太多了,如果不熟练,平时是需要经常网上查找的,这个系列可以帮助大家快速回忆用法。
再见 CSV,速度提升 150 倍!