首页 > 代码库 > Ural 1011. Conductors
Ural 1011. Conductors
1011. Conductors
Time limit: 2.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Background
Everyone making translations from English to Russian knows an English phrase "Naked conductor runs along the bus". It has two very different meanings.
Problem
Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more than P% conductors and less than Q% conductors of all citizens of Ekaterinburg. Your task is to determine a minimal possible number of Ekaterinburg citizens. By percentage, we know that there are more than P% conductors and less than Q% conductors of all Russian citizens in this city
Input
Two numbers P,Q such that 0.01 ≤ P, Q ≤ 99.99. Numbers are given with 2 digits precision. These numbers are separated by some spaces or "end of line" symbols.
Output
The minimal number of Ekaterinburg citizens.
Sample
| input | output |
|---|---|
1314.1 | 15 |
Notes
If there are 15 citizens and 2 conductors among them in Ekaterinburg, then there are 13 1/3 % conductors of all citizens.
Problem Source: USU Championship 1997
来源： <http://acm.timus.ru/problem.aspx?space=1&num=1011>
初步想法：从 1 开始遍历，当 n/p 和 n/q 之间存在整数，则所夹最小整数就是所求结果了。但下面的程序 floor 、 ceil 、 fabs 太耗时间了，虽然在自己电脑上都是秒出，但在评测机上达到了 2s 多，华丽丽 TLE。
#include <stdio.h>#include <math.h>#include <stdlib.h>int main(){ long n=0; double p,q,tp,tq; scanf("%lf%lf",&p,&q); p/=100.0;q/=100.0; while(++n){ tp=floor(n/p); tq=ceil(n/q); if(fabs(tq-tp)<1E-2) break; //if(tp>tq) break; //if(tp<tq) continue; } printf("%.0f",tp); return 0;}
?改进：整个算法就循环最耗时间了，有针对性地修改即可，直接 long 强转只保留整数部分，于是考虑：
? n/p n/q 强转 -> tp tq
2.x 1.y 2 1
3.x 1.y 3 1
2.x 2.y 2 2
可以看到上面就是小数直接夹着整数的情况成立条件是 tp > tq 。
#include <stdio.h>#include <math.h>#include <stdlib.h>const double e=1E-6;int main(){ long n=0; double p,q; long tp,tq; scanf("%lf%lf",&p,&q); p/=100.0;q/=100.0; while(++n){ //tp=long(n/p); //WA //tq=long(n/q); tp=long(n/p-e); tq=long(n/q+e); if(tq<tp) break; } printf("%ld\n",tq+1); return 0;}
By Black Storm（使用为知笔记）
Ural 1011. Conductors
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。