原题来源:杭电1006
Problem Description
The three hands of the clock are rotating every second and meeting each other many times everyday. Finally, they get bored of this and each of them would like to stay away from the other two. A hand is happy if it is at least D degrees from any of the rest. You are to calculate how much time in a day that all the hands are happy.
Input
The input contains many test cases. Each of them has a single line with a real number D between 0 and 120, inclusively. The input is terminated with a D of -1.
Output
For each D, print in a single line the percentage of time in a day that all of the hands are happy, accurate up to 3 decimal places.
Sample Input
Sample Output
该题目要计算一天中时针、分针、秒针之间角度大于某一角度的概率。最朴素的算法是模拟每秒(每0.1秒或0.01秒)时计算三个针子之间角度,但计算量超大。以下java程序便是一例,由于计算量过大,会超时,但如减小计算量,精度又无法满足需求:
import java.io.*;
import java.util.*;
public class P1006_2 {
public static void main(String args[]) throws IOException{
Scanner sin = new Scanner(System.in);
int count ;
double data[] = new double[3];
float distance ;
distance = sin.nextFloat();
while((int)distance != -1){
count = 0;
if(distance >=120)
System.out.println("0.000");
else
{
//12小时分时秒针重合一次,每小时时分秒针分别走30,360,360*60度
for(int i = 0;i<12;i++)
//每小时均分30份,每份时时分秒针分别走1,12,720度
for(int j=0;j<30;j++)
// 每份再均分1000小份
for(int k=0;k<1000;k++){
data[0] = (i * 30 + j + 0.001 * k);
data[1] = (j * 12 + 0.012 * k);
data[2] = (k* 0.72)%360;
Arrays.sort(data);
if(data[1]-data[0]>=distance&data[2]-data[1]>=distance&360+data[0]-data[2]>=distance)
count ++;
}
double percent = (double)count /360/10;
System.out.printf("%f\n",percent);
}
distance = sin.nextFloat();
}
}
}
不能AC,这是个大问题。后来从网上得到一个巧妙的算法,其原理是以空间换时间。其源程序(c++)如下:
#include <cstdio> #include <iostream> using namespace std;
inline double max(double a,double b,double c) { a= a > b ? a: b; a= a > c ? a: c; return a; } inline double min(double a,double b,double c) { a= a < b ? a: b; a= a < c ? a: c; return a; } int main() { double hdans; double dsm[1444],dsh[1444],dmh[26]; //dsm存放秒针与分针之间的角度,dsh存放秒针与时针之间的角度 //dmh存放分针与时针之间的角度。 double s,m,h;
s=3600.0000/59; m=43200.0000/719; h=43200.0000/11;
while(cin >> hdans && hdans !=-1) { int i,j; int sp[2],mp[2],hp[2]; double sum=0; double x=0,y=0; dsm[0] = (10*hdans)/59; dsh[0] = (120*hdans)/719; dmh[0] = (120*hdans)/11;
dsm[1] = s-dsm[0]; dsh[1] = m-dsh[0]; dmh[1] = h-dmh[0];
for(i=2,j=3; ;i+=2,j+=2) { dsm[i] = dsm[i-2]+s; dsm[j] = dsm[j-2]+s; if(dsm[i]>43200 && dsm[j]>43200) break; } for(i=2,j=3;;i+=2,j+=2) { dsh[i] = dsh[i-2]+m; dsh[j] = dsh[j-2]+m; if(i==1436) i=1436; if(dsh[i]>43200 && dsh[j]>43200) break; } for(i=2,j=3;;i+=2,j+=2) { dmh[i] = dmh[i-2]+h; dmh[j] = dmh[j-2]+h; if(dmh[i]>43200 && dmh[j]>43200) break; } //以上代码用来根据hdans初始化dsm,dsh,dmh; sp[0]=mp[0]=hp[0]=0; sp[1]=mp[1]=hp[1]=1; //sp,mp,hp分别为dsm,dsh,dmh的上下界指针。 while(y<=43200 && x<=43200) { x=max(dsm[sp[0]],dsh[mp[0]],dmh[hp[0]]); y=min(dsm[sp[1]],dsh[mp[1]],dmh[hp[1]]); if(x<y) sum+=y-x;
if(y==dsm[sp[1]]) {sp[0]+=2;sp[1]+=2;} if(y==dsh[mp[1]]) {mp[0]+=2;mp[1]+=2;} if(y==dmh[hp[1]]) {hp[0]+=2;hp[1]+=2;} } printf("%.3f\n",sum/432); }//while return 0; }
|
其中,s,m,h分别表示秒针与分针,秒针与时针,分针与时针重合一次所需要的时间。
dsm,dsh,dmh数组一分为二,偶下标元素表示秒针与分针,秒针与时针,分针与时针之间角度满足时所对应的开始时间,而奇下标元素则表示不满足时所对应的开始时间。
很是巧妙!足见偶学习的空间还是很大的。o(∩_∩)o...哈哈 加油~
分享到:
相关推荐
ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛ACM大赛
这是关于ACM图论问题的经典讲解,简洁精辟的讲解了常见的ACM图论问题!
ACM中的数学问题_林舒.ppt
ACM统计数字问题,通过ACM网站accept
ACM ACM ACM ACM ACM讲义.ppt
ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板AACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM 模板ACM ...
ACM 在线测评第二题,括号配对!表示完全是自己写的,没有参考他人思想!有不足之处请指正!
acm,背包问题大全,详细讲解,内容齐全,概括到位,c++
ACM常见解题思想,及思维转换,和一般的优化求解,专项算法解析
欧洲ACM问题集,里面是英文的,ACM爱好者明智的选择,本人精心收集,分享给广大朋友
ACM PRO ACM PROACM PRO ACM PROACM PRO ACM PRO
很有用的关于ACM程序设计大赛中的大数问题的全解析。。。
ACM常用代码 ACM常用代码 ACM常用代码
ACM程序设计大赛算法模板 ACM模板 一般编程问题 【实例简介】 这是我整理所得,不代表是我写的、、对于有些参考没有标记的,欢迎你们提出我来修正!感谢那些浙大ACM的前辈!!! ACM程序设计大赛算法模板 ACM模板 ...
包含近几年多道ACM面试题目,希望有所帮助
acm模板acm模板acm模板acm模板acm模板acm模板acm模板acm模板
ACM中背包问题经典九讲,01背包完全背包重复背包混合背包多重费用背包应有尽有,欢迎下载
ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码ACM常用代码