C++博客-ACM博客_kuangbin

[导入]VK Cup 2012 Qualification Round 1 E. Phone Talks

kuangbin — Mon, 05 Mar 2012 08:31:00 GMT

Cool J has recently become a businessman Mr. Jackson, and he has to make a lot of phone calls now. Today he has n calls planned. For each call we know the moment t_i (in seconds since the start of the day) when it is scheduled to start and its duration d_i (in seconds). All t_i are different. Mr. Jackson is a very important person, so he never dials anybody himself, all calls will be incoming.

Mr. Jackson isn't Caesar and he can't do several things at once. If somebody calls him while he hasn't finished the previous conversation, Mr. Jackson puts the new call on hold in the queue. In this case immediately after the end of the current call Mr. Jackson takes the earliest incoming call from the queue and starts the conversation. If Mr. Jackson started the call at the second t, and the call continues for d seconds, then Mr. Jackson is busy at seconds t, t + 1, ..., t + d - 1, and he can start a new call at second t + d. Note that if Mr. Jackson is not busy talking when somebody calls, he can't put this call on hold.

Mr. Jackson isn't Napoleon either, he likes to sleep. So sometimes he allows himself the luxury of ignoring a call, as if it never was scheduled. He can ignore at most k calls. Note that a call which comes while he is busy talking can be ignored as well.

What is the maximum number of seconds Mr. Jackson can sleep today, assuming that he can choose an arbitrary continuous time segment from the current day (that is, with seconds from the 1-st to the 86400-th, inclusive) when he is not busy talking?

Note that some calls can be continued or postponed to the next day or even later. However, the interval for sleep should be completely within the current day.

Input

The first input line contains a pair of integers n, k (0 ≤ k ≤ n ≤ 4000) separated by a space. Following n lines contain the description of calls for today. The description of each call is located on the single line and consists of two space-separated integers t_i and d_i, (1 ≤ t_i, d_i ≤ 86400). All t_i are distinct, the calls are given in the order of strict increasing t_i.

Scheduled times of calls [t_i, t_i + d_i - 1] can arbitrarily intersect.

Output

Print a number from 0 to 86400, inclusive — the maximally possible number of seconds for Mr. Jackson to sleep today.

Sample test(s)

Input

3 2
30000 15000
40000 15000
50000 15000

Output

Input

5 1
1 20000
10000 10000
20000 20000
25000 10000
80000 60000

Output

Note

In the first sample the most convenient way is to ignore the first two calls.

In the second sample it is best to ignore the third call. In this case Mr. Jackson will have been speaking:

first call: from 1-st to 20000-th second,
second call: from 20001-st to 30000-th second,
fourth call: from 30001-st to 40000-th second (the third call is ignored),
fifth call: from 80000-th to 139999-th second.

Thus, the longest period of free time is from the 40001-th to the 79999-th second.

DP；；；

#include
#include
#include<string>
#include<string.h>
using namespace std;
int dp[4005][4005];
struct node
{
    int s,d;
};
node a[4005];
int main()
{
    int i,j,n,k,ans;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
    for(i=0;i    {
        scanf("%d%d",&a[i].s,&a[i].d);
    }
     
     
     
    ans=0;
    for(i=0;i<=n;++i)
    {
        
        for(j=0;j<=k;++j)
        {
            dp[i][j]=86401;
        }
    }
    
    
    dp[0][0]=1;
    for(i=0;i    {
        for(j=0;j<=k;++j)
        {
            if(j!=k)
                dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]);
            if(dp[i][j]            {
                ans=max(ans,a[i].s-dp[i][j]);
                dp[i+1][j]=min(dp[i+1][j],a[i].s+a[i].d);
            }
            else
            {
                dp[i+1][j]=min(dp[i+1][j],dp[i][j]+a[i].d);
            }
        }
    }
    
    
    
    for(j=0;j<=k;++j)
    {
        ans=max(ans,86401-dp[n][j]);
    }
    printf("%d\n",ans);
    }
    
    return 0;    
    
    
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380629.html

kuangbin 2012-03-05 16:31 发表评论

[导入]VK Cup 2012 Qualification Round 1 D. Ice Sculptures

kuangbin — Mon, 05 Mar 2012 08:30:00 GMT

The Berland University is preparing to celebrate the 256-th anniversary of its founding! A specially appointed Vice Rector for the celebration prepares to decorate the campus. In the center of the campus n ice sculptures were erected. The sculptures are arranged in a circle at equal distances from each other, so they form a regular n-gon. They are numbered in clockwise order with numbers from 1 to n.

The site of the University has already conducted a voting that estimated each sculpture's characteristic of t_i — the degree of the sculpture's attractiveness. The values of t_i can be positive, negative or zero.

When the university rector came to evaluate the work, he said that this might be not the perfect arrangement. He suggested to melt some of the sculptures so that:

the remaining sculptures form a regular polygon (the number of vertices should be between 3 and n),
the sum of the t_i values of the remaining sculptures is maximized.

Help the Vice Rector to analyze the criticism — find the maximum value of t_i sum which can be obtained in this way. It is allowed not to melt any sculptures at all. The sculptures can not be moved.

Input

The first input line contains an integer n (3 ≤ n ≤ 20000) — the initial number of sculptures. The second line contains a sequence of integers t₁, t₂, ..., t_n, t_i — the degree of the i-th sculpture's attractiveness ( - 1000 ≤ t_i ≤ 1000). The numbers on the line are separated by spaces.

Output

Print the required maximum sum of the sculptures' attractiveness.

Sample test(s)

Input

8
1 2 -3 4 -5 5 2 3

Output

Input

6
1 -2 3 -4 5 -6

Output

Input

6
1 2 3 4 5 6

Output

Note

In the first sample it is best to leave every second sculpture, that is, leave sculptures with attractivenesses: 2, 4, 5 и 3.

暴力求解的。。。

就是等间隔取数，求其和最大值！！！

#include
int aa[20110];


int main()
{
    
    
    int n;
    int res;
    int sum;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=1;i<=n;i++)
          scanf("%d",&aa[i]);
        res=-200000000;
        for(int i=1;i<=n/3;i++)
        {
            if(n%i!=0)continue;
            if(n/i<3)continue;
            for(int j=1;j<=i;j++)
            {
                sum=0;
                for(int k=j;k<=n;k+=i)
                  sum+=aa[k];
                if(sum>res) res=sum;
            }    
        }    
        
        
        printf("%d\n",res);
        
        
    }   
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380627.html

kuangbin 2012-03-05 16:30 发表评论

[导入]VK Cup 2012 Qualification Round 1 B. Taxi

kuangbin — Mon, 05 Mar 2012 08:28:00 GMT

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of s_i friends (1 ≤ s_i ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

Input

The first line contains integer n (1 ≤ n ≤ 10⁵) — the number of groups of schoolchildren. The second line contains a sequence of integers s₁, s₂, ..., s_n (1 ≤ s_i ≤ 4). The integers are separated by a space, s_i is the number of children in the i-th group.

Output

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

Sample test(s)

Input

5
1 2 4 3 3

Output

Input

8
2 3 4 4 2 1 3 1

Output

Note

In the first test we can sort the children into four cars like this:

the third group (consisting of four children),
the fourth group (consisting of three children),
the fifth group (consisting of three children),
the first and the second group (consisting of one and two children, correspondingly).

There are other ways to sort the groups into four cars.

水题，4个人的单独。

3和1搭配，

2和2搭配。

3有多的话只能单独了。

2可以加入1个的

#include
int aa[5];



int main()
{
    
    
    
    int n;
    int t;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<5;i++)aa[i]=0;
        while(n--)
        {
            scanf("%d",&t);
            aa[t]++;
        }    
        int res=0;
        res+=aa[4];
        if(aa[1]==aa[3])
        {
            res+=aa[1];
            aa[1]=0;
            aa[3]=0;
            if(aa[2]%2==0)
            {
                res+=aa[2]/2;
            }    
            else
            {
                res=res+aa[2]/2+1;
            }    
        }    
        else if(aa[1]3])
        {
            res+=aa[1];
            aa[3]-=aa[1];
            aa[1]=0;
            
            res+=aa[3];
            
            if(aa[2]%2==0)
            {
                res+=aa[2]/2;
            }    
            else
            {
                res=res+aa[2]/2+1;
            }  
        }    
        else
        {
            res+=aa[3];
            aa[1]-=aa[3];
            aa[3]=0;
            
            if(aa[2]%2==0)
            {
                res+=aa[2]/2;
            }    
            else
            {
                res=res+aa[2]/2+1;
                aa[1]-=2;
            }  
            
            if(aa[1]>=1)
            {
                if(aa[1]%4==0) res+=aa[1]/4;
                else
                res=res+aa[1]/4+1;
            }    
        }    
        
        
        
        printf("%d\n",res);
    }    
    
    
    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380624.html

kuangbin 2012-03-05 16:28 发表评论

[导入]VK Cup 2012 Qualification Round 1 A. Next Round

kuangbin — Mon, 05 Mar 2012 08:26:00 GMT

"Contestant who earns a score equal to or greater than the k-th place finisher's score will advance to the next round, as long as the contestant earns a positive score..." — an excerpt from contest rules.

A total of n participants took part in the contest (n ≥ k), and you already know their scores. Calculate how many participants will advance to the next round.

Input

The first line of the input contains two integers n and k (1 ≤ k ≤ n ≤ 50) separated by a single space.

The second line contains n space-separated integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 100), where a_i is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: a_i ≥ a_i + 1).

Output

Output the number of participants who advance to the next round.

Sample test(s)

Input

8 5
10 9 8 7 7 7 5 5

Output

Input

4 2
0 0 0 0

Output

Note

In the first example the participant on the 5th place earned 7 points. As the participant on the 6th place also earned 7 points, there are 6 advancers.

In the second example nobody got a positive score.

很简单的题目~~~~~

#include
int mm[120];
int main()
{
    
    
    int n,k;
    
    
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        for(int i=1;i<=n;i++)
          scanf("%d",&mm[i]);
        int res=k;
        if(mm[k]>0)
        {
            for(int i=k+1;i<=n;i++)
            {
                if(mm[i]break;
                res++;
            }    
        }  
        else
        {
            res--;
            for(int i=k-1;i>=1;i--)
            {
                if(mm[i]>0) break;
                res--;
            }    
        } 
        
        printf("%d\n",res);     
    }    
    
    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/05/2380621.html

kuangbin 2012-03-05 16:26 发表评论

[导入]迎接2012新赛季——HDOJ系列热身赛（2） Problem E HDU4165 Pills

kuangbin — Sat, 03 Mar 2012 05:25:00 GMT

Problem E

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

Aunt Lizzie takes half a pill of a certain medicine every day. She starts with a bottle that contains N pills.

On the first day, she removes a random pill, breaks it in two halves, takes one half and puts the other half back into the bottle.

On subsequent days, she removes a random piece (which can be either a whole pill or half a pill) from the bottle. If it is half a pill, she takes it. If it is a whole pill, she takes one half and puts the other half back into the bottle.

In how many ways can she empty the bottle? We represent the sequence of pills removed from the bottle in the course of 2N days as a string, where the i-th character is W if a whole pill was chosen on the i-th day, and H if a half pill was chosen (0 <= i < 2N). How many different valid strings are there that empty the bottle?

Input

The input will contain data for at most 1000 problem instances. For each problem instance there will be one line of input: a positive integer N <= 30, the number of pills initially in the bottle. End of input will be indicated by 0.

Output

For each problem instance, the output will be a single number, displayed at the beginning of a new line. It will be the number of different ways the bottle can be emptied.

Sample Input

6 1 4 2 3 30 0

Sample Output

132 1 14 2 5 3814986502092304

相当于求N个W，和N个H的排列数，而且要求前面任意个中必需H的个数不大于W的个数~~~~

不知道哪些大神是怎么样做出来的，好快的速度就做出来了~~~~

我想了好久都没有想到DP的方法，

最后想出来了，感觉方法比较笨~~~~

转化成了图，W表示往下走，H表是往右走，

则必须在左下角中。

N个W和H的时候就是到N-1行的路径数

如N=1时，为dp[0,0]

N=2时为dp[1,0]+dp[1,1]

N=3时为dp[2,0]+dp[2,1]+dp[2,2]

应该会有更好的方法的~~~~~

我的思路有点蹉了~~~~但幸好做出来了！

代码如下：

#include
long long dp[31][31];
void init()
{
    dp[0][0]=1;
    for(int i=1;i<31;i++)
    {
        dp[i][0]=1;
        for(int j=1;j          dp[i][j]=dp[i-1][j]+dp[i][j-1];
        dp[i][i]=dp[i][i-1];
    }   
} 
int main()
{
    int N;
    init();
    while(scanf("%d",&N),N)
    {
        printf("%I64d\n",dp[N][N]);
    }    
    return 0;
}

要求的其实就是从（0，0）到(N,N)的路径数，只能往下或者往右走，而且不能走到右上部分去。

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378248.html

kuangbin 2012-03-03 13:25 发表评论

[导入]迎接2012新赛季——HDOJ系列热身赛（2） Problem A HDU 4161 Iterated Difference

kuangbin — Sat, 03 Mar 2012 05:11:00 GMT

Problem A

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0

Problem Description

You are given a list of N non-negative integers a(1), a(2), ... , a(N). You replace the given list by a new list: the k-th entry of the new list is the absolute value of a(k) - a(k+1), wrapping around at the end of the list (the k-th entry of the new list is the absolute value of a(N) - a(1)). How many iterations of this replacement are needed to arrive at a list in which every entry is the same integer?

For example, let N = 4 and start with the list (0 2 5 11). The successive iterations are:

3 6 11
3 5 9
2 4 8
2 4 6
2 2 6
0 4 4
4 0 4
4 4 4
Thus, 8 iterations are needed in this example.

Input

The input will contain data for a number of test cases. For each case, there will be two lines of input. The first line will contain the integer N (2 <= N <= 20), the number of entries in the list. The second line will contain the list of integers, separated by one blank space. End of input will be indicated by N = 0.

Output

For each case, there will be one line of output, specifying the case number and the number of iterations, in the format shown in the sample output. If the list does not attain the desired form after 1000 iterations, print 'not attained'.

Sample Input

4 0 2 5 11 5 0 2 5 11 3 4 300 8600 9000 4000 16 12 20 3 7 8 10 44 50 12 200 300 7 8 10 44 50 3 1 1 1 4 0 4 0 4 0

Sample Output

Case 1: 8 iterations Case 2: not attained Case 3: 3 iterations Case 4: 50 iterations Case 5: 0 iterations Case 6: 1 iterations

水题~~~~~

迭代就可以了！

#include
#include
#include
using namespace std;
int a[50];
int main()
{
    int N,res,j;
    int iCase=0;
    while(scanf("%d",&N),N)
    {
        iCase++;
        for(int i=0;i        {
            scanf("%d",&a[i]);
        }   
       for(j=0;j1;j++)
            {
                if(a[j]!=a[j+1])break;
            }  
       if(j>=N-1)
       {
           printf("Case %d: 0 iterations\n",iCase);
           continue;
           
       }    
        for(res=1;res<=1000;res++)
        {
            a[N]=a[0];
            for(int i=0;i            {
                a[i]=abs(a[i]-a[i+1]);
            } 
            for(j=0;j1;j++)
            {
                if(a[j]!=a[j+1])break;
            }  
            if(j>=N-1)break;     
        }   
        if(res<=1000)printf("Case %d: %d iterations\n",iCase,res);
        else printf("Case %d: not attained\n",iCase);  
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378235.html

kuangbin 2012-03-03 13:11 发表评论

[导入]店长推荐Ⅱ~~~~

kuangbin — Mon, 27 Feb 2012 12:03:00 GMT

店长推荐Ⅱ

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 97(31 users)

Total Accepted: 28(24 users)

Special Judge: No

Description

想必大家已经领略了店长的调皮,自从店长知道了vagaa之后就一直沉迷期中不能自拔,教主看到后很是伤心，玩物丧志啊!于是教主教店长了一个vagaa的新用法,资源搜索功能。输入一些关键词后可以搜索出相关共享的好资源，店长得知后又是欣喜若狂。同时,教主又发明一个游戏，是上次的升级版,这次给出一些由字母和数字的玩具的同时，关键字不再是vagaa了，需要自己给出.看最后能组成多少个关键字。

Input

每行输入一个字符串由小写字母和数字组成，每个字符代表一个玩具, 紧接着输入一个关键字，同样由字母和数字组组成，字符串长度0

处理到文件结束

Output

输出能够组成关键字的数量

按照样例输出格式输出并换行.

Sample Input

vagaadsfaagav ga
asgvasdfzxcades dea

Sample Output

Case 1: 2
Case 2: 1

Author

void

#include
#include<string.h>
int tt[40],count[40];
char str[10010];
int main()
{
    int len,m;
    int iCase=0;
    while(scanf("%s",&str)!=EOF)
    {
        iCase++;
        len=strlen(str);
        memset(tt,0,sizeof(tt));
        memset(count,0,sizeof(count));
        for(int i=0;i        {
            if(str[i]>='0'&&str[i]<='9')
            {
                m=str[i]-'0'+0;
                tt[m]++;
                
            }    
            else
            {
                m=str[i]-'a'+10;
                tt[m]++;
            }    
        }  
        scanf("%s",&str);
        len=strlen(str);
        for(int i=0;i        {
            if(str[i]>='0'&&str[i]<='9')
            {
                m=str[i]-'0'+0;
                count[m]++;
                
            }    
            else
            {
                m=str[i]-'a'+10;
                count[m]++;
            }    
        }    
        int res=10000;
        for(int i=0;i<=9+26;i++)
        {
            if(count[i]>0)
            {
                int tmp=tt[i]/count[i];
                if(tmp            }    
        }    
        printf("Case %d: %d\n",iCase,res);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/02/27/2370325.html

kuangbin 2012-02-27 20:03 发表评论

[导入]青蛙过河~~~~

kuangbin — Mon, 27 Feb 2012 07:16:00 GMT

青蛙过河

Time Limit: 1000 MS

Memory Limit: 65535 K

Total Submit: 29(11 users)

Total Accepted: 9(9 users)

Special Judge: No

Description

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：0，1，……，L（其中L是桥的长度）。坐标为0的点表示桥的起点，坐标为L的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是s到t之间的任意正整数（包括s,t）。当青蛙跳到或跳过坐标为L的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度L，青蛙跳跃的距离范围s,t，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

Input

有多组测试数据。
对于每组测试数据，第一行四个正整数L, s, t, n（1 <= L <= 10^5, 1 <= s <= t <= 10，1 <= n <= 100），分别表示独木桥的长度，青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数。第二行有n个不同的正整数分别表示这n个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

Output

每组测试数据仅输出一行，包括一个整数，表示青蛙过河最少需要踩到的石子数。

Sample Input

10 2 3 5
2 3 5 6 7

Sample Output

#include
#include<string.h>
const int MAXN=100020;
int flag[MAXN];
int dp[MAXN];
int main()
{
    int L,s,t,n;
    int a;
    while(scanf("%d%d%d%d",&L,&s,&t,&n)!=EOF)
    {
        memset(flag,0,sizeof(flag));
        memset(dp,-1,sizeof(dp));//初始化，-1为不能到达的 
        //dp[i]表示到底 i  点需要经过的最少石子数，-1表示不能到达 
        for(int i=0;i        {
            scanf("%d",&a);
            flag[a]=1;//有石子为1，否则为0 
        }    
        dp[0]=0;
        for(int i=s;i<=L+t-1;i++)
        {
            for(int j=i-t;j<=i-s;j++)// j 点跳到 i 点 
            {
                if(j>=0&&dp[j]!=-1)//j 点能够跳到 
                {
                    if(dp[i]==-1)dp[i]=dp[j]+flag[i]; //第一次 直 接 给 值 
                    else if(dp[i]>dp[j]+flag[i]) dp[i]=dp[j]+flag[i];//找小的值 
                    
                }    
            }    
        }  
        int res=10000;
        for(int i=L;i<=L+t-1;i++)//L 到 L+t-1 中最小的非 -1 值 
        {
            if(dp[i]!=-1&&dp[i]        }      
        printf("%d\n",res);
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/02/27/2369901.html

kuangbin 2012-02-27 15:16 发表评论

[导入]告别2011，迎接2012

kuangbin — Mon, 02 Jan 2012 16:18:00 GMT

2011已经逝去，2012已经到来~~~~

2011年，总感觉自己得到了很多，也失去了很多，也留下不尽的遗憾。仍记得2011年到来的时候，我自己对自己说这一年将会是我关键的一年，给自己定下了很多目标~~~~这些目标只能说是大致实现了吧，也很多遗憾！

为了迎接2012年，总感觉自己应该写点东西，来总结自己的2011，规划下2012.但是一直抽不出时间来写。等有时间了再写一篇来总结2011吧！

人生应该处于不断的奋斗当中！2012年，我要取得成功！2012年，我一定会做得更好！

加油！

————————————————————————————————————by kuangbin

文章来源:http://www.cnblogs.com/kuangbin/archive/2012/01/03/2310575.html

kuangbin 2012-01-03 00:18 发表评论

[导入]HDU 1006 Tick and Tick

kuangbin — Sun, 04 Dec 2011 07:17:00 GMT

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1006

这题做了好久了，学习了网上的解法后自己写出来了。

就是枚举12*60分钟，看一分钟内有多少秒是happytime，一分钟内解三个不等式得到区间。

具体看代码。

代码有注释很详细的。

#include
#include
#include
#include
using namespace std;
struct qujian
{
    double l,r;
};    
double D;
qujian solve(double a,double b)//解方程 D<=a*x+b<=360-D ,并且和 [0,60] 取交集
{
    qujian p;
    if(a>0)
    {
        p.l=(D-b)/a;
        p.r=(360-D-b)/a;
    }    
    else
    {
        p.l=(360-D-b)/a;
        p.r=(D-b)/a;
    }    
    if(p.l<0)p.l=0;
    if(p.r>60)p.r=60;
    if(p.l>=p.r)  p.l=p.r=0;
    return p;
}     
qujian jiao(qujian a,qujian b)
{
    qujian p;
    p.l=max(a.l,b.l);
    p.r=min(a.r,b.r);
    if(p.l>=p.r) p.l=p.r=0;
    return p;
}    
/*
   hh=30*h+m/2+s/120;
   mm=6*m+s/10;
   ss=6*s;
   D<=|hh-mm|<=360-D;
   D<=|hh-ss|<=360-D;
   D<=|mm-ss|<=360-D;
   hh-mm=
*/
double happytime(int h,int m)//计算 h 时，m 分 满足题意的秒数
{
    double a,b;
    qujian s[3][2];
    qujian s1;
    
    //解方程 D<=|hh-mm|<=360-D 
    //hh=30*h+m/2+s/120;
    //mm=6*m+s/10;
    a=1.0/120-0.1;
    b=30*h+m/2.0-6*m;
    s[0][0]=solve(a,b);
    s[0][1]=solve(-a,-b);
    
    //解方程  D<=|hh-ss|<=360-D 
    //hh=30*h+m/2+s/120;
    //ss=6*s;
    a=1.0/120-6.0;
    b=30*h+m/2.0;
    s[1][0]=solve(a,b);
    s[1][1]=solve(-a,-b);
    
    //解方程  D<=|mm-ss|<=360-D 
    //mm=6*m+s/10;
    //ss=6*s;
    a=0.1-6;
    b=6*m;
    s[2][0]=solve(a,b);
    s[2][1]=solve(-a,-b);
    
    double res=0;
    //六个区间，选三个取交集。
    //因为绝对值的式子得到的两个区间要并，而三个不同表达式的区间要交，故这样做。 
    for(int i=0;i<2;i++)
      for(int j=0;j<2;j++)
         for(int k=0;k<2;k++)
         {
             s1=jiao(jiao(s[0][i],s[1][j]),s[2][k]);
             res+=s1.r-s1.l;
         }    
    return res;
}     

int main()
{
    while(scanf("%lf",&D))
    {
        if(D==-1) break;
        double res=0;
        int h,m;
        for(h=0;h<12;h++)
        {
            for(m=0;m<60;m++)
            {
                res+=happytime(h,m);
            }    
        }    
        printf("%.3lf\n",res*100.0/(60*60*12));    
    }    
    return 0;
}

文章来源:http://www.cnblogs.com/kuangbin/archive/2011/12/04/2275470.html

kuangbin 2011-12-04 15:17 发表评论