“浪潮杯”山东省第六届ACM大学生程序设计竞赛正赛题目.pdf

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 your 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 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 heights 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 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 Sample 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 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 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 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 price 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 One 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 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 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 calculate 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 cases 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 integers 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 sum of both groups are multiples of 10 then they are niuniu Moreover A counts for 1 J Q K black joker and red joker counts for 10 BIGZHUGOD has an incomplete pack of card And his three friends let BIGZHUGOD pick up 5 cards randomly if they are niuniu BIGZHUGOD will gain meals from friends Now BIGZHUGOD knows the number of every kind of card he wants to know the possibility that he can gain the meal Input The first line of input contains an integer T indicating the number of test cases T 500 Each case there are 15 integers x1 x2 x15 indicating the number of A 2 3 10 J Q K black joker red joker 0 x1 x2 x13 4 0 x14 x15 1 x1 x2 x15 5 Output For each case output in a single line contains the possibility of BIGZHUGOD can get big meal from his friends If the possibility is 0 output 0 Otherwise output p q where p and q are co prime integers have no common divisor greater than one Sample Input 2 4 4 4 4 4 4 4 4 4 4 4 4 4 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 Sample Output 2681 35139 0 6 Problem F Problem F BIGZHUGOD and His Friends IBIGZHUGOD and His Friends II I Description BIGZHUGOD and his three friends are playing a game in a triangle ground The number of BIGZHUGOD is 0 and his three friends are numbered from 1 to 3 Before the game begins three friends stand on three vertices of triangle in numerical order 1 on A 2 on B 3 on C BIGZHUGOD stands inside of triangle Then the game begins three friends run to the next vertex in uniform speed and in straight direction 1 to B 2 to C 3 to A and there speeds may different And BIGZHUGOD can stand in any position inside the triangle When any of his friends arrives at next vertex the game ends BIGZHUGOD and his friends have made an agreement we assume that the beginning is time 0 if during the game you can find a moment that BIGZHUGOD can block the sight line of 1 to C 2 to A 3 to B Then each friend has to treat BIGZHUGOD with a big meal Now BIGZHUGOD knows the lengths of time that his three friends need run to next vertices t1 t2 and t3 He wants to know whether he has a chance to gain three big meals of course he wants to know in which exciting moment t he can block three friends sight line Input The first line contains an integer T indicating the number of test cases T 1000 For each case there are three integer t1 t2 t3 1 t1 t2 t3 100 Output If BIGZHUGOD has a chance to gain big meal from his friends output YES and the exciting moment t rounding to 4 digits after decimal point Otherwise output NO Sample Input 2 1 1 1 3 4 6 Sample Output YES 0 5000 YES 2 0000 7 ProblemProblem G G Cube NumberCube Number Description In mathematics a cube number is an integer that is the cube of an integer In other words it is the product of some integer with itself twice For example 27 is a cube number since it can be written as 3 3 3 Given an array of distinct integers a1 a2 an you need to find the number of pairs ai aj that satisfy ai aj is a cube number Input The first line of the input contains an integer T 1 T 20 which means the number of test cases Then T lines follow each line starts with a number N 1 N 100000 then N integers followed all the integers are between 1 and 1000000 Output For each test case you should output the answer of each case Sample Input 1 5 1 2 3 4 9 Sample Output 2 8 Problem Problem H H Square NumberSquare Number Description In mathematics a square number is an integer that is the square of an integer In other words it is the product of some integer with itself For example 9 is a square number since it can be written as 3 3 Given an array of distinct integers a1 a2 an you need to find the number of pairs ai aj that satisfy ai aj is a square number Input The first line of the input contains an integer T 1 T 20 which means the number of test cases Then T lines follow each line starts with a number N 1 N 100000 then N integers followed all the integers are between 1 and 1000000 Output For each test case you should output the answer of each case Sample Input 1 5 1 2 3 4 12 Sample Output 2 9 Problem I Problem I Routing TableRouting Table Description In the computer network a Router is a device which finds an optimal way to transmit the datagrams passing through it to it s destination efficiently To accomplish this task the Router maintains a Routing Table The Routing Table stores a variety of relevant data about transmission path In other words the information contained in the table determines the forwarding strategy of a datagram Normally the information in the Routing Table for each routing table entry is First the destination IP Address followed by the number of bits of the sub net mask and finally the forwarded network port number of the destination network For each datagram passing through it the Router compares the datagram s destination IP Address with the information of routing table entry if the network number of the destination IP Address is equals to the network number stored in the routing table entry then the datagram is forwarded to the corresponding port Now give you the Routing Table stored in the Router Then for each datagram travel through this Router give you it s destination IP Address please return which network port will the datagram be forwarded to Input The first line of input contains an integer T indicating the number of test cases T 20 The first line of each test case contains two integers N and M represent the number of entries in the Routing Table and the number of datagram passing through the Router N and M are all less than 100000 Nest N lines each line represent a routing table entry the format of input is IP Address bits of sub net mask and forwarded port number And next M lines each line contain a destination IP Address Please refer to the sample input for more detail Output For each destination IP Address please output the port number that the Router should forward If there are many entry both match to this destination IP Address please output the one that has the longest bits of sub net mask If there are also many entry match please output the one that has the smallest port number If there are none entry match please output the default port 65535 10 Sample Input 1 4 4 192 168 0 0 16 1234 192 168 1 0 24 1235 192 168 1 0 23 1233 192 168 0 0 23 1236 192 168 2 0 192 168 0 0 192 168 1 0 255 255 255 255 Sample Output 1234 1233 1235 65535 11 Problem J Single Round MathProblem J Single Round Math Description Association for Couples Math ACM is a non profit organization which is engaged in helping single people to find his her other half As November 11th is Single Day on this day ACM invites a large group of singles to the party People round together chatting with others and matching partners There are N gentlemen and M ladies in the party each gentleman should only match with a lady and vice versa To memorize the Singles Day ACM decides to divides to divide people into 11 groups each group should have the same amount of couples and no people are left without the groups Can ACM achieve the goal Input The first line of the input is a positive integer T T is the number of test cases followed Each test case contains two integer N and M 0 N M 101000 which are the amount of gentlemen and ladies Output For each test case output YES if it is possible to find a way output NO if not Simple Input 3 1 1 11 11 22 11 Sample Output NO YES NO 12 Problem H Problem H Last HitLast Hit Description Kirito likes playing LOL but he is a noob who never wins His teammates don t want to play with him anymore After practicing with AI for months he thinks it s time to return to the battlefield Now there are N enemy minions in front of him He wants to give them the last hit to get more gold The last hit means that the minion s HP is reduced to or below zero HP 0 after this hit The minions are attacking a defense tower now The tower has enough HP so it will not be destroyed and Kirito will not be attacked Kirito can reduce a minion s HP by Y at each hit while the tower s attack value is X The tower has the same attack speed as Kirito s so if Kirito choose to attack at every opportunity they will take turns hitting the minions Kirito can choose not to attack but the tower will keep attacking until all minions are killed Besides Kirito can choose which minion to hit but the tower will always attack the minion according to the input sequence As an observer of the game you want to know how many last hits can Kirito get at most Suppose the tower attacks first Input The first line of input contains an integer T indicating the number of test cases T 100 The first line of each test case contains three integers N X Y 1 N 1000 0 X Y 109 Next line contains N integers representing the HP of each minion 1 HP 109 Output One line for each test case containing the number of last hits can Kirito get Sample Input 2 3 1 1 1 2 3 3 2 1 3 2 1 Sample Output 13 2 2 14 Problem L Problem L Circle of FriendsCircle of Friends Description Nowadays Circle of Friends is a very popular social networking platform in WeChat We can share our life to friends through it or get other s situation Similarly in real life there is also a circle of friends friends would often get together communicating and playing to maintain friendship And when you have difficulties friends will generally come to help and ask nothing for return However the friendship above is true friend relationship while sometimes you may regard someone