 Jumping Hero

A software house has decided to create a computer game, where the hero must find its way from a start position to the end position, through a labyrinth. In the labyrinth, some cells contain magic fountains that can be used to get superpowers an infinite number of times. Whenever the hero enters a cell with a magic fountain, he gets superpowers.
Usually, our hero moves in the labyrinth one cell left/right/up/down at a time (to an empty cell). With superpowers, the hero jumps to an empty cell N positions to the left/right/up/down. The superpower lasts for M jumps, and the hero can change its jumping direction after each jump. A jump is allowed if the end cell of the jump is within the map and it is not a wall �C thus, the hero can jump over walls. If the hero jumps to a cell with a new magic fountain, the hero gets the superpowers of the new magic fountain, and the remaining effect of the previous magic fountain is cancelled. If the hero jumps to the cell where he obtained its current superpowers, no effect occurs (i.e., the hero gets no additional superpowers). When the current superpower ends, the hero proceeds its normal onecell movement. If, after getting superpowers in some fountain, the hero cannot move to any cell, he looses his superpowers and returns to his previous cell. To reach the end position, the hero must move to the end cell or finish one jump in the end cell.
Given the labyrinth map compute the minimum number of moves/jumps from the start position to the end position.
Input
A positive integer P in a single line followed by a sequence of P labyrinth maps. The first line of each labyrinth map contains two positive integers, L and C, separated by an empty space, with L the number of lines and C the number of columns in the map. L and C are both lesser than 300. The following L lines of the input contain C integers each that define the cells of the map (separated by a empty space). Each integer, i, must be interpreted as follows: i = 0 represents a wall; i = 1 represents an empty cell (where the hero can move into); i = M*10+N represents an empty cell with a magic fountain that makes the hero jump M times to the cell that is N positions to the left/right/up/down of the current cell. M ranges from 1 to 5 and N ranges from 2 to 6. The maximum number of magic fountains in a map is 5,000. The two last lines of the input define the coordinates of the start position and end position (coordinates consist of two integers, denoting the line and column respectively, starting from 0).
Output
The output consists of one single line that contains an integer with the minimum number of moves/jumps, from the start position to the end position. If it is impossible to reach the end position, the output should be a single line containing IMPOSSIBLE.
Sample Input
1
8 8
0 1 1 1 1 1 1 1
0 1 0 0 1 13 1 1
0 1 32 1 1 1 0 0
0 1 1 0 1 1 1 0
0 1 1 0 0 0 0 0
0 1 1 1 1 1 1 0
0 1 0 0 1 1 1 0
0 1 1 1 1 1 1 0
1 7
5 4
Sample Output14
Fiber Communications _course
20171016Description Farmer John wants to connect his N (1 <= N <= 1,000) barns (numbered 1..N) with a new fiberoptic network. However, the barns are located in a circle around the edge of a large pond, so he can only connect pairs of adjacent barns. The circular configuration means that barn N is adjacent to barn 1. FJ doesn't need to connect all the barns, though, since only certain pairs of cows wish to communicate with each other. He wants to construct as few connections as possible while still enabling all of these pairs to communicate through the network. Given the list of barns that wish to communicate with each other, determine the minimum number of lines that must be laid. To communicate from barn 1 to barn 3, lines must be laid from barn 1 to barn 2 and also from barn 2 to barn 3(or just from barn 3 to 1,if n=3). Input * Line 1: Two integers, N and P (the number of communication pairs, 1 <= P <= 10,000) * Lines 2..P+1: two integers describing a pair of barns between which communication is desired. No pair is duplicated in the list. Output One line with a single integer which is the minimum number of direct connections FJ needs to make. Sample Input 5 2 1 3 4 5 Sample Output 3
The Alphabet Game _course
20171015Description Little Dara has recently learned how to write a few letters of the English alphabet (say k letters). He plays a game with his little sister Sara. He draws a grid on a piece of paper and writes p instances of each of the k letters in the grid cells. He then asks Sara to draw as many sidetoside horizontal and/or vertical bold lines over the grid lines as she wishes, such that in each rectangle containing no bold line, there would be p instances of one letter or nothing. For example, consider the sheet given in Figure 1, where Sara has drawn two bold lines creating four rectangles meeting the condition above. Sara wins if she succeeds in drawing the required lines. Dara being quite fair to Sara, wants to make sure that there would be at least one solution to each case he offers Sara. You are to write a program to help Dara decide on the possibility of drawing the right lines. ![](http://poj.org/images/1231_1.jpg) Input The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case consists of two integers k (1 <= k <= 26), the number of different letters, and p (1 <= p <= 10), the number of instances of each letter. Followed by the first line, there are k lines, one for each letter, each containing p pairs of integers (xi, yi) for 1 <= i <= p. A pair indicates coordinates of the cell on the paper where one instance of the letter is written. The coordinates of the upper left cell of the paper is assumed to be (1,1). Coordinates are positive integers less than or equal to 1,000,000. You may assume that no cell contains more than one letter. Output There should be one line per test case containing a single word YES or NO depending on whether the input paper can be divided successfully according to the constraints stated in the problem. Sample Input 2 3 2 6 4 8 4 4 2 2 1 2 3 2 4 3 3 1 1 3 1 5 1 2 1 4 1 6 1 2 2 4 2 8 1 Sample Output YES NO
Partition a Matrix _course
20171017Description Given an M * N matrix consisted of nonnegative elements, you may partition it into three parts with two straight line segments. The line segments cannot go through any element of the matrix and they must be parallel to the row or the column of the matrix, but they need not to be parallel to each other. Each of the three parts is a nonempty matrix, which means it contains at least one element. We define the value of a matrix as the sum of all elements in it. We denote the values of the three remaining matrices as X, Y, Z, and the balance degree as X  Y + Y  Z + Z  X, where . means the absolute value. Among all ways of partition, there is one, which has the least balance degree. Your task is to decide what the least balance degree is. Input The input will consist of several test cases. For each test case, two integers M and N are given in the first line, indicating the number of rows and columns of the matrix; each of the following M lines contains N integers, indicating the matrix. The input is terminated by a single line with two zeros. You may assume that 2 <= M, N <= 500 and all elements of the matrix are integers in the range [0, 65535]. There may be some blank lines between test cases. Output For each matrix of the input, print a line containing the least balance degree. Sample Input 3 3 9 8 7 6 5 4 3 2 1 0 0 Sample Output 10
Ticket to Ride _course
20170523Problem Description Ticket to Ride is a board game for up to 5 players. The goal of the game is to set up train lines (and to thwart the opponents’ attempts at setting up their train lines). At the beginning of play, each player is assigned four train lines. A player may choose to discard as many of these four assignments as she likes. Each assignment has a score, corresponding to its difficulty (so, typically, a train line between e.g. Stockholm and Tokyo would be worth more than a train line between e.g. Stockholm and Utrecht). At the end of the game, each player gets points for the assignments that they have successfully completed, and penalty points for the assignments that they have failed to complete. An assignment consists of a pair of cities that are to be connected by a series of shorter railway routes. A route can be claimed (for a certain cost associated with the route), but things are complicated by the fact that there is only a limited number of routes, and once a player claims a route, none of the other players can claim it. A player has successfully set up a train line between two cities if there is a path between the two cities using only routes that have been claimed by this player. For simplicity, we will ignore all additional aspects of the game (including the actual process of claiming routes and additional ways to score points). For instance, if your assignment is to connect Stockholm and Amsterdam in the Figure above, you would probably want to claim the routes between Stockholm and Copenhagen, and between Copenhagen and Amsterdam. But if another player manages to claim the route between Copenhagen and Stockholm before you, your train line would have to use some other routes, e.g. by going to Copenhagen via Oslo. In this problem, we will consider the rather bold strategy of trying to complete all four assignments (typically, this will be quite hard). As a preliminary assessment of the difficulty of achieving this, we would like to calculate the minimum cost of setting up all four lines assuming that none of the other players interfere with our plans. Your job is to write a program to determine this minimum cost. Input The input consists of several (at most 20) games to be analyzed. Each game starts with two integers 1 <= n <= 30, 0 <= m <= 1 000, giving the number of cities and railway routes in the map, respectively. Then follow n lines, giving the names of the n cities. City names are at most 20 characters long and consist solely of lower case letters (’a’’z’). After this follow m lines, each containing the names of two different cities and an integer 1 <= c <= 10 000, indicating that there is a railway route with cost c between the two cities. Note that there may be several railway routes between the same pair of cities. You may assume that it is always possible to set up a train line from any city to any other city. Finally, there will be four lines, each containing the names of two cities, giving the four train line assignments. The input is terminated by a case where n = m = 0. This case should not be processed. Output For each game, output a single line containing a single integer, the minimum possible cost to set up all four train lines. Sample Input 10 15 stockholm amsterdam london berlin copenhagen oslo helsinki dublin reykjavik brussels oslo stockholm 415 stockholm helsinki 396 oslo london 1153 oslo copenhagen 485 stockholm copenhagen 522 copenhagen berlin 354 copenhagen amsterdam 622 helsinki berlin 1107 london amsterdam 356 berlin amsterdam 575 london dublin 463 reykjavik dublin 1498 reykjavik oslo 1748 london brussels 318 brussels amsterdam 173 stockholm amsterdam oslo london reykjavik dublin brussels helsinki 2 1 first second first second 10 first first first first second first first first 0 0 Sample Output 3907 10
Street Directions _course
20171016Description According to the Automobile Collision Monitor (ACM), most fatal traffic accidents occur on twoway streets. In order to reduce the number of fatalities caused by traffic accidents, the mayor wants to convert as many streets as possible into oneway streets. You have been hired to perform this conversion, so that from each intersection, it is possible for a motorist to drive to all the other intersections following some route. You will be given a list of streets (all twoway) of the city. Each street connects two intersections, and does not go through an intersection. At most four streets meet at each intersection, and there is at most one street connecting any pair of intersections. It is possible for an intersection to be the end point of only one street. You may assume that it is possible for a motorist to drive from each destination to any other destination when every street is a twoway street. Input The input consists of a number of cases. The first line of each case contains two integers n and m. The number of intersections is n (2 <= n <= 1000), and the number of streets is m. The next m lines contain the intersections incident to each of the m streets. The intersections are numbered from 1 to n, and each street is listed once. If the pair i j is present, j i will not be present. End of input is indicated by n = m = 0. Output For each case, print the case number (starting from 1) followed by a blank line. Next, print on separate lines each street as the pair i j to indicate that the street has been assigned the direction going from intersection i to intersection j. For a street that cannot be converted into a oneway street, print both i j and j i on two different lines. The list of streets can be printed in any order. Terminate each case with a line containing a single `#' character. Note: There may be many possible direction assignments satisfying the requirements. Any such assignment is acceptable. Sample Input 7 10 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 2 5 3 6 7 9 1 2 1 3 1 4 2 4 3 4 4 5 5 6 5 7 7 6 0 0 Sample Output 1 1 2 2 4 3 1 3 6 4 3 5 2 5 4 6 4 6 7 7 5 # 2 1 2 2 4 3 1 4 1 4 3 4 5 5 4 5 6 6 7 7 5 #
Rooted Trees Isomorphism _course
20171014Description Isomorphism is the problem of testing whether two graphs are really the same. Suppose we are given a collection of graphs and must perform some operation on each of them. If we can identify which of the graphs are duplicate, they can be discarded so as to avoid redundant work. First we have to explain what is meant when we say two graphs are the same. Two labeled graphs G1 = (V1,E2) and G2 = (V2,E2) are identical when we can find a mapping f of the vertices of G1 to the vertices of G2 such that (x, y) is an edge of G1 if and only if (f(x), f(y)) is an edge of G2. Such a mapping is called an isomorphism. No efficient algorithm is known for the general graph isomorphism problem, but the problem is easier to determine whether two trees are isomorphic to each other. In Figure 7, it is not hard to verify that tree T1 is isomorphic to tree T3, but T1 is not isomorphic to T2. ![](http://poj.org/images/1343_1.jpg) You are given a collection of k trees C = {T1, T2, ... , Tk} such that each Ti has exactly n nodes. The objective of the problem is to partition these trees into isomorphic (equivalent) classes such that any two trees within the same isomorphic class are isomorphic to each other. A naive method of enumerating all possible mapping functions would require generating all possible n! different mappings. What resulted is a very timeconsuming O(n!) time algorithm just to test two trees. You need to figure out a somehow clever way for solving the problem. Input A collection of k (nnode) trees C = {T1, T2, ... , Tk}. The inputs are just a list of integers. The first 2 integers (in a single line) represent the number of trees, k, and the size of each tree, n. Note that k can be as large as 150 and n can be as large as 100. After the two integers, there will be k lines representing the edge sets for each tree Ti; each line contains exactly n1 pairs of integers, representing the n1 (directed) edges of each tree. Thus, there are totally 2n2 integers for each tree, and the total input will be 2k(n1) integers except the first two parameters. Each tree is indexed by their appearance ordering; that is, the first line represents the tree T1, the second line is T2, ... , etc, and the last (kth) line is just Tk. Output For the given collection of trees, partition these trees into isomorphic (equivalent) classes such that any two trees within the same isomorphic class are isomorphic to each other. For each isomorphic class, output the indices of these isomorphic trees in a line. Suppose that there are m isomorphic classes, you need to print out m lines. For example, a line t1 = t2 = ... = tp; represents an isomorphic class of size p such that two trees Tti and Ttj , 1<=i, j <=p, are isomorphic to each other. For each line, output indices of those isomorphic trees in increasing order; that is, t1 < t2 < ... < tp. Further, print out these m isomorphic classes by their increasing lexical ordering; that is, by the ordering of their first indices. For example, suppose that there are 4 isomorphic classes {4, 2, 7}, {5, 1, 3}, {8, 9}, {6}. The output shall be 1 = 3 = 5 ; 2 = 4 = 7 ; 6 ; 8 = 9 ; Sample Input 3 7 7 2 7 1 7 6 2 3 1 4 6 5 7 2 7 1 2 3 1 4 1 5 5 6 4 3 3 2 4 1 1 7 5 6 4 5 Sample Output 1 = 3 ; 2 ;
Storehouse _course
20171013Description Advanced Cargo Movement, Ltd. owns a big storehouse in which a lot of various goods is stored. The storehouse has limited number of bays where a cargo can be loaded. Each day, trucks come to the bays, load their cargo (each truck loads just one type of goods) and leave for the shops. In order to speedup the loading, storekeepers move the goods to the bay in advance. Since the exact quantity of cargo to be loaded is not known beforehand, the storekeepers must prepare more goods than needed and the leftover goods is then returned to the store. Thus, it is useful when the next truck coming to the bay loads the same goods as the previous one, because it saves unnecessary movement of cargo. The capacity of trucks is much smaller than the capacity of the bay, therefore, any number of trucks can be served from one bay without reloading, as long as they want to load the same type of goods. Your task is to organize which type of goods will be prepared in which bay, so that storekeepers must move the unloaded goods back to the storehouse as few times as possible. At the beginning of each day, no goods is prepared in any bay. The goods left in bays at the end of the day is not counted to the number of moves needed. Input The first line of the input contains the number of test cases to solve. Each test case starts with the line containing three integer numbers, B, G, N, 1 <= B <= 1 000, 1 <= G <= 1 000 000, 1 <= N <= 1 000 000, separated by a single space. B is the number of bays in the storehouse, G the number of types of goods stored in the storehouse and N the number of trucks coming to the storehouse. The test case continues by N lines. On the ith line, there is a number ti, 1 <= ti <= G, specifying the type of goods the ith truck wants to load. Output For each test case, your program should output "Case X:" on the first line, where X is the case number starting with one. Then N lines follow. For each i, 1 <= i <= N, the ith line must contain one of the following strings: "NO ACTION"  when no action needs to be performed before the arrival of the truck i(i.e., the goods ith truck wants to load is already at some bay), or "LOAD b g"  when the goods with number g should be moved to the bay b before the ith truck arrives. The goods currently present at the bay b is automatically moved back to the storehouse. Each time some truck arrives, the goods it wants to load must be prepared at some bay. Assume that any truck leaves the bay before the next one arrives, i.e., only a single truck is served at a time. The number of "LOAD" actions should be as small as possible. If there are more solutions with the same number of "LOAD" actions, choose any one you want. Outputs for different test cases should be separated by a blank line. Sample Input 2 2 4 5 1 2 1 4 1 3 3 3 1 3 2 Sample Output Case 1: LOAD 1 1 LOAD 2 2 NO ACTION LOAD 2 4 NO ACTION Case 2: LOAD 1 1 LOAD 2 3 LOAD 3 2
Alignment of Code _course
20170110Description You are working in a team that writes Incredibly Customizable Programming Codewriter (ICPC) which is basically a text editor with bells and whistles. You are working on a module that takes a piece of code containing some definitions or other tabular information and aligns each column on a fixed vertical position, while keeping the resulting code as short as possible, making sure that only whitespaces that are absolutely required stay in the code. So, that the first words on each line are printed at position p1 = 1; the second words on each line are printed at the minimal possible position p2, such that all first words end at or before position p2  2; the third words on each line are printed at the minimal possible position p3, such that all second words end at or before position p3  2, etc. For the purpose of this problem, the code consists of multiple lines. Each line consists of one or more words separated by spaces. Each word can contain uppercase and lowercase Latin letters, all ASCII punctuation marks, separators, and other nonwhitespace ASCII characters (ASCII codes 33 to 126 inclusive). Whitespace consists of space characters (ASCII code 32). Input The input file contains one or more lines of the code up to the end of file. All lines (including the last one) are terminated by a standard endofline sequence in the file. Each line contains at least one word, each word is 1 to 80 characters long (inclusive). Words are separated by one or more spaces. Lines of the code can have both leading and trailing spaces. Each line in the input file is at most 180 characters long. There are at most 1000 lines in the input file. Output Write to the output file the reformatted, aligned code that consists of the same number of lines, with the same words in the same order, without trailing and leading spaces, separated by one or more spaces such that ith word on each line starts at the same position pi. Sample Input start: integer; // begins here stop: integer; // ends here s: string; c: char; // temp Sample Output start: integer; // begins here stop: integer; // ends here s: string; c: char; // temp
Wiping Words _course
20161225Description In this problem, you are given a paragraph of text in terms of a sequence of lines. Each lines contains a number of words which are sequences of lowercase and uppercase letters and are separated by either blank characters or asterisks. A word is wiped out if for each character in that word, there is no letter or asterisk character in the same position in the next line, or the word appears in the last line of the input. If such a case happens, all occurrences of that word in the text is converted to blanks independent of the corresponding characters in the next line. Note that the asterisks and black characters never disappear. Also, note that the words are considered casesensitive. Write a program to read a sequence of lines described above and wipe out as many word as it can iteratively. Input The first line of the input contains a single integer t (1 ≤ t ≤ 20) which is the number of test cases in the input. Each test case contains a sequence of lines containing characters A..Z, a..z, blank and asterisk (*). After each test case, there is a line containing single hash character (#) which is not a part of the lines you must consider in your algorithm. Output For each test case, write the input lines in the output with the wiped out words converted to blanks. Separate outputs for consecutive test cases with lines containing a single hash character. Sample Input 2 ACM is ** # in this world you are in*side the world * # Sample Output ACM ** # you * the * #
Blue x Red = Bang _course
20171011Description The RB Company is one of the pioneering companies in making electronic boards. This company has recently faced a difficult problem to solve in designing its special power boards. Each power board is a flat plastic plate with special red and/or blue colored plugs on it. The blue plugs are recognized as null poles, and the red ones are phase poles. This company's special design requires that all the blue plugs should be interconnected with straight lines to make a simple blue polygon. All vertices of the resulting polygon should be blue plugs, and any blue plug should be a vertex of this polygon. With similar conditions, all the red plugs should make a red polygon. You may assume that no three plugs of the same color are colinear, i.e. lie on one line. The design problem is that safety precautions require that there should be no red and blue polygon intersections; otherwise a disastrous explosion would be inevitable. This happens when the two polygons have nonempty intersection. The RB engineers have realized that some configurations of red and blue plugs makes it impossible to have nonintersecting red and blue polygons. They consider such configurations disastrous. Your task is to write a program to help the RB engineers recognize and reject the disastrous configurations. Input The first line of the input file contains a single integer t (1 <= t <= 5), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integers b and r (3 <= b, r < 10), the number of blue and red plugs respectively, followed by b lines, each containing two integers x and y representing the coordinates of a blue plug followed by r lines, each containing two integers x and y representing the coordinates of a red plug. Note that all coordinates are pairwise distinct and are in range 0 to 100,000 inclusive. Output There should be one line per test case containing YES if there exist nonintersecting polygons or NO otherwise. The output is considered to be casesensitive. Sample Input 2 4 4 2 2 4 2 2 4 1 1 2 5 2 6 3 3 1 3 3 3 1 1 3 1 2 3 2 2 1 4 3 4 Sample Output YES NO
选美大赛问题 _course
20161206Description Bessie, Farmer John's prize cow, has just won first place in a bovine beauty contest, earning the title 'Miss Cow World'. As a result, Bessie will make a tour of N (2 <= N <= 50,000) farms around the world in order to spread goodwill between farmers and their cows. For simplicity, the world will be represented as a twodimensional plane, where each farm is located at a pair of integer coordinates (x,y), each having a value in the range 10,000 ... 10,000. No two farms share the same pair of coordinates. Even though Bessie travels directly in a straight line between pairs of farms, the distance between some farms can be quite large, so she wants to bring a suitcase full of hay with her so she has enough food to eat on each leg of her journey. Since Bessie refills her suitcase at every farm she visits, she wants to determine the maximum possible distance she might need to travel so she knows the size of suitcase she must bring.Help Bessie by computing the maximum distance among all pairs of farms. Input * Line 1: A single integer, N * Lines 2..N+1: Two spaceseparated integers x and y specifying coordinate of each farm Output * Line 1: A single integer that is the squared distance between the pair of farms that are farthest apart from each other. Sample Input 4 0 0 0 1 1 1 1 0 Sample Output 2
Map of Ninja House _course
20171017Description An old document says that a Ninja House in Kanazawa City was in fact a defensive fortress, which was designed like a maze. Its rooms were connected by hidden doors in a complicated manner, so that any invader would become lost. Each room has at least two doors. The Ninja House can be modeled by a graph, as shown in Figure 1. A circle represents a room. Each line connecting two circles represents a door between two rooms. I decided to draw a map, since no map was available. Your mission is to help me draw a map from the record of my exploration. I started exploring by entering a single entrance that was open to the outside. The path I walked is schematically shown in Figure 2, by a line with arrows. The rules for moving between rooms are described below. After entering a room, I first open the rightmost door and move to the next room. However, if the next room has already been visited, I close the door without entering, and open the next rightmost door, and so on. When I have inspected all the doors of a room, I go back through the door I used to enter the room. I have a counter with me to memorize the distance from the first room. The counter is incremented when I enter a new room, and decremented when I go back from a room. In Figure 2, each number in parentheses is the value of the counter when I have entered the room, i.e., the distance from the first room. In contrast, the numbers not in parentheses represent the order of my visit. I take a record of my exploration. Every time I open a door, I record a single number, according to the following rules. 1. If the opposite side of the door is a new room, I record the number of doors in that room, which is a positive number. 2. If it is an already visited room, say R, I record "the distance of R from the first room" minus "the distance of the current room from the first room", which is a negative number. In the example shown in Figure 2, as the first room has three doors connecting other rooms, I initially record "3". Then when I move to the second, third, and fourth rooms, which all have three doors, I append "3 3 3" to the record. When I skip the entry from the fOurth room to the first room, the distance difference "3" (minus three) will be appended, and so on. So, when I finish this exploration, its record is a sequence of numbers "3 3 3 3 3 3 2 5 3 2 5 3". There are several dozens of Ninja Houses in the city. Given a sequence of numbers for each of these houses, you should produce a graph for each house. Input The first line of the input is a single integer n, indicating the number of records of Ninja Houses I have visited. You can assume that n is less than 100. Each of the following n records consists of numbers recorded on one exploration and a zero as a terminator. Each record consists of one or more lines whose lengths are less than 1000 characters. Each number is delimited by a space or a newline. You can assume that the number of rooms for each Ninja House is less than 100, and the number of doors in each room is less than 100. Output For each Ninja House of m rooms, the output should consist of m lines. The ith line of each such m lines should look as follows: i r(1) r(2)... r(ki), where r(1),... , r(ki), should be rooms adjoining room i, and ki should be the number of doors in room i. Numbers should be separated by exactly one space character. The rooms should be numbered from 1 in visited order. r(1), r(2),..., r(ki), should be in ascending order. Note that the room i may be connected to another room through more than one door. In this case, that room number should appear in r(1),...,r(ki), as many times as it is connected by different doors. Sample Input 2 3 3 3 3 3 3 2 5 3 2 5 3 0 3 5 4 2 4 3 2 2 1 0 Sample Output 1 2 4 6 2 1 3 8 3 2 4 7 4 1 3 5 5 4 6 7 6 1 5 7 3 5 8 8 2 7 1 2 3 4 2 1 3 3 4 4 3 1 2 2 4 4 1 2 2 3
Sorting Slides _course
20171015Description Professor Clumsey is going to give an important talk this afternoon. Unfortunately, he is not a very tidy person and has put all his transparencies on one big heap. Before giving the talk, he has to sort the slides. Being a kind of minimalist, he wants to do this with the minimum amount of work possible. The situation is like this. The slides all have numbers written on them according to their order in the talk. Since the slides lie on each other and are transparent, one cannot see on which slide each number is written. ![](http://poj.org/images/1486_1.jpg) Well, one cannot see on which slide a number is written, but one may deduce which numbers are written on which slides. If we label the slides which characters A, B, C, ... as in the figure above, it is obvious that D has number 3, B has number 1, C number 2 and A number 4. Your task, should you choose to accept it, is to write a program that automates this process. Input The input consists of several heap descriptions. Each heap descriptions starts with a line containing a single integer n, the number of slides in the heap. The following n lines contain four integers xmin, xmax, ymin and ymax, each, the bounding coordinates of the slides. The slides will be labeled as A, B, C, ... in the order of the input. This is followed by n lines containing two integers each, the x and ycoordinates of the n numbers printed on the slides. The first coordinate pair will be for number 1, the next pair for 2, etc. No number will lie on a slide boundary. The input is terminated by a heap description starting with n = 0, which should not be processed. Output For each heap description in the input first output its number. Then print a series of all the slides whose numbers can be uniquely determined from the input. Order the pairs by their letter identifier. If no matchings can be determined from the input, just print the word none on a line by itself. Output a blank line after each test case. Sample Input 4 6 22 10 20 4 18 6 16 8 20 2 18 10 24 4 8 9 15 19 17 11 7 21 11 2 0 2 0 2 0 2 0 2 1 1 1 1 0 Sample Output Heap 1 (A,4) (B,1) (C,2) (D,3) Heap 2 none
Roman Numerals _course
20171011Description The original system of writing numbers used by the early Romans was simple but cumbersome. Various letters were used to represent important numbers, and these were then strung together to represent other numbers with the values decreasing monotonically from left to right. The letters they used and the numbers that were represented are given in the following table. I 1 V 5 X 10 L 50 C 100 D 500 M 1000 Thus 1993 was written as MDCCCCLXXXXIII. This system was then superseded by a partially placeoriented system, whereby if the above rule of decreasing values was broken, it meant that the immediately preceding (lower) value was deemed to be `negative' and was subtracted from the higher (out of place) value. In this system 1993 was usually written as MCMXCIII. There is still some controversy as to which letters could precede which other letters, but for the purposes of this problem we will assume the following restrictions: 1. A letter from the left column can never appear more than three times in a row, and there can never be more than one other occurrence of that letter. 2. A letter from the right column can never appear more than once. 3. Once a letter has been used in a `negative' position, all subsequent characters (apart from the one immediately following) may not be greater than that character. Thus we could write MXMIII for 1993 or CCXCIV for 294, however we could not write ILV for 54, nor could we write LIL for 99. Note that 299 could be written as CCXCIX or CCIC Given a Roman sum, we can either interpret it as such or as an encoding of an Arabic sum. Thus V+V=X could be interpreted as an ambiguous encoding of an Arabic sum with V ∈ {1, 2, 3, 4} and X = 2 * V. Similarly, X+X=XX could be interpreted as a correct Roman sum but an impossible Arabic encoding (apart from the trivial encoding X = 0) and XX+XX=MXC as an incorrect Roman sum, but a valid encoding with M = 1, X = 9, and C = 8. Write a program that will read in sums in Roman numerals and determine whether or not they are correct as Roman sums and also whether they are impossible, ambiguous or valid as Arabic encodings. Assume that zero will never appear on its own or as a leading digit, and that no two Roman numerals map onto the same Arabic digit. Input Input will consist of a series of lines, each line consisting of an apparent Roman sum, i.e. a valid Roman number, a plus sign (+), another valid Roman number, an equal sign (=) and another valid Roman number. No Roman number will contain more than 9 letters. The file will be terminated by a line consisting of a single #. Output Output will consist of a series of lines, one for each line of the input, and each containing two words. The first word will be one of (Correct, Incorrect) depending on whether the Roman sum is or is not correct. The second word will be separated from the first by exactly one space and will be one of the set (impossible, ambiguous, valid) depending on the Arabic sum. Sample Input V+V=X X+X=XX XX+XX=MXC # Sample Output Correct ambiguous Correct impossible Incorrect valid
Organize Your Train part II _course
20161108Description RJ Freight, a Japanese railroad company for freight operations has recently constructed exchange lines at Hazawa, Yokohama. The layout of the lines is shown in Figure 1. ![](http://poj.org/images/3007_1.gif) Figure 1: Layout of the exchange lines A freight train consists of 2 to 72 freight cars. There are 26 types of freight cars, which are denoted by 26 lowercase letters from "a" to "z". The cars of the same type are indistinguishable from each other, and each car's direction doesn't matter either. Thus, a string of lowercase letters of length 2 to 72 is sufficient to completely express the configuration of a train. Upon arrival at the exchange lines, a train is divided into two subtrains at an arbitrary position (prior to entering the storage lines). Each of the subtrains may have its direction reversed (using the reversal line). Finally, the two subtrains are connected in either order to form the final configuration. Note that the reversal operation is optional for each of the subtrains. For example, if the arrival configuration is "abcd", the train is split into two subtrains of either 3:1, 2:2 or 1:3 cars. For each of the splitting, possible final configurations are as follows ("+" indicates final concatenation position): [3:1] abc+d cba+d d+abc d+cba [2:2] ab+cd ab+dc ba+cd ba+dc cd+ab cd+ba dc+ab dc+ba [1:3] a+bcd a+dcb bcd+a dcb+a Excluding duplicates, 12 distinct configurations are possible. Given an arrival configuration, answer the number of distinct configurations which can be constructed using the exchange lines described above. Input The entire input looks like the following. the number of datasets = m 1st dataset 2nd dataset ... mth dataset Each dataset represents an arriving train, and is a string of 2 to 72 lowercase letters in an input line. Output For each dataset, output the number of possible train configurations in a line. No other characters should appear in the output. Sample Input 4 aa abba abcd abcde Sample Output 1 6 12 18
三星的上机题，请大神帮助解答。怎么打印出3到10000的数据。_course
20170618You are to find the closest common ancestor of two vertices in a binary tree. For example, the common ancestors of vertices 8 and 13 in the figure below are vertices 3 and 1. Among them, vertex 3 is the closest to the vertex 8 and 13. And the size of subtree (the number of vertices in the subtree) rooted by vertex 3 is 8.![图片说明](https://imgask.csdn.net/upload/201706/18/1497782587_428418.jpg) Given a binary tree and two vertices, write a program that finds the closest common ancestor and computes the size of the subtree rooted by the closest common ancestor. No input is given where one of the two given vertices is an ancestor of the other. For example, ‘11 and 3’ in the above tree is an invalid input. Therefore, your program does not have to consider this case. [Constraints] The number of vertices are from 3 to 10000 [Input] You are given 10 test cases. Each test case has two lines, so the total number of lines is 20. In each test case, the first line consists of four integers, V (the number of vertices in the tree), E (the number of edges), and the indices of two vertices. E edges are listed in the next line. Each edge is represented by two vertices; the index of the parent vertex always precedes the index of the child. For example, the edge connecting vertices 5 and 8 is represented by “5 8”, not by “8 5.” There is no order in which the edges are given. Every consecutive integer in the input is separated by a space. Given 10 test cases, First 4 test cases contain small number of vertices(3, 5, 7, 10 each). Next 6 test cases contain same or greater than 50 vertices. The indices of vertices are integers from 1 to V, and root vertex always has the index 1. It is guaranteed that the parent vertex has smaller index than the child vertex. In this problem, it is not important whether the child is the left child of the parent or the right child; so you can decide this arbitrarily. [Output] Output 10 answers in 10 lines. Each line starts with ‘#x’ meaning the index of a test case, and writes the answer after a space. The answer has two integers: the index of the closest common ancestor and the size of the subtree rooted by the closest common ancestor. These two integers are separated by a space as well. [I/O Example] Input (20 lines in total) 13 12 8 13 ← Start of the first input 1 2 1 3 2 4 3 5 3 6 4 7 7 12 5 9 5 8 6 10 6 11 11 13 10 9 1 10 ← Start of the second input 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 ... Output (10 lines in total) #1 3 8 #2 1 10 ...
Optimal Milking _course
20171010Description FJ has moved his K (1 <= K <= 30) milking machines out into the cow pastures among the C (1 <= C <= 200) cows. A set of paths of various lengths runs among the cows and the milking machines. The milking machine locations are named by ID numbers 1..K; the cow locations are named by ID numbers K+1..K+C. Each milking point can "process" at most M (1 <= M <= 15) cows each day. Write a program to find an assignment for each cow to some milking machine so that the distance the furthestwalking cow travels is minimized (and, of course, the milking machines are not overutilized). At least one legal assignment is possible for all input data sets. Cows can traverse several paths on the way to their milking machine. Input * Line 1: A single line with three spaceseparated integers: K, C, and M. * Lines 2.. ...: Each of these K+C lines of K+C spaceseparated integers describes the distances between pairs of various entities. The input forms a symmetric matrix. Line 2 tells the distances from milking machine 1 to each of the other entities; line 3 tells the distances from machine 2 to each of the other entities, and so on. Distances of entities directly connected by a path are positive integers no larger than 200. Entities not directly connected by a path have a distance of 0. The distance from an entity to itself (i.e., all numbers on the diagonal) is also given as 0. To keep the input lines of reasonable length, when K+C > 15, a row is broken into successive lines of 15 numbers and a potentially shorter line to finish up a row. Each new row begins on its own line. Output A single line with a single integer that is the minimum possible total distance for the furthest walking cow. Sample Input 2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0 Sample Output 2
The comment in cpp _course
20171029Problem Description In C++ ,there are two styles of comment, one is a stream of characters enclosed by "/*" and "*/", and the other is a single line beginning with "//". Comments will not be nested as in c++. Your task is to deal with these comments, which is to capitalize all the letters in a comment and count the number of occurrence of comments. To simplify your task, you may assume that comments will not appear in constant strings. Input The first line speicifies the number of test cases T (T <= 10). Each test case begins with a number L (L <= 100), the number of lines of the C++ code, following L lines which is the body of the code. The length of each line of the code will not exceed 200. Output For each test case, output the number occurrence of comments you've found and then the resulting text of your processing. print a line after each test case. Sample Input 2 1 /*hduacm 1 /*hduacm //hduacm */ Sample Output 0 /*hduacm 1 /*HDUACM //HDUACM */
Bold ASCII Lines _course
20171101Problem Description Your grandmother recently developed a passion for the internet and the new technologies in general, and is now discovering the wonders of ASCII art. Unfortunately, her sight is not as it once was, and she has difficulty seeing the pictures. ![](http://acm.hdu.edu.cn/data/images/C23610051.JPG) Moreover, she cannot merely increase the font size as she usually does, because doing so makes the characters stand out more on their own and less as a whole. You come up with a solution: writing a program which duplicates the ASCII lines in order to make them look bold. Input The first line of the input will contain n, the number of test cases. For each test case, the first line will contain the positive integers w and h, both of which will be at most 100. h lines will follow, each containing w ASCII characters. The character “.” (dot) will denote the background ASCII “color”, and the only other color will be “*” (star). For each image, add a 1character wide border of dots around the image, and proceed to replace every single star character in the original picture with a , where the middle star is positioned where the original star was. Output In the output, separate each test case with “”. Sample Input 2 2 1 *. 3 3 .*. *.* .*. Sample Output .*.. ***. .*..  ..*.. .***. ***** .***. ..*..
软件测试2小时入门
20181010本课程内容系统、全面、简洁、通俗易懂，通过2个多小时的介绍，让大家对软件测试有个系统的理解和认识，具备基本的软件测试理论基础。 主要内容分为5个部分： 1 软件测试概述，了解测试是什么、测试的对象、原则、流程、方法、模型； 2.常用的黑盒测试用例设计方法及示例演示； 3 常用白盒测试用例设计方法及示例演示； 4.自动化测试优缺点、使用范围及示例‘； 5.测试经验谈。
 43.19MB
智鼎(附答案).zip
20200422并不是完整题库，但是有智鼎在线2019年9、10、11三个月的试题，有十七套以上题目，普通的网申行测题足以对付，可以在做题时自己总结一些规律，都不是很难
 43KB
炉温系统的PID控制器设计——MATLAB程序
20180517本文主要研究的课题是：炉温系统的PID控制器设计研究 ，并且在MATLAB的大环境下进行模拟仿真。 (1)第一章 介绍课题的研究背景、意义以及发展现状。 (2)第二章 建立炉温系统数学模型 (3)第三
Java进阶高手课Java基础编程提升
20200427课程聚焦Java基础编程提升的核心知识点，以真实场景项目实战为导向，循序渐进，深入浅出的了解Java基础编程，讲解Java这门使用广泛的编程语言，助你能够游刃有余地游走在这些技术之中。
Python进阶Pandas数据分析库
20181218您观看课程学习后 免费入群领取【超全Python资料包+17本学习电子书】 Pandas是python中非常常用的数据分析库，在数据分析，机器学习，深度学习等领域经常被使用。本课程会讲解到pandas中最核心的一些知识点，包括Series以及DataFrame的构建，赋值，操作，选择数据，合并等等，以及使用pandas对文件进行读取和写入，使用pandas绘图等等。
 博客 AES/ECB/PKCS5Padding128在JAVA，PHP，JavaScript， Python四种语言中的相互加解密
 下载 一种高分辨率图像采集系统的设计与实现
 下载 2.45G远距离读卡器应用于不停车管理项目
 博客 一个很好的MediaPlayer音频播放示例
 学院 JVM从入门到入魔
 学院 3天计算机视觉精进训练营
 学院 2020千锋Linux云计算入门视频全套全开源（最新版）
 学院 3小时快速学习计算机基础
 下载 虚拟校园漫游系统优化算法研究
 学院 PHP微信小程序鲜花礼品商城
 学院 Netty教程：十二个实例带你轻松学习Netty
 博客 java中的string对象深入了解
 博客 js数据类型
 博客 代码练习switch
 博客 在自己的程序里测试PCL点云的显示
 学院 系统学习Linux命令
 下载 通用数字调制器设计与实现
 学院 基于RK3399和OpenCV实现实时视频增强
 下载 科技论文写作资料汇总（升级版2）.html
 下载 ASP.NET多文件上传控件Uploadify的使用方法
 学院 JavaWeb珠宝首饰购物商城毕业设计 大学生毕业设计教学视频
 学院 PHP微信小程序家具家居商城 大学生毕业设计 教学视频
 下载 Zend Framework教程之前端控制器Zend_Controller_Front用法详解
 学院 Java微信小程序珠宝首饰购物商城 大学生毕业设计教学视频
 学院 Java小白学习方法指南！避开思维惯性！让学习事半功倍
 博客 如何提升Java基础知识？从这6点出发
 博客 atlas已存在表关联新表关系不创建
 下载 GridView自定义分页实例详解(附demo源码下载)
 下载 NOVO3266嵌入式主板在车载系统上应用
 学院 2020年软考网络规划设计师论文写作套路精讲视频课程