ACM International Collegiate Programming Contest

Size: px

Start display at page:

Download "ACM International Collegiate Programming Contest"

보미 현
6 years ago
Views:

Problem A Castles The country ICPCIA has a river called river of castles. In the past, ICPCIA was divided into two kingdoms called Westeria and Eastania.

All castles of each side of the river are located with an x-monotone increasing and y-monotone decreasing feature.

Then x i < x j and y i > y j if i < j. Also, u i < u j and v i > v j if i < j.

The bridge will be an I-shape(a horizontal segment or a vertical segment) or an L-shape(both of a horizontal segment and a vertical segment).

1 Problem A Castles The country ICPCIA has a river called river of castles. In the past, ICPCIA was divided into two kingdoms called Westeria and Eastania. Two kingdoms were separated by the river which runs in the direction from northwest to southeast. Both kingdoms had competitively built many castles for defense and attack along the riverside. All castles of each side of the river are located with an x-monotone increasing and y-monotone decreasing feature. In other words, let S = {s 1, s 2,, s n } be the castles of Westeria and T = {t 1, t 2,, t m } the castles of Eastania. Let (x i, y i ) (resp. (u i, v i )) be the coordinates of s i (resp. t i ). Then x i < x j and y i > y j if i < j. Also, u i < u j and v i > v j if i < j. Now, the Ministry of Culture and Tourism of ICPCIA decided to build a beautiful bridge connecting two castles on the opposite side of the river. The bridge will be an I-shape(a horizontal segment or a vertical segment) or an L-shape(both of a horizontal segment and a vertical segment). They want to find the location of the bridge such that its length is as small as possible. So, they try to find the closest pair of castles on the opposite side. The distance between two castles s i and t j is computed by x i - u j + y i - v j. Given the information of two sets of castles, write a program to find the distance between the closest castles on the opposite side of the river. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of three lines. The first line of each test case contains two integers. The first integer, n, is the number of castles in the west side of the river, and the integer, m, is the number of castles in the east side of it, where 1 n, m 200,000. The second line of each test case contains 2n integers x 1, y 1, x 2, y 2,, x n, y n, where (x i, y i ) is the coordinate of the i-th castle in the west side of the river and x i < x j and y i > y j if i < j. The last line of each test case contains 2m integers u 1, v 1, u 2, v 2,, u m, v m, where (u i, v i ) is the coordinate of the i-th castle in the east side of the river and u i < u j and v i > v j if i < j. You may assume ICPC 2011 Problem A: Castles

2 that there exists an x-monotone increasing and y-monotone decreasing path which separates two sets of castles. All integers representing the coordinates of castles are between and 10 9, inclusive. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the distance between the closest castles on the opposite side of the river. The following shows sample input and output for two test cases. Sample Input ICPC 2011 Problem A: Castles

3 Problem B 크로스컨트리 크로스컨트리달리기는주자들이자연적인야외의지형에만들어진코스를달리는운동경기이다. 경주 코스는일반적으로 4 에서 12 킬로미터이며, 숲이나넓은땅을통과하는풀과흙으로된지면과언덕과 평평한지형을포함한다. 이경기는주자들의개인성적을매기고, 이를가지고팀의점수를계산한다. 한팀은여섯명의선수로구성되며, 팀점수는상위네명의주자의점수를합하여계산한다. 점수는자격을갖춘팀의주자들에게만주어지며, 결승점을통과한순서대로점수를받는다. 이점수를더하여가장낮은점수를얻는팀이우승을하게된다. 여섯명의주자가참가하지못한팀은점수계산에서제외된다. 동점의경우에는다섯번째주자가가장빨리들어온팀이우승하게된다. 예를들어, 다음의표를살펴보자. 등수 팀 A B C C A C B D A A C A C C A 점수 1 n/a n/a n/a 팀 B 와 D 는선수의수가여섯이아니므로, 점수를받을수없다. 팀 A 의점수는 18 ( ) 이고, 팀 C 의 점수는 18 ( ) 이다. 이경우두팀의점수가같으므로다섯번째로결승점을통과한선수를고려한다, A 팀의다섯번째선수의점수가 C 팀의다섯번째선수의점수보다적으므로 A 팀이우승팀이된다. 모든선수들의등수가주어질때, 우승팀을구하는프로그램을작성하라. 각팀의참가선수가여섯보다 작으면그팀은점수계산에서제외됨을주의하라. 여섯명보다많은선수가참가하는팀은없고, 적어도한 팀은참가선수가여섯이며, 모든선수는끝까지완주를한다고가정한다. 입력입력데이터는표준입력을사용한다. 입력은 T 개의테스트케이스로주어진다. 입력파일의첫번째줄에테스트케이스의수를나타내는정수 T 가주어진다. 두번째줄부터는두줄에하나의테스트케이스에해당하는데이터가주어진다. 각테스트케이스의첫번째줄에는하나의정수 N (6 N 1,000) 이주어진다. 두번째줄에는팀번호를나타내는 N 개의정수 t 1, t 2,, t N 이공백을사이에두고주어진다. 각팀은 1 과 M(1 M 200) 사이의정수로표현된다. ICPC 2011 Problem B: Cross Country

4 출력 출력은표준출력을사용한다. 하나의테스트케이스에대한우승팀의번호를한줄에출력한다. 다음은두개의테스트데이터에대한입력과출력의예이다. Sample Input ICPC 2011 Problem B: Cross Country

5 Problem C Cube of a Graph The cube of a graph is the graph on the vertex set in which two vertices are joined by an edge if their distance in is at most three, where the distance between two vertices in a graph is defined as the number of edges in a shortest path connecting them. A bridge (also known as a cut-edge) of a graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. To study hamiltonian properties of the cubes of connected graphs, the following notions concerned with bridge were suggested in early 1960 s. A bridge of a graph is said to be nontrivial if neither vertex incident with the edge is of degree one, where the degree of a vertex is the number of edges incident to it. See Figure 1. A vertex of is called a pure bridge vertex if each edge incident to the vertex is a nontrivial bridge. A set of three distinct mutually adjacent vertices, each of degree at least three, is called a pure bridge triangle if each edge of that is incident with exactly one of three vertices is a nontrivial bridge Figure 1. A connected graph which has seven nontrivial bridges represented by dotted lines. There are three pure bridge vertices 7, 8, and 15, one pure bridge triangle, and one pure bridge pair. It has been known that the cube of any connected graph is hamiltonian-connected, i.e. every two vertices of are connected by a hamiltonian path. Recently, an ambitious research project on strong hamiltonian properties of graphs was initiated by Prof. Cho, who is a highly considered graph theorist. He introduced a new notion called pure bridge pair to characterize some interesting hamiltonian properties. A set of two adjacent vertices is called a pure bridge pair if both vertices are pure bridge vertices. To support Prof. Cho s research, you are to write an efficient running program to identify all the pure bridge vertices, pure bridge triangles, and pure bridge pairs in a large connected graph. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains two positive integers. The first ICPC 2011 Problem C: Cube of a Graph

6 integer is the number of vertices and the second integer is the number of edges in an input graph, where and. In the following lines, each line contains two integers and which means is an edge of. You may assume that is connected and the vertex set of is. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the numbers of pure bridge vertices, pure bridge triangles, and pure bridge pairs in sequence. The following shows sample input and output for two test cases. Sample Input ICPC 2011 Problem C: Cube of a Graph

7 Problem D DSLR 네개의명령어 D, S, L, R 을이용하는간단한계산기가있다. 이계산기에는레지스터가하나있는데, 이레지스터에는 0 이상 10,000 미만의십진수를저장할수있다. 각명령어는이레지스터에저장된을다음과같이변환한다. 의네자릿수를,,, 라고하자 ( 즉 = (( 10 + ) 10 + ) 10 + 라고하자 ). (1) D: D 는을두배로바꾼다. 결과값이 9999 보다큰경우에는 으로나눈나머지를취한다. 그결과값 ( mod 10000) 을레지스터에저장한다. (2) S: S 는에서 1 을뺀결과을레지스터에저장한다. 이 0 이라면 9999 가대신레지스터에저장된다. (3) L: L 은의각자릿수를왼편으로회전시켜그결과를레지스터에저장한다. 이연산이끝나면레지스터에저장된네자릿수는왼편부터,,, 이된다. (4) R: R 은의각자릿수를오른편으로회전시켜그결과를레지스터에저장한다. 이연산이끝나면레지스터에저장된네자릿수는왼편부터,,, 이된다. 위에서언급한것처럼, L 과 R 명령어는십진자릿수를가정하고연산을수행한다. 예를들어서 = 1234 라면여기에 L 을적용하면 2341 이되고 R 을적용하면 4123 이된다. 여러분이작성할프로그램은주어진서로다른두정수 와 에대하여 를 로바꾸는 최소한의명령어를생성하는프로그램이다. 예를들어서 = 1234, = 3412 라면다음과같이두개의 명령어를적용하면를로변환할수있다 L 2341 L R 4123 R 3412 따라서여러분의프로그램은이경우에 LL 이나 RR 을출력해야한다. 의자릿수로 0 이포함된경우에주의해야한다. 예를들어서 1000 에 L 을적용하면 0001 이되므로결과는 1 이된다. 그러나 R 을적용하면 0100 이되므로결과는 100 이된다. Input 프로그램은표준입력으로입력을받는다. 프로그램입력은 T 개의테스트케이스로구성된다. 테스트케이스개수 T 는입력의첫줄에주어진다. 각테스트케이스로는두개의정수와가공백으로분리되어차례로주어지는데는레지스터의초기값을나타내고는최종값을나타낸다. 와는모두 0 이상 10,000 미만이다. ICPC 2011 Problem D: DSLR

8 Output 여러분의프로그램은표준출력에출력해야한다. 에서로변환하기위해필요한최소한의명령어나열을출력한다. 다음은세개의테스트케이스에대한샘플입출력이다. Sample Input LL L DDDD ICPC 2011 Problem D: DSLR

9 Problem E Goldbach s Conjecture A natural number is called a prime number (or a prime) if it is bigger than 1 and has no divisors other than 1 and itself. For example, 5 is prime, since no number except 1 and 5 divides it. On the other hand, 6 is not a prime since Goldbach's conjecture is one of the famous unsolved problems in number theory and in all of mathematics. It states: Every even integer greater than 2 can be expressed as the sum of two primes. Such a number is called a Goldbach number. Expressing a given even number as a sum of two primes is called a Goldbach partition of the number. For example, 4 2 2, 6 3 3, 8 3 5, or , , or Note that Goldbach partition has been found for any even interger n less than Given any even integer n greater than 2, write a program that prints the two primes of the Goldbach partition of n. If there are more than one Goldbach partitions of n, find a partition such that the difference of the two primes of it is minimized. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case consists of an even integer n ( 4 n 1,000 ). Output Your program is to write to standard output. For each test case, find the Goldbach partition as described above, and print its two primes in non-decreasing order with one blank between them. The following shows sample input and output for two test cases. Sample Input ICPC 2011 Problem E: Goldbach s Conjecture

10 Problem F Number Link Number Link is a type of logic puzzle involving finding paths to connect numbers in a grid. The player has to pair up all the matching numbers on the grid with continuous lines (or paths). The lines cannot branch off or cross over each other, and the numbers have to fall at the end of each line (i.e., not in the middle). Also the lines should pass by each cell in the grid exactly once. An example of Number Link with its solution is shown below. (a) Initial configuration (b) Solution Figure 1. An example of a Number Link Puzzle Here we concentrate on the case that a pair of only one numbers, say number 1, is located on the grid. Also for the given grid, and are both even. An example for this case is shown in the following Figure 2. Figure 2. An example in which a pair of number 1 s exists Given an grid where a pair of number 1 s is located, write a program to find a path which connects the number 1 s and passes by each cell exactly once. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains two even integers and, the dimensions of the grid, where. Each of the second and third lines of each test case ICPC 2011 Problem F: Number Link

11 contains two integers and j, representing the location of one of the number 1 s in the grid. Here the location of the number 1 denotes the cell of the -th row and the -th column in the grid. Output Your program is to write to standard output. For each test case, if there is no path connecting the number 1 s, then print. Otherwise, print, and in the next lines, print the two integers and, representing the cell on the path. Here the end cells of the path are the locations of the number 1 s, that is, print the locations of the number 1 s in the first line and the last line, respectively. The following shows sample input and output for two test cases. Sample Input ICPC 2011 Problem F: Number Link

12 Problem G Stains Taeyeon has been using a rectangular carpet for a long time, thus the carpet has lots of indelible stains. Taeyeon decided to repair it by covering the stains with additional carpet patches. The shape of the patches is a diamond, which is a 45 - rotated axis-aligned square, as illustrated in Figure 1 below. The cost of a patch is proportional to its area. Taeyeon wants to minimize the total cost of the patches used to cover the stains, i.e., minimize the sum of area of the patches used. Moreover, Taeyeon is full of artistic sensitivity, so she wants some pattern of the patches. For this, she will align the centers of the patches on a line as illustrated in Figure 1. Patches can overlap each other. Figure 1. Stains are black dots and the centers of the patches are the crosses. The thick line is the x-axis. The figure above shows an example in which the nine stains can be covered by three patches with the minimum cost of. The stains are given with integer coordinates. You should find a set of diamond-shape patches such that (1) every stain must be contained in the interior or on the boundary of some patch, (2) the centers of the patches must be on -axis, and (3) the sum of area of the patches used must be minimized. You can assume that stains are all distinct and no stains lie on the -axis. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with integer, the number of stains, where. Each of the following lines contains two integers, representing -coordinate and -coordinate of the stains between and, inclusive. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain a real value, the minimum area of the patches used to cover the stains; you output only 1 digit after decimal point, simply ignore the ones from the 2 nd digit after decimal point. ICPC 2011 Problem G: Stains

13 The following shows sample input and output for two test cases. Sample Input ICPC 2011 Problem G: Stains

14 Problem H 연습시즌 두프로야구팀 X 와 Y 가 7 군데의도시를정해진순서로방문하면서연습시즌을보낸다. 7 개의도시는 {, 로표시되어있다. 두팀 X 와 Y 가연습시즌을시작하는날과마치는날은반드시동일해야한다. 이연습시즌동안각팀은도시를방문해서연습훈련을하거나또는한호텔을정해서하루종일휴식 ( 휴식일 ) 을가진다. 각팀이방문해야하는도시들의순서는이미각각정해져있지만그중간에쉬는휴식일은따로정해져있지않다. 따라서방문해야할도시들의순서는바꿀수없지만그중간에휴식일은상황을봐가면서적절히선택할수있다. 예를들어연습시즌동안한팀이방문해야할도시의순서가 S=<,,,,,,, > 와같다면각팀은그중간에휴식일을넣을수있다. 예를들어아래두개의일정은 S 에중간중간휴식일이들어간상태의새로운일정의예 S1 과 S2 를보여주고있다. S1=<,, R,,, R, R,,,, R, > S2=<,,,, R,, R,,, > 연습시즌에는많은비용이든다. 한팀이야구장을사용할때내야하는경비는 7 개도시모두동일하게 C 원이다. 만일두팀 X 와 Y 가같은야구장을사용해도전체비용은 C 이므로각팀은각각 C/2 만큼의경비만을내면되기때문에약간이득이된다. 즉두팀이다른야구장에서따로훈련을하면각각 C 만큼의경비를내어전체비용은 2C 이지만같은야구장을쓰면각각 C/2 만내면되기때문에전체비용은 C 가된다. 그런데각팀이호텔에서휴식일로쉴때의경비계산은좀다르다. 연습시즌동안각팀은원기회복을위하여중간에휴식일을가질수있다. 이경우에는한호텔을모두빌어서전체가쉰다. 그런데호텔에서는야구팀이호텔전체를빌려서사용하기때문에일단호텔전체를빌릴경우독점사용비로 D 만큼요구한다. 그리고사용하는기간에따라서추가로하루당 d 만큼의비용을요구한다. 즉야구팀이어떤호텔에 w 일간연속해서머물경우 D+w d 만큼지불해야한다. 예를들어전체간 D=4, d=1 인경우에한팀이 5 일간연속해서호텔에머물경우전체비용은 4 + 1*5 = 9 만큼의비용을내야한다. 만일 5 일을각각따로따로떨어진날로하루씩머물경우에는모두 5 번의독점료를내야하고또한 5 일동안의사용료를내야하므로전체비용은 5*4+5*1=25 가된다. 두팀의도시방문순서가주어졌을때특별한변화없이각각그대로방문하는연습시즌일정을짜면아래표 - 1 과같아진다. 이경우 Y 팀은앞의가정대로연습시즌의처음과끝을 X 팀과맞추기위해서마지막이틀, 7 일과 8 일째날은휴식일로사용하고있다. X 표 -1. 간단한일정 -A Day1 Day 2 Day 3 Day 4 Day 5 Day 6 Day7 Day8 Y R R 만일야구장사용료가 C=3 이고, 호텔독점료 D=4, 일일사용료 d=1 일때, 위표 -1 에있는일정대로하면 X 와 Y 가지불해야하는전체비용은아래표 -2 와같다. ICPC 2011 Problem H: Training Season

15 표 2. 일정-A 에따라서연습시즌을지낼경우비용. Day Day1 Day2 Day3 Day4 Day5 Day6 Day7 Day8 X Y R R X 비용 Y 비용 합 따라서 X 와 Y 가지불해야하는전체비용은 6* = 48 이다. 일정 -A 와조금다른다른일정을잡아보자. 만일아래표 -3 과같이 Y 팀의일정에휴식일을적절히넣어서조정하면두팀이야구장을공동으로쓰는날이늘어나므로전체비용을줄일수있다. 표 3. 일정-B Day Day1 Day2 Day3 Day4 Day5 Day6 Day7 Day8 X Y R R X 비용 Y 비용 Total 따라서전체비용은 = 34 이되어일정 -A 에따른비용에비해서 = 14 만큼절약할수있다. 그러나최적의일정은 C, D 그리고 d 값에따라서다르게결정될수있음을유의해야한다. 여러분은 X 와 Y 팀의방문도시일정이주어졌을때두팀이지출해야하는비용의합을최소로가는가장좋은일정을구하고그전체비용을출력하는것이다. 아래입출력의예를잘살펴보면이문제를잘이해할수있을것이다. Input 입력은표준입력으로들어온다. 입력은모두 T 개의테스트케이스가있다. 테스트케이스의전체개수는첫줄에주어진다. 각테스트케이스는 3 개의줄로이루어져있다. 첫라인에는 C, D, d 를나타내는정수값이차례대로하나의공백을두고나타난다. 각숫자는모두 10 이하의양의정수이다. 그다음이어지는두개의줄에는방문해야할도시의순서가하나의공백을두고나타난다. 각도시는 1 부터 7 까지의정수로표시된다. 그리고그끝은숫자 0 으로표시되어있다. 방문해야할도시의개수 N 은 2 < N < 100 로제한되어있다. Output 여러분의프로그램은표준출력에써야한다. 각테스트케이스에해당되는정답, 즉연습시즌을마칠수있는최소의비용 (X 와 Y 비용의합 ) 을출력해야한다. 다음은다섯개의테스트데이터에대한입력과출력의예이다. Sample Input ICPC 2011 Problem H: Training Season

16 ICPC 2011 Problem H: Training Season

17 Problem I 두수의합 여러개의서로다른정수 S = {a 1, a 2,, a n } 와또다른정수 K 가주어졌을때, S 에속하는서로다른두개의정수의합이 K 에가장가까운두정수를구하시오. 예를들어, 10 개의정수 S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0} 가주어졌을때, K = 8 에그합이가장가까운두정수는 {12, -4} 이다. 또한 K = 4 에그합이가장가까운두정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의다섯종류가있다. 여러개의서로다른정수가주어졌을때, 주어진정수들중에서서로다른두정수의합이주어진또다른정수에가장가까운두정수의조합의수를계산하는프로그램을작성하시오. 입력프로그램은표준입력으로입력을받는다. 프로그램입력은 t 개의테스트케이스로구성된다. 입력의첫번째줄에테스트케이스의개수를나타내는정수 t 가주어진다. 두번째줄부터두줄에한개의테스트케이스에해당하는데이터가주어진다. 각테스트케이스의첫번째줄에는두개의정수 n 과 K (2 n 1,000,000, K 10 8 ) 가한개의공백을사이에두고입력된다. 두번째줄에는 n 개의정수가하나의공백을사이에두고주어지며, 각정수의최대값은 10 8 이고, 최소값은 이다. 잘못된데이터가입력되는경우는없다. 출력출력은표준출력 (standard output) 을사용한다. 입력되는테스트케이스의순서대로다음줄에이어서각테스트케이스의결과를출력한다. 각테스트케이스의출력되는첫줄에입력으로주어진 n 개의정수들중에서서로다른두정수의합이주어진또다른정수 K 에가장가까운두정수의조합의수를출력한다. 다음은네개의테스트데이터에대한입력과출력의예이다. Sample Input ICPC 2011 Problem I: 두수의합

18 Problem J Widest Path We are given a graph which represents connections between nodes in the computer network, and the weight of an edge represents the bandwidth of a connection between two nodes. For the efficient data transmission between two nodes in the network, we are interested in finding a path between two nodes that has wide bandwidth. The bandwidth of a path is the minimum weight of an edge in the path. The widest path problem is to find the path between two nodes that has the maximum possible bandwidth. For example, the widest path from node 1 to node 4 in Figure 1 has bandwidth 25, and passes through node 3 and node 2. The widest path from node 6 to node 3 has bandwidth 30, and passes through node 5. Figure 1. Example of a computer network Given two nodes in a graph, write a program which determines the bandwidth of the widest path between two nodes. Input Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Each test case starts with a line containing four integers n, m, s and t for a connected graph, where n represents the number of nodes and m ( ) represents the number of edges, s and t represents the two nodes(nodes are numbered from 1 to n). In the following m lines, the bandwidth of the edges are given; each line contains three integers, u, v, and b, where b ( ) is the bandwidth of a connection between two nodes u and v. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the bandwidth of the widest path between two nodes s and t. The following shows sample input and output for two test cases. ICPC 2011 Problem J: Widest Path

19 Sample Input ICPC 2011 Problem J: Widest Path

sna-node-ties

sna-node-ties Node Centrality in Social Networks Nov. 2015 Youn-Hee Han http://link.koreatech.ac.kr Importance of Nodes ² Question: which nodes are important among a large number of connected nodes? Centrality analysis