2023年福建省第三届大学生程序设计竞赛题目.doc

Problem A Solve equationAccept: 111Submit: 229Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionYou are given two positive integers A and B in Base C. For the equation:A=k*B+dWe know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this problem, we want to maximize k.For example, A=123 and B=100, C=10. So both A and B are in Base 10. Then we have:(1) A=0*B+123(2) A=1*B+23As we want to maximize k, we finally get one solution: (1, 23)The range of C is between 2 and 16, and we use a, b, c, d, e, f to represent 10, 11, 12, 13, 14, 15, respectively.InputThe first line of the input contains an integer T (T10), indicating the number of test cases.Then T cases, for any case, only 3 positive integers A, B and C (2C16) in a single line. You can assume that in Base 10, both A and B is less than 231.OutputFor each test case, output the solution “(k,d)” to the equation in Base 10.Sample Input32bc 33f 16123 100 101 1 2 Sample Output(0,700)(1,23)(1,0)Problem B Bin & Jing in wonderlandAccept: 4Submit: 28Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionBin has a dream that he and Jing are both in a wonderland full of beautiful gifts. Bin wants to choose some gifts for Jing to get in her good graces.There are N different gifts in the wonderland, with ID from 1 to N, and all kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I love Jing”, and then the wonderland random drop a gift in front of Bin. The dropping probability for gift i (1iN) is P(i). Of cause, P(1)+P(2)+P(N)=1. Bin finds that the gifts with the higher ID are better. Bin shouts k times and selects r best gifts finally.That is, firstly Bin gets k gifts, then sorts all these gifts according to their ID, and picks up the largest r gifts at last. Now, if given the final list of the r largest gifts, can you help Bin find out the probability of the list?InputThe first line of the input contains an integer T (T2,000), indicating number of test cases. For each test cast, the first line contains 3 integers N, k and r (1N20, 1k52, 1rmin(k,25) as the description above. In the second line, there are N positive float numbers indicates the probability of each gift. There are at most 3 digits after the decimal point. The third line has r integers ranging from 1 to N indicates the finally list of the r best gifts ID. OutputFor each case, output a float number with 6 digits after the decimal points, which indicates the probability of the final list.Sample Input42 3 30.3 0.71 1 12 3 30.3 0.71 1 22 3 30.3 0.71 2 22 3 30.3 0.72 2 2 Sample Output0.0270000.1890000.4410000.343000Problem C Floor problemAccept: 133Submit: 150Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionIn this problem, we have f(n,x)=Floorn/x. Here Floorx is the biggest integer such that no larger than x. For example, Floor1.1=Floor1.9=1, Floor2.0=2.You are given 3 positive integers n, L and R. Print the result of f(n,L)+f(n,L+1)+.+f(n,R), please.InputThe first line of the input contains an integer T (T100), indicating the number of test cases.Then T cases, for any case, only 3 integers n, L and R (1n, L, R10,000, LR).OutputFor each test case, print the result of f(n,L)+f(n,L+1)+.+f(n,R) in a single line.Sample Input31 2 3100 2 100100 3 100 Sample Output0382332Problem D Digits CountAccept: 11Submit: 64Time Limit: 10000 mSecMemory Limit : 262144 KBProblem DescriptionGiven N integers A=A0,A1,.,AN-1. Here we have some operations:Operation 1: AND opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai AND opn (here AND is bitwise operation).Operation 2: OR opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai OR opn (here OR is bitwise operation).Operation 3: XOR opn L RHere opn, L and R are integers.For LiR, we do Ai=Ai XOR opn (here XOR is bitwise operation).Operation 4: SUM L RWe want to know the result of AL+AL+1+.+AR.Now can you solve this easy problem?InputThe first line of the input contains an integer T, indicating the number of test cases. (T100)Then T cases, for any case, the first line has two integers n and m (1n1,000,000, 1m100,000), indicating the number of elements in A and the number of operations.Then one line follows n integers A0, A1, ., An-1 (0Ai16,0i m) if (g = 1)+cnt;return;for (int i = 1; i = acur; +i)gao(cur + 1, g 0 ? i : gcd(g, i);int main() scanf(%d, &m);for (int i = 1; i = m; +i)scanf(%d, a + i);gao(1, -1);cout cnt 0 and x is an integer;(2) Assume x=a0a1.alen-2alen-1(0ai9, a0 is positive). Any a2i+1 is larger or equal to a2i and a2i+2(if exists).For example, 111, 132, 893, 7 are Mountain Number while 123, 10, 76889 are not Mountain Number.Now you are given L and R, how many Mountain Number can be found between L and R (inclusive) ?InputThe first line of the input contains an integer T (T100), indicating the number of test cases.Then T cases, for any case, only two integers L and R (1LR1,000,000,000).OutputFor each test case, output the number of Mountain Number between L and R in a single line.Sample Input31 101 1001 1000 Sample Output954384Problem I StarAccept: 78Submit: 320Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionOverpower often go to the playground with classmates. They play and chat on the playground. One day, there are a lot of stars in the sky. Suddenly, one of Overpowers classmates ask him: “How many acute triangles whose inner angles are less than 90 degrees (regarding stars as points) can be found? Assuming all the stars are in the same plane”. Please help him to solve this problem.InputThe first line of the input contains an integer T (T10), indicating the number of test cases.For each test case:The first line contains one integer n (1n100), the number of stars.The next n lines each contains two integers x and y (0|x|, |y|1,000,000) indicate the points, all the points are distinct.OutputFor each test case, output an integer indicating the total number of different acute triangles.Sample Input130 010 05 1000 Sample Output1Problem J Min NumberAccept: 85Submit: 261Time Limit: 1000 mSecMemory Limit : 32768 KBProblem DescriptionNow you are given one non-negative integer n in 10-base notation, it will only contain digits (0-9). You are allowed to choose 2 integers i and j, such that: i!=j, 1ij|n|, here |n| means the length of ns 10-base notation. Then we can swap ni and nj. For example, n=9012, we choose i=1, j=3, then we swap n1 and n3, then we get 1092, which is smaller than the original n.Now you are allowed to operate at most M times, so what is the smallest number you can get after the operation(s)?Please note that in this problem, leading zero is not allowed!InputThe first line of the input contains an integer T (T100), indicating the number of test cases.Then T cases, for any case, only 2 integers n and M (0n101000, 0M100) in a single line.OutputFor each test case, output the minimum number we can get after no more than M operations.Sample Input39012 09012 19012 2 Sample Output901210921029Problem K TicketsAccept: 14Submit: 50Time Limit: 3000 mSecMemory Limit : 32768 KBProblem DescriptionYou have won a collection of tickets on luxury cruisers. Each ticket can be used only once, but can be used in either direction between the 2 different cities printed on the ticket. Your prize gives you free airfare to any city to start your cruising, and free airfare back home from wherever you finish your cruising.You love to sail and dont want to waste any of your free tickets. How many additional tickets would you have to buy so that your cruise can use all of your tickets?Now giving the free tickets you have won. Please compute the smallest number of additional tickets that can be purchased to allow you to use all of your free tickets.InputThere is one integer T (T100) in the first line of the input.Then T cases, for any case, the first line contains 2 integers n, m (1n, m100,000). n indicates the identifier of the cities are between 1 and n, inclusive. m indicates the tickets you have won. Then following m lines, each line contains two integers u and v (1u, vn), indicates the 2 cities printed on your tickets, respectively.OutputFor each test case, output an integer in a single line, indicates the smallest number of additional tickets you need to buy.Sample Input35 31 31 24 56 51 31 21 61 51 43 21 21 2 Sample Output120