ACM-ICPC 2020年上海区域赛正式赛试题.pdf-资料库

第1页 / 共20页

第2页 / 共20页

第3页 / 共20页

第4页 / 共20页

第5页 / 共20页

第6页 / 共20页

第7页 / 共20页

第8页 / 共20页

ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 Problem A. Wowoear Input ﬁle: Output ﬁle: Time limit: Memory limit: standard input standard output 3 seconds 1024 megabytes Wowo is a solo adventurer who completed many dangerous journeys on his own foot in forests, deserts and even glaciers. The Shanghai ICPC (Shanghai Invitational Contest on Programmable Cheating) committee invited Wowo as a tester of their new running trial. The trial can be described as a 2D simple polyline (p1, . . . , pn). In other words, the trial consists of n− 1 line segments (p1, p2), . . . , (pn−1, pn). The line segments do not intersect with each other except that two consecutive line segments (pi, pi+1) and (pi+1, pi+2) intersect at the point pi+1. Any two consecutive segments have diﬀerent directions. The committee wants Wowo to run from p1 to pn along the line segments (p1, p2), . . . , (pn−1, pn) in order. However, Wowo has a smart device that can hack the committee’s system for an interval of time. Wowo is able to choose 2 points a, b on the trial and run directly from a to b along the line segment (a, b). Each of these a and b can be some pi (1 ≤ i ≤ n) and can be some point on some line segment (pi, pi+1) (1 ≤ i < n) as well. Before reaching a and after reaching b, Wowo has to run along the original trial. Wowo does not want to be caught cheating, so he decided that the line segment (a, b) should not intersect or touch any line segment of the trial at any point other than a and b. Help Wowo to choose a and b wisely and output the shortest distance Wowo need to run from p1 to pn using his smart cheating device. Input The ﬁrst line includes a single integer n indicating the number of points on the running trial (2 ≤ n ≤ 200). The i + 1-th line (1 ≤ i ≤ n) contains two integers x and y separated by a single space indicating the coordinates of pi (−1000 ≤ x, y ≤ 1000). It two consecutive line segments (pi, pi+1) and (pi+1, pi+2) intersect at the point pi+1. In other words, holds for any integers i, j satisfying 1 ≤ i < j < n. Here (pi, pi+1) ∩ (pj, pj+1) = (s, t) represents all points on the line segment from s to t including s and t. It is guaranteed that each line segment has nonzero length. In other words, pi = pi+1 for any integer i ∈ [1, n). It is guaranteed that adjacent line segments are not collinear. In other words, for any integer i ∈ [1, n− 2] and any real number λ, pi − pi+1 is not equal to λ(pi+1 − pi+2). Output Output the shortest distance Wowo needs to run. Your answer will be considered correct if its absolute or relative error does not exceed 10−6. Example i = j − 1 {pj} i = j − 1 intersect with each other except ∅ is guaranteed that the line segments do not that standard input standard output 22.099751242242 5 0 0 1 10 2 0 3 10 4 0 Page 1 of 18

ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 Problem B. Mine Sweeper II Input ﬁle: Output ﬁle: Time limit: Memory limit: standard input standard output 1 second 1024 megabytes A mine-sweeper map X can be expressed as an n × m grid. Each cell of the grid is either a mine cell or a non-mine cell. A mine cell has no number on it. Each non-mine cell has a number representing the number of mine cells around it. (A cell is around another cell if they share at least one common point. Thus, every cell that is not on the boundary has 8 cells around it.) The following is a 16×30 mine-sweeper map where a ﬂagged cell denotes a mine cell and a blank cell denotes a non-mine cell with number 0. Given two mine-sweeper maps A, B of size n × m, you should modify at most nm (i.e. the largest 2 2 ) cells in B (from a non-mine cell to a mine cell or vice nonnegative integer that is less than or equal to nm versa) such that the sum of numbers in the non-mine cells in A and the sum of numbers in the non-mine cells in B are the same. (If a map has no non-mine cell, the sum is considered as 0.) If multiple solutions exist, print any of them. If no solution exists, print “-1” in one line. Input The ﬁrst line contains two integers n, m (1 ≤ n, m ≤ 1000), denoting the size of given mine-sweeper maps. The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th row of the mine-sweeper map A. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell. The i-th line of the following n lines contains a length-m string consisting of “.” and “X” denoting the i-th row of the mine-sweeper map B. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell. Output If no solution exists, print “-1” in one line. Otherwise, print n lines denoting the modiﬁed mine-sweeper map B. The i-th line should contain a length-m string consisting of “.” and “X” denoting the i-th row of the modiﬁed map B. A “.” denotes for a non-mine cell and an “X” denotes for a mine cell. Please notice that you need not print the numbers on non-mine cells since these numbers can be determined by the output mine-sweeper map. Page 2 of 18

ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 standard input standard output X.XX .X.. Example 2 4 X..X X.X. X.X. .X.. Note We modify one cell in B. Then the sums of the numbers on non-mine cells in A and B both equal 10. Page 3 of 18

ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 Problem C. Sum of Log standard input standard output 1 second 1024 megabytes Input ﬁle: Output ﬁle: Time limit: Memory limit: Given two non-negative integers X and Y , determine the value of X Y [i&j = 0]log2(i + j) + 1 modulo 109 + 7 where i=0 j=[i=0] • & denotes bitwise AND; • [A] equals 1 if A is true, otherwise 0; • x equals the maximum integer whose value is no more than x. Input The ﬁrst line contains one integer T (1 ≤ T ≤ 105) denoting the number of test cases. Each of the following T lines contains two integers X, Y (0 ≤ X, Y ≤ 109) indicating a test case. Output For each test case, print one line containing one integer, the answer to the test case. Example standard input standard output 3 3 3 19 26 8 17 Note For the ﬁrst test case: 14 814 278 • Two (i, j) pairs increase the sum by 1: (0, 1), (1, 0) • Six (i, j) pairs increase the sum by 2: (0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0) So the answer is 1 × 2 + 2 × 6 = 14. Page 4 of 18

ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 Problem D. Walker Input ﬁle: Output ﬁle: Time limit: Memory limit: standard input standard output 1 second 1024 megabytes As a world-famous traveler, Prof. Pang’s research interest is to travel as many places as possible in his life. We have a segment [0, n]. There are two travelers on it. The ﬁrst one is on position p1 with velocity v1 (which means s/he can walk v1 unit on the segment per second). The second one is on position p2 with velocity v2. From their respective beginning points, travelers can walk on the segment. They cannot walk outside the segment. Whenever they want to change their direction, they can turn around immediately. Please help Prof. Pang to calculate the minimum possible time by which every position of the segment is passed by at least one traveler. Input The ﬁrst line contains one integer test (1 ≤ test ≤ 10000) – the number of test cases. The i-th of the next test lines contains ﬁve numbers n, p1,i, v1,i, p2,i, v2,i (0 < n ≤ 10000, 0 ≤ p1,i, p2,i ≤ n, 0.001 ≤ v1,i, v2,i ≤ 1000). All numbers have at most 3 digits after the decimal point. Output For each test case, we should output one number – the minimum time that every position of the segment is passed by at least one traveler. Your answer is considered correct if its absolute or relative error does not exceed 10−6. Example standard input 2 10000.0 1.0 0.001 9999.0 0.001 4306.063 4079.874 0.607 1033.423 0.847 standard output 5001000.0000000000 3827.8370013755 Page 5 of 18

Problem E. The Journey of Geor Autumn ICPC 2020, Shanghai Site China, Shanghai, Dec, 13, 2020 Input ﬁle: Output ﬁle: Time limit: Memory limit: standard input standard output 1 second 1024 megabytes Once upon a time, there was a witch named Geor Autumn, who set oﬀ on a journey across the world. Along the way, she would meet all kinds of people, from a country full of ICPC competitors to a horse in love with dotabut with each meeting, Geor would become a small part of their story, and her own world would get a little bit bigger. Geor just arrived at the state of Shu where people love poems. A poem is a permutation (a1, . . . , an) of [n]. ((a1, . . . , an) is a permutation of [n] means that each ai is an integer in [1, n] and that a1, . . . , an are distinct.) One poem is good if for all integer i satisfying i > k and i ≤ n, ai > min(ai−k, . . . , ai−1). Here min(ai−k, . . . , ai−1) denotes the minimum value among ai−k, . . . , ai−1. Help Geor calculate how many good poems there are, given n and k. To avoid huge numbers, output the answer modulo 998244353. Input The ﬁrst line contains two integers n and k separated by a single space (1 ≤ n ≤ 107, 1 ≤ k ≤ 107). Output Output only one integer in one linethe number of good poems modulo 998244353. Examples standard input standard output 1 1 2 3 3 2 4 2 1 2 4 10 Page 6 of 18

资料库

ACM-ICPC 2020年上海区域赛正式赛试题.pdf

相关推荐

开发技术

热门标签

最新资料