Microsoft Word - A_Battleship_final.docx

Transcription

1 Problem A Battleship Time Limit: 6 seconds You are a member of the prestigious ICPC (Inter-Continental Protecting Corps) and fighting against the evil enemy. The battlefield is represented by an grid. The coordinate of the leftmost and lowest point is 1, 1 and that of the rightmost and highest point is,. The enemy has a fleet of battleships. Each battleship is represented by a line segment whose length is greater than 0 and its endpoints are, and,. Also, its weight is. You can fire a laser cannon times to destroy battleships. Each time you can fire it either horizontally or vertically. If you shoot it vertically, the laser is represented by a line linking, 1 and, and all the battleships which meet the line (including the endpoints) are destroyed. If you shoot it horizontally, the laser is represented by a line linking 1, and, and those which meet the line (including the endpoints) are destroyed. While you are a brave soldier, due to the inefficiency of bureaucracy, you are asked to report the heaviest battleship you just destroyed each time you shoot the laser cannon. Consider the example in Figure 1. There are five battleships on a 5 5 grid. The weight of a battleship is written next to it. Assume that we first shoot the cannon vertically and the laser is a line linking 4, 1 and 4,5. Then two battleships are destroyed: one with weight 4 and the other with weight 5, which is heavier. Therefore we report 5. Next we shoot the cannon horizontally and the laser is a line linking 1,4 and 5,4. Again two battleships are destroyed: one with weight 1 and the other with weight, which is heavier. We report. Note that the battleship with weight 4 is already destroyed at the first shooting. Figure 1. An example of battlefield with five battleships. Given the locations of battleships and your shooting information, write a program which reports the heaviest battleship you destroyed each time you shoot the cannon. 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 integers,, and, the size of the grid, the number of battleships, and the number of times you can shoot the laser cannon, respectively, where 1 1,000,000,000 and 1, 100,000. Each of the following lines contains five integers,,, and separated by a space which represent the endpoints of a battleship, and, (1,,, ) and its weight 1 1,000,000. Also each of the following lines contains two integers and where 1. Either 0 or 1. If 0, you shoot the cannon horizontally and the laser is represented by a ICPC 013 Problem A: Battleship

2 line linking 1, and,. If 1, you shoot it vertically and the laser is represented by a line linking, 1 and,. Output Your program is to write to standard output. Print exactly lines for each test case. Each line should contain an integer value, the weight of the heaviest battleship you destroyed by shooting the laser cannon. If you destroyed nothing, print 0. The following shows sample input and output for two test cases. Sample Input Output for the Sample Input ICPC 013 Problem A: Battleship

3 Problem B Cain Calendar Time Limit: 1 second It was recently revealed by the ICPC excavation team that the Inca Empire was established just after the Cain Empire which was a splendid civilization that flourished in South America. It is believed that the people in the Cain Empire used an interesting odd calendar. In their calendar, a year was represented by :, where and are natural numbers which are less than or equal to and, respectively. The first year, that is, the beginning of the world is represented by 1:1. The second year is represented by :. Let : be the following year of :. If, 1, otherwise 1. Similarly, if, 1, otherwise 1. The last year of their calendar is :. It is said that there was a prophecy which states the world ends in the year :. For example, assume that 10 and 1. The first year is represented by 1:1. The year 1:11 represents the 11 th year, 3:1 represents the 13 th year, and 10:1 represents the 60 th year which is the last year. Given four integers,,, and, write a program that computes the number such that : represents the th year, where : is the last year of the world in the Cain Calendar. 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 a single line containing four integers,,, and 1, 40,000, 1, 1 ), where : is the last year of the world in the Cain Calendar. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer, where the th year is represented by : for and given in the input. If there doesn t exist a year represented by :, print -1. The following shows sample input and output for three test cases. Sample Input Output for the Sample Input ICPC 013 Problem B: Cain Calendar

4 Problem B 카잉달력 Time Limit: 1 second 최근에 ICPC 탐사대는남아메리카의잉카제국이놀라운문명을지닌카잉제국을토대로하여세워졌다는사실을발견했다. 카잉제국의백성들은특이한달력을사용한것으로알려져있다. 그들은 과 보다작거나같은두개의자연수, 를가지고각년도를 : 와같은형식으로표현하였다. 그들은이세상의시초에해당하는첫번째해를 1:1 로표현하고, 두번째해를 : 로표현하였다. : 의다음해를표현한것을 : 이라고하자. 만일 이면 1이고, 그렇지않으면 1이다. 같은방식으로만일 이면 1이고, 그렇지않으면 1이다. : 은그들달력의마지막해로서, 이해에세상의종말이도래한다는예언이전해온다. 예를들어, 10 이고 1라고하자. 첫번째해는 1:1 로표현되고, 11 번째해는 1:11 로표현된다. 3:1 은 13 번째해를나타내고, 10:1 는마지막인 60 번째해를나타낸다. 네개의정수,, 와 가주어질때, : 이카잉달력의마지막해라고하면 : 는몇번째해를나타내는지를구하는프로그램을작성하라. 입력 (Input) 입력데이터는표준입력을사용한다. 입력은 개의테스트데이터로구성된다. 입력의첫번째줄에는입력데이터의수를나타내는정수 가주어진다. 각테스트데이터는한줄로구성된다. 각줄에는네개의정수,, 와 가주어진다 1, 40,000, 1, 1 ), 여기서 : 은카잉달력의마지막해를나타낸다. 출력 (Output) 출력은표준출력을사용한다. 각테스트데이터에대해, 정수 를한줄에출력한다. 여기서 는 : 가 번째해를나타내는것을의미한다. 만일 : 에의해표현되는해가없다면, 즉, : 가유효하지않은표현이면, -1을출력하라. ICPC 013 Problem B: 카잉달력

5 다음은세개의테스트데이터에대한입력과출력의예이다. 입력예제 (Sample Input) 출력예제 (Output for the Sample Input) ICPC 013 Problem B: 카잉달력

6 Problem C Casting Time Limit: 10 seconds Casting is a manufacturing process in which liquid is poured into a cast that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. To ensure that the given object can be mass produced by re-using the same case parts, the cast parts must be removed from the object without destroying either the cast parts or the object. Figure 1. Figure 1(a) shows an object (dark gray) with its cast (light gray). Our goal is to divide the cast into two parts along a straight line through two vertices of the object such that the cast parts can be removed from the object by translation without destroying either the cast parts or the object. In Figure 1(b), the cast is divided into two parts by the straight line through and such that the upper part is removed vertically upward and the lower part is removed vertically downward from the object without destroying either the cast parts or the object. Figure 1(c) and Figure (d) show such divisions by the straight line through and, and by the straight line through and, respectively. However, not every pair of vertices defines such a division. In Figure 1(e), the left part defined by the straight line through and cannot be removed from the object without destroying either the cast parts or the object. Given a convex polygon with vertices in the plane, your program is to find all pairs, of vertices of such that both cast parts of divided by the straight line through, can be removed by translation without destroying either the cast parts or the object. ICPC 013 Problem C: Casting

7 Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with integer, the number of vertices of a convex polygon, where 3 100,000. The next line contains a sequence of integers,, where and are the -coordinate and -coordinate of vertex of, respectively. The coordinates are all integers with 1,000,000,000 1,000,000,000 and 1,000,000,000 1,000,000,000. Vertices,,, of are given in clockwise order along the boundary of. Output Your program is to write to standard output. For each test case, print a line containing the number of pairs, of vertices with such that both cast parts of divided by the straight line through, can be removed by translation without destroying either the cast parts or the object. The following shows sample input and output for three test cases. Sample Input Output for the Sample Input ICPC 013 Problem C: Casting

8 Problem D Dual Priority Queue Time Limit: 3 seconds A dual priority queue is a data structure in which we can insert and delete data like a typical queue. Its difference from a typical queue is that when an item is to be deleted from the queue either an item with highest priority or with lowest priority in it is deleted according to the operation for deletion. There are two operations for the dual priority queue, one for inserting an item into it, the other for deleting an item from it. Deletion operation itself has two parameters: one for deleting an item with highest priority from it, and the other for deleting an item with lowest priority. Suppose there is a dual priority queue which stores integers only. The value of each integer in is considered the priority of itself. Given a list of operations, write a program that processes the operations for and shows the minimum and maximum numbers in after finishing the operations. Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with a line containing an integer 1,000,000, the number of operations for. In the next lines, each line contains either D or I followed by an integer. Operation I means inserting integer into. Note that the same integers can be inserted into. Operation D 1 means deleting the maximum number from. While Operation D 1 is used to delete the minimum number from. If there are two or more maxima (minima) in when the operation is D 1 ( D 1 ), only one of them is deleted. If is empty when the operation is D you can ignore it. Each input to be inserted into is a 3-bit integer. Output Your program is to write to standard output. For each test case, print the maximum and the minimum numbers among those which remain in. The two numbers should be printed in a line separated by a blank. If is empty at the end, print EMPTY. The following shows sample input and output for two test cases. Sample Input 7 I 16 I D -1 D 1 D 1 I 13 Output for the Sample Input EMPTY ICPC 013 Problem D: Dual Priority Queue

9 D -1 9 I -45 I 653 D 1 I -64 I 45 I 97 D 1 D -1 I 333 ICPC 013 Problem D: Dual Priority Queue

10 Problem D 이중우선순위큐 Time Limit: 3 seconds 이중우선순위큐 (dual priority queue) 는전형적인우선순위큐처럼데이터를삽입, 삭제할수있는자료구조이다. 전형적인큐와의차이점은데이터를삭제할때연산 (operation) 명령에따라우선순위가가장높은데이터또는가장낮은데이터중하나를삭제하는점이다. 이중우선순위큐를위해선두가지연산이사용되는데, 하나는데이터를삽입하는연산이고다른하나는데이터를삭제하는연산이다. 데이터를삭제하는연산은또두가지로구분되는데하나는우선순위가가장높은것을삭제하기위한것이고다른하나는우선순위가가장낮은것을삭제하기위한것이다. 정수만저장하는이중우선순위큐 가있다고가정하자. 에저장된각정수의값자체를우선순위라고간주하자. 에적용될일련의연산이주어질때이를처리한후최종적으로 에저장된데이터중최대값과최솟값을출력하는프로그램을작성하라. 입력 (Input) 입력데이터는표준입력을사용한다. 입력은 개의테스트데이터로구성된다. 입력의첫번째줄에는입력데이터의수를나타내는정수 가주어진다. 각테스트데이터의첫째줄에는 에적용할연산의개수를나타내는정수 1,000,000 가주어진다. 이어지는 줄각각엔연산을나타내는문자 ( D 또는 I ) 와정수 이주어진다. I 은정수 을 에삽입하는연산을의미한다. 동일한정수가삽입될수있음을참고하기바란다. D 1 는 에서최대값을삭제하는연산을의미하며, D - 1 는 에서최솟값을삭제하는연산을의미한다. 최대값 ( 최솟값 ) 을삭제하는연산에서최대값 ( 최솟값 ) 이둘이상인경우, 하나만삭제됨을유념하기바란다. 만약 가비어있는데적용할연산이 D 라면이연산은무시해도좋다. 에저장될모든정수는 3-비트정수이다. ICPC 013 Problem D: 이중우선순위큐

11 출력 (Output) 출력은표준출력을사용한다. 각테스트데이터에대해, 모든연산을처리한후 에남아있는값중최대값과최솟값을출력하라. 두값은한줄에출력하되하나의공백으로구분하라. 만약 가비어있다면 EMPTY 를출력하라 다음은두개의테스트데이터에대한입력과출력의예이다. 입력예제 (Sample Input) 7 I 16 I D -1 D 1 D 1 I 13 D -1 9 I -45 I 653 D 1 I -64 I 45 I 97 D 1 D -1 I 333 출력예제 (Output for the Sample Input) EMPTY ICPC 013 Problem D: 이중우선순위큐

12 Problem E Falling Ants Time Limit: 1 second ants are on a stick where some facing right and some facing left. You can assume all ants are so tiny compared to the distance between them, that they can be considered moving points without volume. From a start signal, all ants begin to march in whichever direction they are currently facing. All ants march in a constant speed such as 1mm per second. If two different ants collide on a point, then they bounce and reverse their previous direction. Bouncing and reversing movement does not take any time. When an ant is reaching the end of stick, that ant falls off from the stick and down to the ground. We assume the stick is floating over a floor. Initially all ants are placed in distinct positions, that means no two ants are placed at a same point of the stick. We represent each ant using a signed integer, called an ant ID. The sign of the ant ID denotes the facing direction in the intial state, where '-'('+') means facing the left (right). The absolute value of the ant ID is one of N integers 1,,,. So the absolute values of the ant ID are all distinct. In Figure 1, you can see that there are 6 ants with the signed ID 4, 5, 1, 3,, 6 whose corresponding positions are 5,8,19,,4,5 on a long stick with length 30. The arrow assigned for each ant shows the facing direction in the initial state. The position of the left end is 0, and the position of the right end is 30. It is easy to see that the ant of ID +6 will arrive at the right end of the stick at time 5, and then it falls off the stick at L= Figure 1. You are given information of ants before marching; ant ID and the corresponding position on a stick. If two ants are falling simultaneously from both sides (left and right), then we will break the tie of falling order such that the ant with smaller ID number falls off slightly earlier than the other. Let us give one example for this case. In Figure, if two ants with ID 1, will reach each end simultaneously, the ant of ID 1 will fall off earlier than the ant of ID since 1. So the falling sequence of four ants in Figure is 1,,4,3, i.e., the ant of ID 1 falls off the first and the ant of ID 3 falls off the last Figure. ICPC 013 Problem E: Falling Ants

13 Given a positive integer 1, you should find the -th ant in the falling sequence, i.e., the -th falling ant. 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 three integer numbers, and, where is the total number of the ants, is the length of the stick, and is the falling order we are concerned with. Each line in the following has two integer numbers, and, where is the initial position of the ant. Note that is increasing such as. Note that 1 1, 3 100,000, 10 5,000,000 and 1. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the ID number of the -th falling ant from the stick among all ants. You should not write + symbol if the ant ID is positive. The following shows sample input and output for two test cases which are the description of Figure 1 and. Sample Input Output for the Sample Input - ICPC 013 Problem E:Falling Ants

14 Problem F KCPC Time Limit: 1 second You are participating in the prestigious programming competition called KCPC (Korean Collegiate Programming Contest). You are supposed to solve problems and for each problem you get between 0 and 100 points each time you submit your solution to the server. The submission is done electronically and the server maintains a log in order of submission time. The log includes your team ID, the problem number, and your score. For any problem you can submit your solution several times and you get the greatest points among your submissions. (For a problem, you get 0 points if you make no submission for the problem.) Your final score is simply the sum of the points you earned and your ranking is (the number of teams with higher score than yours) + 1. However, there may be two or more teams with the same score and the tie is broken by applying the ground rules in the following order. Rule 1: If the final scores are the same, the team with the smaller number of submissions in total wins. Rule : If both the final scores and the numbers of submission are the same, the team whose last submission is earlier wins. Assume that no two solutions are submitted at the same time and every team makes at least one submission. Given the log of the server, write a program to compute your ranking. Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with four integers, the number of teams, the number of problems, your team ID, and the number of log entries, where 3, 100, 1, and 3 10,000. In the following m lines, the information on submission is given in order of submission time. Each line contains three integers, team ID, problem number, and score, where 1, 1, and Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain your ranking. The following shows sample input and output for two test cases. Sample Input Output for the Sample Input 1 ICPC 013 Problem F: KCPC

15 ICPC 013 Problem F: KCPC

16 Problem F KCPC 시간제한 : 1 초 당신은유명프로그래밍대회인 KCPC(Korean Collegiate Programming Contest) 에참가하고있다. 이대회에서총 개의문제를풀게되는데, 어떤문제에대한풀이를서버에제출하면그문제에대해 0점에서 100점사이의점수를얻는다. 풀이를제출한팀의 ID, 문제번호, 점수가서버의로그에제출되는시간순서대로저장된다. 한문제에대한풀이를여러번제출할수있는데, 그중최고점수가그문제에대한최종점수가된다. ( 만약어떤문제에대해풀이를한번도제출하지않았으면그문제에대한최종점수는 0점이다.) 당신팀의최종점수는각문제에대해받은점수의총합이고, 당신의순위는 ( 당신팀보다높은점수를받은팀의수 )+1 이다. 점수가동일한팀이여럿있을수있는데, 그경우에는다음규칙에의해서순위가정해진다. 규칙 1. 최종점수가같은경우, 풀이를제출한횟수가적은팀의순위가높다. 규칙. 최종점수도같고제출횟수도같은경우, 마지막제출시간이더빠른팀의순위가높다. 동시에제출되는풀이는없고, 모든팀이적어도한번은풀이를제출한다고가정하라. 서버의로그가주어졌을때, 당신팀의순위를계산하는프로그램을작성하시오. 입력 (Input) 입력데이터는표준입력을사용한다. 입력은 개의테스트데이터로구성된다. 입력의첫번째줄에는테스트데이터의수를나타내는정수 가주어진다. 각테스트데이터의첫번째줄에는팀의개수, 문제의개수, 당신팀의 ID, 로그엔트리의개수 을나타내는 4 개의정수가주어진다. 여기서, 3, 100, 1, 3 10,000이다. 그다음 개의줄에는각풀이에대한정보가제출되는순서대로주어진다. 각줄에는팀 ID, 문제번호, 획득한점수 를나타내는세개의정수가주어진다. 여기서 1, 1, 0 100이다. ICPC 013 Problem F: KCPC

17 출력 (Output) 출력은표준출력을사용한다. 주어진각테스트데이터에대해당신팀의순위를한줄에출력하여야한다. 다음은두개의테스트데이터에대한입력과출력의예이다. 입력예제 (Sample Input) 출력예제 (Output for the Sample Input) 1 ICPC 013 Problem F: KCPC

18 Problem G Moore Machine Time Limit: 5 seconds Moore Machine is a finite state machine of which the output is determined by the states of them. The Moore Machine is named after Edward F. Moore, an American mathematician and computer scientist. The state transtion of a Moore Machine is directed by the given input. For example, if the input is given as aabba, the output of the following Moore Machine is PRETTY. b a b b a a b a 1/P /R 1/P /R 3/E 4/T 5/Y b Figure 1. An example of a Moore Machine a In Figure 1, a circle denotes each state and the label on the arrow denotes the input symbol. One of the states is designated as the start state, which is represented by an arrow with no origin pointing to the state. In this case, the start state is State 1. Each state N with output symbol S is depicted in label N/S. Generally, a Moore Machine can have cycles. However, we can think of a certain kind of Moore Machine which has no cycle at all. Let s call this kind of Moore Machine a series-parallel Moore Machine. Unfortunately, one of the output symbols of a series-parallel Moore Machine is erased. The problem is to find the erased output symbol using the given output of the machine. Note that it is not always possible to find the erased symbol. For example, assume the following series-parallel Moore Machine is given. B A C Figure. An example of a series-parallel Moore Machine In Figure, only the output symbols are shown as labels on states for simplicity. The white circle without any ICPC 013 Problem G: Moore Machine

19 label denotes the state whose output symbol is erased. If the given output of the machine is ADC, then we can determine the erased symbol is D. However, if the output is ABC, we cannot uniquely determine the erased symbol. Or, if the output is given as ABD, it is not a valid output of this machine. Your program should also determine these impossible cases. Since the Moore Machine is reduced to a series-parallel graph, the representation of the machine itself can be defined in a straight-forward way. A Moore Machine consists of a single state, whose output is S, is denoted by S itself. A Moore Machine consists of a single state, whose output symbol is erased, is denoted by the underscore symbol _. The Moore Machine consists of a series of sub-machines, whose descriptions are,,, and respectively, is denoted by. The Moore Machine consists of a parallel connection sub-machines, whose descriptions are,,, and respectively, is denoted by. If a Moore Machine is used as a part of another bigger Moore Machine, the parentheses can be used for enclosing the part. Using this representation, the above Moore Machine can be given as A(B _)C. Write a program determining the erased symbol for a given series-parallel Moore Machine and an output produced by the machine. If the erased symbol cannot be uniquely determined, print the underscore symbol _ instead. If the output cannot be produced from the given machine, print the exclamation mark! instead. Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. From the second line, each test case is given. A test case consists of two lines. The string in the first line of a test case contains the representation of the series-parallel Moore Machine. The second line contains an output of the machine. Only capital English alphabets are used for the output symbols. It is assumed that the outermost connection of the Moore Machine is serial. It is also assumed that there is only one erased symbol in the input machine. The lengths of the input lines of test cases are less than or equal to 100. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the erased output symbol. If it cannot be determined, the underscore symbol should be printed. If the output cannot be produced from the machine, the exclamation mark symbol should be printed. The following shows sample input and output for three test cases. Sample Input 3 A(B _)C ADC A(B D _)C ADC A(B CD(E _)G)E BOY Output for the Sample Input D _! ICPC 013 Problem G: Moore Machine

20 Problem H Networks with Unidirectional Links Time Limit: 1 second There is a multicomputer system that consists of a number of nodes, each with its own memory. The nodes in the system are interconnected via unidirectional communication links. The interconnection network of the system, representing the way in which the nodes are connected together, is modeled as a directed graph, where vertices and directed edges respectively represent nodes and unidirectional links of the network. Figure 1 shows an example of interconnection networks with fourteen nodes interconnected via nineteen unidirectional links. Linear arrays and rings are two of the important computational structures in interconnection networks. In a linear array, each node except for the extreme ends has two neighboring nodes, one to its left and one to its right, where the two nodes at the ends are connected to their single neighbor. If the nodes at either end are connected, we refer to it as a ring. More specifically, the nodes of a linear array with nodes can be numbered from 0 to 1 so that there exists a unidirectional link from node to node +1 for every 0 1. The linear array becomes a ring if we add a unidirectional link from the node 1 to the node 0. To support parallel applications that require one of the two aforementioned computational structures, we needs to decompose the system into several subsystems each of whose interconnection networks is a ring or a linear array. The subsystems should be pairwise node-disjoint, i.e., no two subsystems share a common node. According to a recent report, a ring composed of nodes is worth dollars while a linear array of nodes is worth 1 dollars. This motivates the study on how to decompose the system into subsystems in order to maximize profits. You are to write a program for decomposing the interconnection network of our multicomputer system into rings and/or linear arrays whose total value is the maximum possible. Note that a linear array may have only one node and in that case, its value is zero dollar. Figure 1. An interconnection network and its decomposition into a ring of six nodes (red) and a linear array of eight nodes (green). The total value of this decomposition is thirteen dollars, which is the maximum possible. ICPC 013 Problem H: Networks with Uni...

21 Input Your program is to read from standard input. The input consists of T test cases, where the positive integer T is given in the first line of the input, followed by the description of each test case. The first line of a test case contains two positive integers and, respectively indicating the numbers of nodes and unidirectional links in an interconnection network, in which we assume 1,000 and 50,000. The nodes are indexed 0 to 1. In the following lines, each line contains two integers and, which represent a unidirectional link from node to node. The two integers given in a single line are always separated by a space. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain an integer, representing the maximum total value in dollars that can be achieved by decomposing the interconnection network into rings and/or linear arrays. The following shows sample input and output for three test cases. Sample Input Output for the Sample Input ICPC 013 Problem H: Networks with Uni...

22 Problem I Pickup Game Time Limit: 10 seconds You are playing a computer game called the "Pickup." The rules are as follows: (1) There are a number of horizontal and vertical line segments. (See the figure below.) () You can "Pickup" a pair of line segments by clicking on the crossing made by the pair. (The pair disappears from screen when you do this.) (3) Each line segment is given a weight. (4) When you pick up a pair with weights and, you are given a score of. Figure 1. An Example Screen The first goal is to pick up the most line segments. The second goal is to maximize the total score. That is, if there are more than one way of picking up the most line segments, then you have to find the one with the largest possible score. Write a program, given the specification of an instance of the game, which computes the maximum possible number of line segments that can be picked up and the maximum possible score. 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 integers and, the number of horizontal and vertical line segments, respectively, where 1, 00. Each of the following lines contains five integers,,,,, representing the two endpoints (note, ) and the weight of each horizontal line segment. Also each of the following lines contains an analogous information for each vertical line segment. All coordinate values are positive and are less than or equal to 100,000. The weights are also positive and are less than or equal to 0. Any pair of line segments may share at most one point which is never an endpoint of the line segments. ICPC 013 Problem I: Pickup Game

23 Output Your program is to write to standard output. Print exactly one line containing two integers for each test case. You should output the maximum possible number of line segment pairs that can be picked up, followed by maximum possible score while picking up the most pairs of line segments. The following shows sample input and output for two test cases. Sample Input Output for the Sample Input ICPC 013 Problem I: Pickup Game

24 Problem J Registration Time Limit: 1 second Print out your ICPC team number and team name. Input No input is given for this problem. Output Your program is to write to standard output. Print exactly two lines. The first line should contain your team number, and the second line should contain your full team name, even if your team name contains one or more blanks (a character of ASCII 3). The following shows sample input and output, where the team number is 13 and the team name is Your_ICPC_Team_Name. Notice that no input is given. Sample Input Output for the Sample Input 13 Your_ICPC_Team_Name ICPC 013 Problem J: Registration

25 Problem J Registration Time Limit: 1 second 자신의 ICPC 팀번호와팀이름 (team name) 을그대로출력하는프로그램을작성하시오. Input 이문제는입력이없다. Output 표준출력 (standard output) 으로출력해야한다. 첫줄에자신의팀번호, 둘째줄에팀이름을출력한다. 출력할팀이름은공백문자 (ASCII 코드 3 번인문자 ) 를포함하더라도, 공백문자를포함하여완전한이름을출력해야한다. 다음은팀번호가 13 번, 팀이름 (team name) 이 Your_ICPC_Team_Name 인경우의입출력예제이다. 참고로입력은없으므로주의한다. Sample Input Output for the Sample Input 13 Your_ICPC_Team_Name ICPC 013 Problem J: Registration

26 Problem K Security Time Limit: seconds Today most shopkeepers employ a security service. On a famous street, there are several shops. The shops are protected by a guard belonging to a security company, which is also located on the street. For simplicity, we consider the shops and the company as points on a line, running in order from left to right. The company is located at a point for some, denoted by. Starting at the point, the guard should visit each point at least once a day to protect the shops. For each, it takes, time for the guard to move between and. The latency l of is considered to be the time when the guard first visits after leaving s. Obviously the latency l of the starting point is 0. The guard shall travel to minimize the sum of latencies, which is l. For example, in Figure 1, there are six points to, where the starting point is. Also, 7,, 4,, 1,,,, 9. When the guard first walks right from, the latency l and l are determined as 1 and 3, respectively. If the guard travels as in Figure 1, then the sum of all the latencies is 71. It is the minimum for all possible travels of the guard. Figure 1. Given an integer, the number of points, and the times, for the guard to move between and, 1,, 1, write a program to minimize the sum of latencies of points when traveling from a starting point. Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with an integer (1 100), the number of points. The second line contains an integer (1 ), saying that the -th point is the starting point, that is,. The -th line of the following 1 lines contains an integer (1 15,000,000), representing the time, for 1,, 1. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain the minimum of the sum of latencies for all possible movements of the guard. The following shows sample input and output for two test cases. ICPC 013 Problem K: Security

27 Sample Input Output for the Sample Input ICPC 013 Problem K: Security

28 Problem L Tree Time Limit: 3 seconds A binary tree is a basic and important data structure. As illustrated in Figure 1, a binary tree has a unique root node. Each node has at most two child nodes that are ordered from left to right. Let be a binary tree of nodes. Nodes of have unique id numbers from 1 to. For in Figure 1, the node of id 3 is the root node. The node of id 1 has only right child node, but two nodes of id 4 and id 7 have only left child nodes. Two nodes of id 3 and id 6 have left and right child nodes. The other nodes, called leaf nodes, have no child nodes. Figure 1. A binary tree with 8 nodes. The dashed vertical lines from the nodes are imaginary lines to distinguish their left and right child nodes We have three methods to traverse all nodes of ; preorder, inorder, and postorder traversals. These three traversals are done by the following C-style pseudo codes: For a node of, we denote by. left and. right its left child node and right child node, respectively. If has no left child, then. left is equal to. If has no right child, then. right is equal to. preorder(node ) { printf(id number of ); if (. left ) preorder(. left); if (. right ) preorder(. right); } inorder(node ) { if (. left ) inorder(. left); printf(id number of ); if (. right ) inorder(. right); } postorder(node ) { if (. left ) postorder(. left); if (. right ) postorder(. right); printf(id number of ); } You are now given two lists of id numbers of ; one is the list obtained by preorder traversal and the other is by inorder traversal, i.e., two lists obtained by calling preorder(root node of ) and inorder(root node of ). It is well known that can be reconstructed from these two lists. You need to reconstruct from the preorder and inorder traversal lists of, and output its postorder traversal list which should be the same as the result of postorder(root node of ). ICPC 013 Problem L: Tree

29 For example, if you are given preorder traversal list of 3, 6, 5, 4, 8, 7, 1, and inorder traversal list of 5, 6, 8, 4, 3, 1,, 7, then you should reconstruct the tree as in Figure 1, and output its postorder traversal list, which is 5, 8, 4, 6,, 1, 7, 3. Input Your program is to read from standard input. The input consists of test cases. The number of test cases is given in the first line of the input. Each test case starts with integer, the number of nodes of a rooted and ordered binary tree, where 1 1,000. Nodes of are assumed to have distinct id number from 1 to. The next line contains a list of numbers, i.e., a permutation of 1,,,, which is the preorder traversal list of. The next line contains a list of numbers, i.e., a permutation of 1,,,, which is the inorder traversal list of the same. Two neighboring node id numbers in these lists have a single space between them. Note that a unique binary tree is always constructed from these preorder and inorder traversal lists. Output Your program is to write to standard output. Print exactly one line for each test case. The line should contain a permutation of numbers of 1,,,, which is the same as the postorder traversal list of. The following shows sample input and output for two test cases. Sample Input Output for the Sample Input ICPC 013 Problem L: Tree