NOIP2014普及组,提高组 比例简化 飞扬的小鸟 答案

比例简化

说明

在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有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’,中间用一个空格隔开,表示化简后的比例。

样例

输入数据 1

1498 902 10
Copy

输出数据 1

5 3
Copy

提示

【数据说明】
对于100%的数据,1 ≤ A ≤ 1,000,000,1 ≤ B ≤ 1,000,000,1 ≤ L ≤ 100,A/B ≤ L。
【来源】

NOIP2014普及组复赛第2题。

#include<bits/stdc++.h>
using namespace std;
int A,B,L,a,b;
int isz(int x,int y) {//辗转相除,画一画就明白了if(y==0)return x;return isz(y,x%y);
}
int main() {cin>>A>>B>>L;a=L;b=1;//定为最大值for(int i=1; i<=L; i++)//L小于100穷举for(int j=1; j<=L; j++) {//求A/B<=i/j<=a/bbool bz=(isz(i,j)==1);//判断互质bool bd=((A*j)<=(B*i));//判断是否大于(解释:原来是A/b<=i/j但会有精度问题,等式性质转换上去)bool bj=((a*j)>(b*i));//是否更接近A/B本为a/b>i/j但会有精度问题,等式性质转换上去//cout<<"i= "<<i<<" j= "<< j<<" "<<bz<<" "<<bd<<" "<<bj<<endl;if(bz==1&&bd==1&&bj==1)a=i,b=j;//dev性质&&情况默认是0,大服}cout<<a<<" "<<b;return 0;
}

[NOIP2014 提高组] 飞扬的小鸟

说明

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度,让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话,便宣告失败。

为了简化问题,我们对游戏规则进行了简化和改编:

游戏界面是一个长为 n,高为 m 的二维平面,其中有 k 个管道(忽略管道的宽度)。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发,到达游戏界面最右边时,游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 1,竖直移动的距离由玩家控制。如果点击屏幕,小鸟就会上升一定高度 x,每个单位时间可以点击多次,效果叠加;如果不点击屏幕,小鸟就会下降一定高度 y。小鸟位于横坐标方向不同位置时,上升的高度 x 和下降的高度 y 可能互不相同。

小鸟高度等于 0 或者小鸟碰到管道时,游戏失败。小鸟高度为 m 时,无法再上升。

现在,请你判断是否可以完成游戏。如果可以,输出最少点击屏幕数;否则,输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 1 行有 3 个整数 n,m,k,分别表示游戏界面的长度,高度和水管的数量,每两个整数之间用一个空格隔开;

接下来的 n 行,每行 2 个用一个空格隔开的整数 x 和 y,依次表示在横坐标位置 0n1 上玩家点击屏幕后,小鸟在下一位置上升的高度 x,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度 y

接下来 k 行,每行 3 个整数 p,l,h,每两个整数之间用一个空格隔开。每行表示一个管道,其中 p 表示管道的横坐标,l 表示此管道缝隙的下边沿高度,h 表示管道缝隙上边沿的高度(输入数据保证 p 各不相同,但不保证按照大小顺序给出)。

输出格式

共两行。

第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0

第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。

样例

输入数据 1

10 10 6 
3 9  
9 9  
1 2  
1 3  
1 2  
1 1  
2 1  
2 1  
1 6  
2 2  
1 2 7 
5 1 5 
6 3 5 
7 5 8 
8 7 9 
9 1 3 
Copy

输出数据 1

1
6
Copy

提示

【输入输出样例说明】

如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。





【数据范围】

对于 30% 的数据:5n10,5m10,k=0,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;

对于 50% 的数据:5n20,5m10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;

对于 70% 的数据:5n1000,5m100

对于 100% 的数据:5n100005m10000k<n0<x,y<m0<p<n0l<hml+1<h

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define gc(a) a=getchar()
#define pc(a) putchar(a)
ll read(){char c;ll x=0;bool flag=0;gc(c);while(c<'0'||c>'9'){if(c=='-') flag=1;gc(c);}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48),gc(c);}return flag?-x:x;
}
void pr(ll x){if(x<0){x=-x;pc('-');}if(x>9) pr(x/10);pc(x%10+48);
}
//-------快读------
#define inf 0x3f3f3f3f
const ll maxn=10005;
const ll maxm=10005;
struct node
{ll id,h,l;bool operator <(const node &a) const{return id<a.id;}
}o[maxn];
ll x[maxn],y[maxn],dp[2][maxm],n,m,k,cnt=1,ans;
int main()
{//memset(dp,inf,sizeof(dp));//两个被遗忘的初始化之一qwqn=read(),m=read(),k=read();for(int i=1;i<=n;i++)x[i]=read(),y[i]=read();for(int i=1;i<=k;i++)o[i].id=read(),o[i].l=read(),o[i].h=read();sort(o+1,o+k+1);//管道id排序!//for(int i=1;i<=m;i++)//dp[0][i]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++)//注意要初始化!dp[i%2][j]=inf;for(int j=x[i]+1;j<=x[i]+m;j++)//p=1,完全背包dp[i%2][j]=min(dp[i%2^1][j-x[i]]+1,dp[i%2][j-x[i]]+1);for(int j=m+1;j<=x[i]+m;j++)//比m大的都是mdp[i%2][m]=min(dp[i%2][m],dp[i%2][j]);for(int j=1;j<=m-y[i];j++)//p=0,01背包dp[i%2][j]=min(dp[i%2][j],dp[i%2^1][j+y[i]]);if(i==o[cnt].id)//如果这个地方有管道{ans=inf;//主要每次都要初始化一次!for(int j=0;j<=o[cnt].l;j++)dp[i%2][j]=inf;for(int j=o[cnt].h;j<=m;j++)dp[i%2][j]=inf;for(int j=1;j<=m;j++)//寻找是否可以通过ans=min(dp[i%2][j],ans);if(ans==inf){pr(0);pc('\n');pr(cnt-1);return 0;}cnt++;}}ans=inf;//注意要初始化!for(int j=1;j<=m;j++)ans=min(dp[n%2][j],ans);pr(1);pc('\n');pr(ans);return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/98976.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

迈向未来的大门:人脸识别技术的突破与应用

迈向未来的大门&#xff1a;人脸识别技术的突破与应用 人脸识别&#xff1a;人脸识别的工作流程人脸识别的作用人脸识别技术的突破与应用 在深度学习人脸识别之前我们要先知道人脸识别是什么。 人脸识别&#xff1a; 人脸识别是一种基于人脸图像或视频进行身份验证或识别的技术…

【数据挖掘】使用 Python 分析公共数据【01/10】

一、说明 本文讨论了如何使用 Python 使用 Pandas 库分析官方 COVID-19 病例数据。您将看到如何从实际数据集中收集见解&#xff0c;发现乍一看可能不那么明显的信息。特别是&#xff0c;本文中提供的示例说明了如何获取有关疾病在不同国家/地区传播速度的信息。 二、准备您的…

【Linux】Centos安装 mariadb 并授权远程登陆

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; &#x1f40b; 希望大家多多支…

无涯教程-Perl - splice函数

描述 此函数从LENGTH元素的OFFSET元素中删除ARRAY元素,如果指定,则用LIST替换删除的元素。如果省略LENGTH,则从OFFSET开始删除所有内容。 语法 以下是此函数的简单语法- splice ARRAY, OFFSET, LENGTH, LISTsplice ARRAY, OFFSET, LENGTHsplice ARRAY, OFFSET返回值 该函数…

react实现对数组做增删改操作自定义hook

需求 实现对数组的增删改操作。 实现 import { useState } from react;const useArray (currList) > {const [list, setList] useState(currList);// 增const addItem (item) > {setList([...list, item]);};// 删const removeItem (idx) > {const _arr [...l…

容斥原理 博弈论(多种Nim游戏解法)

目录 容斥原理容斥原理的简介能被整除的数&#xff08;典型例题&#xff09;实现思路代码实现扩展&#xff1a;用DPS实现 博弈论博弈论中的相关性质博弈论的相关结论先手必败必胜的证明Nim游戏&#xff08;典型例题&#xff09;代码实现 台阶-Nim游戏&#xff08;典型例题&…

使用ChatGPT进行创意写作的缺点

Open AI警告ChatGPT的使用者要明白此工具的局限性&#xff0c;更不应完全依赖。作为一位创作者&#xff0c;这一点非常重要&#xff0c;应尽可能地避免让版权问题或不必要的文体问题出现在自己的作品中。[1] 毕竟使用ChatGPT进行创意写作目前还有以下种种局限或缺点[2]&#xf…

CSS自学框架之动画

这一节&#xff0c;自学CSS动画。主要学习了淡入淡出、淡入缩放、缩放、移动、旋转动画效果。先看一下成果。 优雅的过渡动画&#xff0c;为你的页面添加另一份趣味&#xff01; 在你的选择器里插入 animation 属性&#xff0c;并添加框架内置的 keyframes 即可实现&#xff0…

爬虫ip带你探索无限可能

各位程序猿大佬们&#xff0c;今天我要为大家带来一个备受关注的话题&#xff1a;爬虫ip的应用范围&#xff01;你可能会好奇&#xff0c;什么是爬虫ip&#xff1f;它在我们的日常生活中有哪些神奇的应用呢&#xff1f;让我们一起来揭开这个神秘的面纱&#xff0c;探索无限可能…

分布式链路追踪——Dapper, a Large-Scale Distributed Systems Tracing Infrastructure

要解决的问题 如何记录请求经过多个分布式服务的信息&#xff0c;以便分析问题所在&#xff1f;如何保证这些信息得到完整的追踪&#xff1f;如何尽可能不影响服务性能&#xff1f; 追踪 当用户请求到达前端A&#xff0c;将会发送rpc请求给中间层B、C&#xff1b;B可以立刻作…

[git]gitpush提示remote: Permission to xxx.git denied to xxx

错误原因&#xff1a;git客户端你先前登录过其他用户导致&#xff0c;你用另一个账号push的时候用的先前用户 解决方法&#xff1a;删除先前用户用你想push用户重新登录 解决步骤&#xff1a; 打开控制面板-->查看方式选择大图标-->然后打开凭据管理器 找到github相关…

Redis——Redis.conf详解+Redis持久化(RDB和AOF)+Redis订阅发布

配置文件 redis启动时通过配置文件启动 原生配置文件全文在网上随便搜索一下就能找到了。 单位 配置文件 unit单位 对大小写不敏感 包含 类比import&#xff0c;将其他的配置文件引入 网络 bind 127.0.0.1 // 绑定ip protected-mode yes //是否受保护 po…

SAP ABAPG开发屏幕自动生成日期的搜索帮助

代码如下&#xff1a; REPORT z_jason_test_f4 . TABLES: s031. PARAMETER p_spmon TYPE spmon DEFAULT sy-datum0(6) OBLIGATORY. SELECT-OPTIONS s_spmon FOR s031-spmon DEFAULT sy-datum0(6) OBLIGATORY. AT SELECTION-SCREEN ON VALUE-REQUEST…

知网G4期刊《高考》简介及投稿要求

知网G4期刊《高考》简介及投稿要求 一、《高考》期刊简介&#xff1a; 主管单位&#xff1a;长春市委宣传部 主办单位&#xff1a;长春出版社 国内刊号22-1372/G4 国际刊号1673-6265 代号12-240 编辑单位&#xff1a;《高考》杂志社 出版周期&#xff1a;旬刊 类 …

无涯教程-Perl - setnetent函数

描述 该函数应在第一次调用getnetent之前调用。 STAYOPEN参数是可选的,在大多数系统上未使用。当getnetent()从网络数据库的下一行检索信息时,setnetent会将枚举设置(或重置)为主机条目集的开头。 语法 以下是此函数的简单语法- setnetent STAYOPEN返回值 此函数不返回任何…

【vue3】对axios进行封装,方便更改路由并且可以改成局域网ip访问(附代码)

对axios封装是在main.js里面进行封装&#xff0c;因为main.js是一个vue项目的入口 步骤&#xff1a; 在1处创建一个axios实例为http&#xff0c;baseURL是基础地址&#xff08;根据自己的需求写&#xff09;&#xff0c;写了这个在vue界面调用后端接口时只用在post请求处写路由…

【前端】vscode javascript 代码片段失效问题解决

1. 文件--首选项--用户代码片段-vue.json : 添加 // { // // Place your global snippets here. Each snippet is defined under a snippet name and has a scope, prefix, body and // // description. Add comma separated ids of the languages where the snippet is app…

探索Perfetto:开源性能追踪工具的未来之光

探索Perfetto&#xff1a;开源性能追踪工具的未来之光 1. 引言 A. 介绍Perfetto的背景和作用 随着移动应用、桌面软件和嵌入式系统的不断发展&#xff0c;软件性能优化变得愈发重要。在这个背景下&#xff0c;Perfetto作为一款开源性能追踪工具&#xff0c;日益引起了开发者…

GraphQL strawberry的使用回顾和体会

GraphQL vs RESTful 简单来说GraphQL 比起 RESTful 集成额外一些功能 出入参校验、序列化 (简化后端编程)自由可选的返回数据字段 (简化一些多余接口开发和沟通联调成本) 这些都是优点了。 开发效率在项目初期是很重要的&#xff0c;需要快速原型化。 但是后期稳定后&#…

Web 拦截器-interceptor

拦截器是一种动态拦截方法调用的机制&#xff0c;类似于过滤器&#xff0c;是Spring框架提出的&#xff0c;用来动态拦截控制器方法的执行。 其作用是拦截请求&#xff0c;在指定方法调用前后&#xff0c;根据业务执行预设代码。 实现步骤 1.定义拦截器&#xff0c;实现Handl…