比例简化
说明
在社交媒体上,经常会看到针对某一个观点同意与否的民意调查以及结果。例如,对某一观点表示支持的有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’,中间用一个空格隔开,表示化简后的比例。
样例
提示
【数据说明】
对于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,依次表示在横坐标位置 0∼n−1 上玩家点击屏幕后,小鸟在下一位置上升的高度 x,以及在这个位置上玩家不点击屏幕时,小鸟在下一位置下降的高度 y。
接下来 k 行,每行 3 个整数 p,l,h,每两个整数之间用一个空格隔开。每行表示一个管道,其中 p 表示管道的横坐标,l 表示此管道缝隙的下边沿高度,h 表示管道缝隙上边沿的高度(输入数据保证 p 各不相同,但不保证按照大小顺序给出)。
输出格式
共两行。
第一行,包含一个整数,如果可以成功完成游戏,则输出 1,否则输出 0。
第二行,包含一个整数,如果第一行为 1,则输出成功完成游戏需要最少点击屏幕数,否则,输出小鸟最多可以通过多少个管道缝隙。
样例
提示
【输入输出样例说明】
如下图所示,蓝色直线表示小鸟的飞行轨迹,红色直线表示管道。
【数据范围】
对于 30% 的数据:5≤n≤10,5≤m≤10,k=0,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 50% 的数据:5≤n≤20,5≤m≤10,保证存在一组最优解使得同一单位时间最多点击屏幕 3 次;
对于 70% 的数据:5≤n≤1000,5≤m≤100;
对于 100% 的数据:5≤n≤10000,5≤m≤1000,0≤k<n,0<x,y<m,0<p<n,0≤l<h≤m,l+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;
}