午夜日韩在线观看,亚洲天天影视,亚洲高清不卡av

[导入]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�Q�；�Q?/p>

#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.

暴力求解的。。�?/p>

��是�{�间隔取敎ͼ�求其和最大��|��Q�！

#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.

水题�Q?个�h的单独�?/p>

3�?搭配�Q?/p>

2�?搭配�?/p>

3有多的话只能单独了�?/p>

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 发表评论

[导入]�q�接2012新赛季——HDOJ�p�d��热��n赛（2�Q? 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�Q�和N个H的排列数�Q�而且要求前面��L��个中必需H的个��C��大于W的个数~~~~

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

我想了好久都没有惛_��DP的方法，

最后想出来了，感觉�Ҏ��比较�W�~~~~

转化成了图，W表示往下走�Q�H表是往双��Q?/div>

则必��d��左下角中�?/div>

N个W和H的时候就是到N-1行的路径�?/div>

如N=1�Ӟ��为dp[0,0]

N=2时�ؓdp[1,0]+dp[1,1]

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

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

我的思�\有点�y�了~~~~但幸好做出来了！

代码如下�Q?/div>

#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;
}

要求的其实就是从�Q?�Q?�Q�到(N,N)的�\径数�Q�只能往下或者往双��Q�而且不能走到右上部分厅R�?/div>
文章来源:http://www.cnblogs.com/kuangbin/archive/2012/03/03/2378248.html

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

[导入]�q�接2012新赛季——HDOJ�p�d��热��n赛（2�Q?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

水题~~~~~

�q�代��可以了�Q?/div>

#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

店长推荐�?/td>

Time Limit: 1000 MS

Memory Limit: 65536 K

Total Submit: 97(31 users)

Total Accepted: 28(24 users)

Special Judge: No

Description

惛_��大家已经领略了店长的调皮,自从店长知道了vagaa之后��׃��直沉�q�h��中不能自�?教主看到后很是伤心，玩物丧志�?于是教主教店长了一个vagaa的新用法,资源搜烦功能。输入一些关键词后可以搜索出相关�׃�n的好资源�Q�店长得知后又是�ƣ喜若狂。同�?教主又发明一个游戏，是上�ơ的升��?�q�次�l�出一些由字母和数字的玩具的同�Ӟ��关键字不再是vagaa了，需要自��q��?看最后能�l�成多少个关键字�?/p>

Input

每行输入一个字�W�串由小写字母和数字�l�成�Q�每个字�W�代表一个玩�? 紧接着输入一个关键字�Q�同��L��字母和数字组�l�成�Q�字�W�串长度0

处理到文件结�?/p>

Output

输出能够�l�成关键字的数量

按照样例输出格式输出�q�换�?

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 发表评论

[导入]青蛙�q�河~~~~

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

青蛙�q�河

Time Limit: 1000 MS

Memory Limit: 65535 K

Total Submit: 29(11 users)

Total Accepted: 9(9 users)

Special Judge: No

Description

在河上有一座独木桥�Q�一只青蛙想沿着独木桥从河的一侧蟩到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一�ơ蟩�q�的距离都是正整敎ͼ�我们可以把独木桥上青蛙可能到辄��点看成数轴上的一串整点：0�Q?�Q?hellip;…�Q�L�Q�其中L是桥的长度）。坐标�ؓ0的点表示桥的��L��Q�坐标�ؓL的点表示桥的�l�点。青蛙从桥的��L��开始，不停的向�l�点方向跌��。一�ơ蟩跃的距离是s到t之间的�Q意正整数�Q�包括s,t�Q��?span style="color: #e53333;">当青蛙蟩到或跌��坐标为L的点�Ӟ��q��青蛙已经跛_��了独木桥�?/span>

题目�l�出独木桥的长度L�Q�青蛙蟩跃的距离范围s,t�Q�桥上石子的位置。你的�Q务是��定青蛙要想�q�河�Q�最��需要踩到的矛_��数�?/span>

Input

有多�l�测试数据�?/span>
对于每组��试数据�Q�第一行四个正整数L, s, t, n�Q? <= L <= 10^5, 1 <= s <= t <= 10�Q? <= n <= 100�Q�，分别表示独木桥的长度�Q�青蛙一�ơ蟩跃的最��距��，最大距��，及桥上石子的个数。第二行有n个不同的正整数分别表�C��n个石子在数��u上的位置�Q�数据保证桥的�v点和�l�点处没有石子）。所有相�ȝ��整数之间用一个空格隔开�?/span>

Output

每组��试数据仅输��Z��行，包括一个整敎ͼ�表示青蛙�q�河最��需要踩到的矛_��数�?/span>

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��Z��能到辄��� 
        //dp[i]表示到底 i  炚w��要经�q�的最���石子数�Q?1表示不能到达 
        for(int i=0;i        {
            scanf("%d",&a);
            flag[a]=1;//有石子�ؓ1�Q�否则�ؓ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]; //�W�一��?�?�?�l?�?
                    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�Q�迎�?012

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

2011已经逝去�Q?012已经到来~~~~

2011�q�_��L��觉自己得��C��很多�Q�也失去了很多，也留下不��的遗憾。仍记得2011�q�到来的时候，我自己对自己说这一�q�将会是我关键的一�q�_��l�自己定下了很多目标~~~~�q�些目标只能说是大致实现了吧�Q�也很多遗憾�Q?/span>

��Z��q�接2012�q�_��L��觉自己应该写点东西，来�ȝ��自己�?011�Q�规划下2012.但是一直抽不出旉��来写。等有时间了再写一��来�ȝ��2011吧！

人生应该处于不断的奋斗当中！2012�q�_��我要取得成功�Q?012�q�_��我一定会做得更好�Q?/span>

加��a�Q?/span>

————————————————————————————————————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

题目链接�Q?a >http://acm.hdu.edu.cn/showproblem.php?pid=1006

�q�题做了好久了，学习了网上的解法后自己写出来了�?/p>

��是枚�D12*60分钟�Q�看一分钟内有多少�U�是happytime�Q�一分钟内解三个不等式得到区间�?/p>

具体看代码�?/p>

代码有注释很详细的�?/p>

#include
#include
#include
#include
using namespace std;
struct qujian
{
    double l,r;
};    
double D;
qujian solve(double a,double b)//解方�E?D<=a*x+b<=360-D ,�q�且�?[0,60] 取交�?/span>
{
    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 �?满��题意的秒�?/span>
{
    double a,b;
    qujian s[3][2];
    qujian s1;
    
    //解方�E?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);
    
    //解方�E? 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);
    
    //解方�E? 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;
    //六个区间�Q�选三个取交集�?br />    //因�ؓ�l�对值的式子得到的两个区间要�qӞ��而三个不同表辑ּ�的区间要交，故这样做�?
    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 发表评论