首页 > ACM题库 > HDU-杭电 > hdu 2257 Bob’s trouble待解决[解题报告]C++
2014
01-04

hdu 2257 Bob’s trouble待解决[解题报告]C++

Bob’s trouble

问题描述 :

Bob is a journalist, nowadays,he has a trouble. You know ,the Olympic Games is around the corner, as a fan of athletic sports, he certainly wants to see the Olympic Games, but as a journalist, the Olympic Games seems to be the busiest time,because Bob needs to report so many games.Fortunately , he has a kind boss.He gives Bob a target, as long as Bob meets the requirement, he can go home to see the Olympic Games.
Now,the boss gives every competition a value, which represents the importance of the competition.As long as the sum of the competitions’ value that Bob reported is not less than the target, he can go home.Although there are a lot of competitions every day,some competitions may take at the same time, so Bob can only choose some competitions to report.Now the problem is what’s the earliest time that Bob can go home?
To finish his work more easily, Bob gets some information about the competition.He finds every day is divided into 24 parts and every competition takes up at most 2 parts.There are 3 kinds of competitions:the first one only takes up 1 part of a day;the second one takes up two successional parts
of a day,it means the competition will hold at the p day’s q and (q+1) part;the third one is special,it is held at two successional days,it means the competition will hold at the p and p+1 days’ q part(ie.If a competition is held at the 2 day’s 3 part, it will also take up the 3 day’s 3 part.)
Meanwhile Bob finds two competitions’ first parts will not coincide,and two competitions’ second parts will not coincide .

输入:

The first line contains the number of cases.
For each case, there are several lines represent the information of the competitions (The number of competitions will not exceed 1150).Each line includes p : the start day of the competition (0 <= p <50); q : the start part of the competition (0 <= q <23) ; a string s represents the form of the competition ( "first" or "second" or "third" as recorded above ) ) the last one is the value of the competition m (0 <m <1000). Separate line with -1 means the end of the competition. Then a line with a num, need (0 <= need <2000000), means the boss’s target.

输出:

The first line contains the number of cases.
For each case, there are several lines represent the information of the competitions (The number of competitions will not exceed 1150).Each line includes p : the start day of the competition (0 <= p <50); q : the start part of the competition (0 <= q <23) ; a string s represents the form of the competition ( "first" or "second" or "third" as recorded above ) ) the last one is the value of the competition m (0 <m <1000). Separate line with -1 means the end of the competition. Then a line with a num, need (0 <= need <2000000), means the boss’s target.

样例输入:

2
0 17 third 999
-1
990
0 1 second 90
0 2 first 900 
-1
990

样例输出:

1
what a pity!

Hint
For the first case, the form of the competition is "third",so it will hold at the 0 day's 17 and the 1 day's 17. so it takes Bob 2 days to finish the report. For the second case, the first competion holds at the 0 day's 1 and 2,the second competition holds at the 0 day's 2,so Bob can only choose one of them.The value he can get is 900,so he can't go home.


  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  3. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.