《浪潮杯山东省第六届ACM大学生程序设计竞赛正赛题目》由会员分享，可在线阅读，更多相关《浪潮杯山东省第六届ACM大学生程序设计竞赛正赛题目（17页珍藏版）》请在金锄头文库上搜索。
1、 The 2015 ACMThe 2015 ACM ICPC China Shandong Provincial ICPC China Shandong Provincial Programming ContestProgramming Contest Problem Set May 10 2015May 10 2015 This problem set should contain twelve 12 problems on fifteen 15 pages Please inform a runner immediately if something is missing from you
2、r problem set Problem A Nias and TugProblem A Nias and Tug ofof WarWar Description Nias is fond of tug of war One day he organized a tug of war game and invited a group of friends to take part in Nias will divide them into two groups The strategy is simple sorting them into a row according to their
3、height from short to tall then let them say one and two alternately i e one two one two The people who say one are the members of the red team while others are the members of the blue team We know that the team which has a larger sum of weight has advantages in the tug of war Now give you the guys h
4、eights and weights please tell us which team has advantages Input The first line of input contains an integer T indicating the number of test cases The first line of each test case contains an integer N N is even and 6 N 100 Each of the next N lines contains two real numbers X and Y representing the
5、 height and weight of a friend respectively Output One line for each test case If the red team is more likely to win output red if the blue team is more likely to win output blue If both teams have the same weight output fair Sample Input 1 6 170 55 165 3 52 5 180 2 60 3 173 3 62 3 175 57 162 2 50 S
6、ample Output blue 1 Problem Problem B B Lowest Unique PriceLowest Unique Price Description Recently my buddies and I came across an idea We want to build a website to sell things in a new way For each product everyone could bid at a price or cancel his previous bid finally we sale the product to the
7、 one who offered the lowest unique price The lowest unique price is defined to be the lowest price that was called only once So we need a program to find the lowest unique price We d like to write a program to process the customers bids and answer the query of what s the current lowest unique price
8、All what we need now is merely a programmer We will give you an Accepted as long as you help us to write the program Input The first line of input contains an integer T indicating the number of test cases T 60 Each test case begins with a integer N 1 N 200000 indicating the number of operations Next
9、 N lines each represents an operation There are three kinds of operations b x x 1 x 106 is an integer this means a customer bids at price x c x a customer has canceled his bid at price x q means Query You should print the current lowest unique price Our customers are honest they won t cancel the pri
10、ce they didn t bid at Output Please print the current lowest unique price for every query q Print none without quotes if there is no lowest unique price Sample Input 2 2 3 b 2 b 2 q 12 b 2 b 2 b 3 b 3 q b 4 q c 4 c 3 q c 2 q Sample Output none none 4 3 2 3 Problem C Problem C Game Game Description O
11、ne day zbybr is playing a game with blankcqk here are the rules of the game There is a circle of N stones zbybr and blankcqk take turns taking the stones Each time one player can choose to take one stone or take two adjacent stones You should notice that if there are 4 stones and zbybr takes the 2nd
12、 the 1st and 3rd stones are still not adjacent The winner is the one who takes the last stone Now the game begins and zbybr moves first If both of them will play with the best strategy can you tell me who will win the game Input The first line of input contains an integer T indicating the number of
13、test cases T 100000 For each case there is a positive integer N N 1018 Output Output the name of the winner Sample Input 2 1 2 Sample Output zbybr zbybr 4 Problem Problem D D StarsStars Description There are N 1 N 400 stars in the sky And each of them has a unique coordinate x y 1 x y N Please calcu
14、late the minimum area of the rectangle the edges of the rectangle must be parallel to the X Y axes that can cover at least K 1 K N stars The stars on the borders of the rectangle should not be counted and the length of each rectangle s edge should be an integer Input Input may contain several test c
15、ases The first line is a positive integer T T 10 indicating the number of test cases below For each test cases the first line contains two integers N K indicating the total number of the stars and the number of stars the rectangle should cover at least Each of the following N lines contains two inte
16、gers x y indicating the coordinate of the stars Output For each test case output the answer on a single line Sample Input 2 1 1 1 1 2 2 1 1 1 2 Sample Output 1 2 5 Problem EProblem E BIGZHUGOD and His Friends IBIGZHUGOD and His Friends I Description BIGZHUGOD and his three friends feel bored at home then they decide to play a game called niuniu The rules of niuniu are first randomly pick 5 cards from all cards then divide them into 2 groups one group has 2 cards and the other has 3 cards If the
