问题 A: Find the demon[Easy] Solution

题目描述







There were demons in Binary Forest. They committed terrible crimes. However, no one saw their faces exactly, the only known thing is their height (they all share a common height, which is different from any other people). One day, the sheik of the forest asked all men lived in the forest to line up and stand in ascending order of their height, but he didn't know how to find the demons. Could you please help the poor sheik?




输入







The first line will be an integer T (100<=T<=1000), which is the number of test cases. For each case have two lines. The first line of the input contains two number n and m, n is the number of the men in the forest (1<=n<=106), and m is the demon's height. The second line contains n numbers which are the heights of the men in the forest. You should determine whether demon(s) is(are) among the men or not.




输出







For each case, output only one line. If there is(are) demon(s) among the men, output YES, otherwise output NO.




样例输入










2




4



1 2 3




1



1 2 3




样例输出










NO




YES













问题 B: High School Problem[Easy]



题目描述







Joy is a twelfth grade student who is aiming to go to SUSTech. One day, when he is doing math practices. He found a problem very hard. It gives a function goes like F(x) = 5x7+6x6+3x3+4x2-2xy (0 <= x <=100), y is a given real number. Can you help Joy find the minimum value of F(x) when x is in its domain?




输入







The first line of the input contains an integer T (1 <= T <= 100) which means the number of test cases. Then T lines follow, each line has only one real numbers Y (0 < Y < 1010).







输出







For each case, print the case number as well as the minimum value (accurate up to 4 decimal places) in one line, when x is in its domain.




样例输入










3




100




200




300




样例输出










Case 1: -193.3774




Case 2: -448.1475




Case 3: -729.3383







问题 C: Fight against demon[Easy]







题目描述







Under your help, the sheik of the forest found that the demons weren't among the men. They must have escaped. After reading ancient books, the sheik found that exactly m cd (candela, which is the unit of strength of light) units of light exposed by the join of two light swords can kill the demons. The men in the forest brought n light swords and put them in ascending order. Could you help sheik to find how many pairs are in the given n light swords with a combination of m cd.




(You can also choose a light sword twice if the condition is satisfied for the sheik can get another same one from the craftsman in the forest.)




输入







The first line will be an integer T (1<=T<=10), which is the number of test cases.




For each case contain two lines. The first line contains two numbers n (1<=n<=5000) and m (1<=m<=108), n is the number of light swords. m is the specified target.




The second line contains n integers:a1, a2,an (1<=ai=106, 1<=i<=n) , which are the light strengths of the light swords brought by men in the forest.




输出







For each case print the number of pairs.




样例输入










3




4 5




1 2 3 4




4 9




2 7 11 15




6



1 2 3




样例输出










2




1




0




提示







Here we simply regard the strength of the combination of light swords is the sum of light strengths of the original ones.




问题 D: University Hotel[Medium]



题目描述







As you know, every university has a hotel but it is always hard to book a room. Every year, thousands of orders fly to the hotels. The boss of a hotel in S University is busy, and hopes to make a program to deal with the orders. As he knows you are good at programming, he turns to you for help. The problem is described as follows:




We need to deal with the orders in the following n days. During the n days, there will be ri rooms available. And there are orders, every order is described by 3 integers, which are dj, sj, tj respectively. This indicates the customer need to book dj rooms from day sj to tj (inclusive). To simplify, we need not to care whether the customer get the same room everyday.




The principle for booking rooms is First come, First get, i.e., we need to assign rooms for the customers by the chronological sequence of the orders. If any one order can’t be satisfied, we need to stop assignment and inform the customer to modify the order. Here, the dissatisfaction refers to that at least one day during day sj to tj the number of remaining rooms is less than dj.




Now we need to know, whether there are orders can't be satisfied. And if so, we should inform which customer to modify the order.




输入







The input contains several test cases. For each test case:




The first line will be 2 integers n, m, which are the number of days and orders.




The second line contains n integers the ith number is ri, indicates the number of rooms can be booked that day.




Then there are m lines, every line has 3 integers dj, sj, tj, indicates the number of rooms to be booked, the begin day and end day of the jth order.




(1≤n,m≤106,0≤ri,dj≤109,1≤sj≤tj≤n)




输出







If all orders can be satisfied, the only output is one line, contains an integer 0, otherwise output two line, the first line output -1, and the second line output the index of the order that should be modified.




样例输入










4 3




2 5 4 3




2 1 3




3 2 4




4 2 4



样例输出
-1




2







问题 E: Sport Meeting[Medium]







题目描述







Annual Sport meeting in S University starts again. This year, the rule of relay running is modified by president of sports department. The rule after modification is as follows:




The total length of the relay running is L (1<=L<= 109). There are n (0<= n <= 500000) possible places to place a new racer (there is a race in the start line). Every racer runs to the next racer in front of him and the final racer runs to the finish line. But the number of racers is limited to a number m (1<=m<=n). Now the team of class 1788 want to know if they try to average the distance of every racer, how many meters one athlete should at most to run.




输入







The input contains several test cases. The first line of each case contains three positive integer L, n, and m. Then n lines follow. Each stands for the distance from the start line to the nth possible place to place new racer, two places will not be the same.




输出







For each case, output an integer standing for the meters one athlete should at most to run.




样例输入










6 1 2




2




25 3 3




11




2




18




样例输出










4



11



问题 F: Puberty Rite[Hard]







题目描述







A remote planet is called Joy. There is an ancient rule in Joy that every kid need to go for a hiking in dark forest to become an adult. This year, the kids of Joy that need to go for a hiking want to go together to ensure their safety. But they want to calculate a position to gather which minimizes the sum of their “distance”.




To simplify, we assume Joy is a straight line, every kid has a location xi on the line and every xi has a corresponding weight wi. As the gravitational force on Joy differs from earth, the “distance” between their home and the gathering position p need to be calculated as S3*Wi where S is |xi - p|.




In a word, we need to calculate the position p that minimize the total distance Σ( S3*Wi) where S is |xi - p|.




输入







The first line of the input is the number T(T<=20), which is the number of test cases. The first line of each case has one integer N(1<=N<=50000), indicating the number of kids. Then comes N lines in the order that xi<=xi+1 for all i(1<=i<N). The ith line contains two real number : Xi,Wi, representing the location and the weight of the ith kid. ( |xi|<=106, 0<wi<15 )




输出






For each test case, please output a line which is "Case #X: Y", X is the number of the test case and Y is the minimum sum of “distance” which is rounded to the nearest integer.




样例输入










1




4




0.6 5




3.9 10




5.1 7




8.4 10




样例输出










Case #1: 832




提示







Triple search.







问题 G: Save Joy[Hard]







题目描述







Joy is now applying for postgraduate programs. But due to his low GPA, no school really wants to receive him. One day poor Joy meet Aladdin, Aladdin promises to help him delete some of his courses he attended to increase his GPA. But now he is confused again, can you write a program to help him point out the maximum GPA he can get by deleting courses.




It should be mentioned that the calculation formula of GPA is Σ(s[i]*c[i])/Σ(s[i])




where the academic credit of the i-th course is s[i] and the score of the i-th course is c[i]. And because of the limitation of power of the magic lamp, he could at most delete k courses.



输入







The input contains multiple test cases. For each test case:




The first line has two positive integers n (1<=n<=105), k (0<=k<n), which is the total course number selected by Joy and the maximum number of deleting courses. The second line has n positive integers s[i]. The third line has n positive integers c[i] (1<=s[i], c[i]<=103).




输出







Output the highest final score. The answer should be round to 3 decimal places.










样例输入










1



1 2 3




2 1



样例输出
2.333