- Island Explorer
A group of explorers has found a solitary island. They land on the island and explore it along a straight line. They build a lot of campsites while they advance. So the campsites are laid on the line.
Coincidently, another group of explorers land on the island at the same time. They also build several campsites along another straight line. Now the explorers meet at the island and they decide to connect all the campsites with telegraph line so that they can communicate with each other wherever they are.
Simply building segments that connect a campsite to another is quite easy, but the telegraph line is rare. So they decide to connect all the campsites with as less telegraph line as possible. Two campsites are connected if they are directly connected with telegraph line or they are both connected to another campsite.
There are multiple test cases.
The number of the test cases is in the first line of the input.
For each test case, first line contains two integers N and M (0≤N, M≤10000), which N is the number of the campsites of the first group of explorers and M is the number of the campsites of the second group of explorers. And there exist at least one campsite.
The next two lines contain eight integers Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. Their absolute values are less than 1000. The integers are the coordinates of four points A, B, C and D. The exploring path of the first group is begin with the first point A and end with the second point B, and the path of the second group is from the third point C to the fourth point D. Every pair of points is distinct.
The last two lines of the test case contain N and M real numbers; they indicate the positions of the campsites. Suppose the i-th real number in the first line is t. It means the x-coordinate of the i-th campsite is Ax * t + Bx * (1-t), and the y-coordinate is Ay * t + By * (1-t). Equally, the campsite on the second straight line is C * t + D * (1-t). You can assume that there are at most four digits in the decimal part, and the numbers are always between 0 and 1.
For each test case, output contains only a real number rounded to 0.001.
0 0 10 10
0 10 10 0
0.1 0.3 0.6 0.8
0.1 0.3 0.6 0.8
Case #1: 19.638
Description Each Sunday Mrs. Mahtaj who is an old woman goes to David Church and after the Sunday pray she comes back home. The traffic center has a complicated rule for closing crossroads that Mrs. Mahtaj can't understand. She is a forgetful woman who can only memorize the path from her house to church. The streets of her city are vertical or horizontal, the same as a grid with the squares of the same size. So she memorizes a path by a string of F (Forward), B (Backward), L (Left) and R (Right). For example, if there is no closed crossroad and Mahtaj is in crossroad (1,0) and faces east, if the string is BRFRLFL she reaches the crossroad (0,4). His son, Khashayar, decides to help her finding a path that can be used both for going from their house to the church and for coming back from the church to their house and does not pass any closed crossroad. I.e. Mahtaj should be able to go from her house to the church and from the church to her house by just one string. Help Khashayar to find such a path. When Mrs. Mahtaj starts the path from her house, she faces east and when she starts from the church she faces west. Input The input consists of several test cases. Each test case begins with a line containing m and n, the number of vertical and horizontal lines (streets) in the grid, which are in range 1 to 100. The second line of a test case contains two pairs of integer, which are x and y coordinates of the source (Mrs. Mahtaj's house) and x and y coordinates of the destination (David church). The horizontal and vertical lines in the grid are indexed from left to right and bottom to up from 0, so coordinates can be expressed using the indices. The third line of a test case contains a single numbe r N, which is the number of closed crossroads. It follows by N lines that each line contains x and y coordinates of a closed crossroad. The test case with m=n=0 indicates the end of the input file. Output The output for each test case is "YES" if there is such path and otherwise "NO". Output for each test case must be written on a separate line and the test case with m=n=0 has no output. Sample Input 3 3 0 0 2 2 2 1 2 2 1 6 5 0 0 5 4 5 3 0 3 2 2 2 0 2 5 2 0 0 Sample Output NO YES
Description Bessie's been appointed the new watch-cow for the farm. Every night, it's her job to walk across the farm and make sure that no evildoers are doing any evil. She begins at the barn, makes her patrol, and then returns to the barn when she's done. If she were a more observant cow, she might be able to just walk each of M (1 <= M <= 50,000) bidirectional trails numbered 1..M between N (2 <= N <= 10,000) fields numbered 1..N on the farm once and be confident that she's seen everything she needs to see. But since she isn't, she wants to make sure she walks down each trail exactly twice. It's also important that her two trips along each trail be in opposite directions, so that she doesn't miss the same thing twice. A pair of fields might be connected by more than one trail. Find a path that Bessie can follow which will meet her requirements. Such a path is guaranteed to exist. Input * Line 1: Two integers, N and M. * Lines 2..M+1: Two integers denoting a pair of fields connected by a path. Output * Lines 1..2M+1: A list of fields she passes through, one per line, beginning and ending with the barn at field 1. If more than one solution is possible, output any solution. Sample Input 4 5 1 2 1 4 2 3 2 4 3 4 Sample Output 1 2 3 4 2 1 4 3 2 4 1
A Walk in the Park _course2017-02-14
问题描述 : You are responsible for inspecting the trees located in a park, to make sure they remain healthy. The location of each tree is given to you as a point in the twodimensional plane, distinct from that of every other tree. Due to recentlyreplanted grass, you are only allowed to walk through the park along a collection of paths. Each path is described by an infinite-length horizontal or vertical line in the two-dimensional plane. No tree lies on any path. You are concerned that it may not be possible to view all the trees in the park from the paths. In particular, a tree is visible only if you can view it by standing on some path while facing in a direction perpendicular to that path; there must be no intervening tree that obstructs your view. Given the geometrical configuration of the park, please report the number of visible trees. 输入: There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths. The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers. The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case. End of the input is signified by a line with two space-separated 0′s. 输出: There will be multiple input sets. For each input set, the first line will contain two integers, N and M , ( 0 < N, M<=100000 ), separated by a space. N is the number of trees, and M is the number of paths. The next N lines each contain two space-separated integers, X and Y , specifying the coordinates of a tree. X and Y may be any 32-bit integers. The next M lines each describe a path (a vertical or horizontal line). They have the form x = K or y = K , with no spaces. K may be any 32-bit integer. x and y will be lower case. End of the input is signified by a line with two space-separated 0′s. 样例输入: 6 3 -1 3 4 2 6 2 6 3 6 4 4 3 x=0 y=-1 y=5 1 2 2 3 x=5 y=5 0 0 样例输出: 5 1
Cow Math _course2017-10-13
Description Taking their cue from the builders of the USA's Interstate Highway system, the cows have introduced the Interpasture Path numbering system. They have already numbered the N (2 <= N <= 25) pastures with the integers 1..N and now are numbering each path between two pastures with its own distinct Interpasture Path number in the range 1..2000 (e.g., I-9 and I-16). In an example Interpasture Path map, four pastures numbered 1, 2, 3, and 4 are connected by Interpasture Paths I-3, I-6, I-9, and I-16: 4--< I-6>--2 / / < I-16> < I-9> / / 1--< I-3>--3 Bessie likes to walk from pasture 1 to pasture 2 on the nifty new Interpasture system. During each walk, she never visits the same pasture twice, so possible walks on the sample map above are 1-4-2 and 1-3-2. Over the years, Bessie has developed an amazing mathematical skill that she likes to exercise. During each walk, she enjoys finding the greatest common factor (GCF) of the Interpasture Paths that she traverses. For instance, the walk designated 1-4-2 touches I-16 and I-6 which have the greatest common factor of 2 (since 2 properly divides into 16 and 6 but no larger integer does). As she walks the pastures day after day, she takes all the possible routes from pasture 1 to pasture 2 and remembers each of the GCFs. After she has taken every possible walk once, she computes the least common multiple (LCM) of all the GCFs. For this example, the two GCF values are 2 and 3 (GCF(6,16)=2 and GCF(3,9)=3), so the LCM is 6. For large networks of paths, Bessie might get tired of all the walking, but she really wants to know the LCM for every map. Calculate that number for her. Input * Line 1: N * Lines 2..N+1: These N lines represent the symmetric Interpasture Path connectivity matrix of the pastures. Line L shows the connectivity between pasture L-1 and the other pastures with its N space-separated integers. The first integer on each line is the Interpasture Path number that connects pasture L-1 and and pasture 1; the second integer is the IP number connecting pasture L-1 and pasture 2; etc. If pasture A connects to pasture B, then pasture B connects to Pasture A. When no Interpasture Path is available, the integer is 0. Output A single line with a single integer that is the LCM of the GCFs of all the possible walks from pasture 1 to pasture 2. It is guaranteed that the answer will contain 100 or fewer digits. Sample Input 4 0 0 3 16 0 0 9 6 3 9 0 0 16 6 0 0 Sample Output 6
Optimal Milking _course2017-10-10
Description 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 furthest-walking 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 space-separated integers: K, C, and M. * Lines 2.. ...: Each of these K+C lines of K+C space-separated 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
Problem Description In the Data structure class of HEU, the teacher asks one problem: How to find the longest path of one tree and the number of such longest path? Input There are several test cases. The first line of each case contains only one integer N, means there are N nodes in the tree. N-1 lines follow, each line has three integers w,v and len, indicate that there is one edge between node w and v., and the length of the edge is len. Output For each test case, output the length of longest path and its number in one line. Sample Input 4 1 2 100 2 3 50 2 4 50 4 1 2 100 2 3 50 3 4 50 Sample Output 150 2 200 1
Problem Description Give you a Graph,you have to start at the city with ID zero. Input The first line is n(1<=n<=21) m(0<=m<=3) The next n line show you the graph, each line has n integers. The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000 Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first. The input end with EOF. Output For each test case,output the shorest length of the hamilton path. If you could not find a path, output -1 Sample Input 3 0 -1 2 4 -1 -1 2 1 3 -1 4 3 -1 2 -1 1 2 -1 2 1 4 3 -1 1 3 2 3 -1 1 3 0 1 2 3 Sample Output 4 5
Description You are to write a program that draws a border around a closed path into a bitmap, as displayed in the following figure: !(http://images.cnblogs.com/cnblogs_com/acmicky/502875/o_1132.png) The path is closed and runs along the grid lines, i.e. between the squares of the grid. The path runs counter-clockwise, so if following the path is considered as going ``forward'', the border pixels are always to the "right'' of the path. The bitmap always covers 32 by 32 squares and has its lower left corner at (0, 0). You can safely assume that the path never touches the bounding rectangle of the bitmap and never touches or crosses itself. Note that a bit gets set if it is on the outside of the area surrounded by the path and if at least one of its edges belongs to the path, but not if only one of its corners is in the path. (A look at the convex corners in the figure should clarify that statement.) Input The first line of the input file contains the number of test cases in the file. Each test case that follows consists of two lines. The first line of each case contains two integer numbers x and y specifying the starting point of the path. The second line contains a string of variable length. Every letter in the string symbolizes a move of length one along the grid. Only the letters 'W' ("west"), 'E' ("east"), 'N' ("north"), 'S' ("south"), and '.' ("end of path", no move) appear in the string. The end-of-path character ( '.') is immediately followed by the end of the line. Output For each test case, output a line with the number of the case ('Bitmap #1', 'Bitmap #2', etc.). For each row of the bitmap from top to bottom, print a line where you print a character for every bit in that row from left to right. Print an uppercase 'X' for set bits and a period '.' for unset bits. Output a blank line after each bitmap. Sample Input 1 2 1 EENNWNENWWWSSSES.
Number Link _course2017-07-15
Problem Description Number Link is a famous game available in platforms including iOS and Android. Given a board with n rows and m columns, the target of the game is to connect pairs of grids with the same numbers. Once two numbers are paired, the path connecting them will occupy the corresponding grids. The path can only go vertically or horizontally. Note that, no two paths could intersect (by sharing the same grid) in any grid. In this problem, you are going to play a modified version, called Number Link ++. See the picture below for an example. In this new game, you can use two types of paths. Type I is to connect two number grids with different parities (i.e., connect odd number with any other even number). It might be hard to cover the entire grid with only type I path, so we allow type II path, which is a circle path covers only the empty grids (the only special case of type II path is a path only connecting two adjacent empty grids; see the figure above). Since there is no free lunch, we have no free path either. When goes from grid (a,b) to an adjacent grid (c,d), you have to pay for a certain amount of tolls. The cost is the same when goes back from (c,d) to (a,b). Usually the cost of a path is the sum of tolls you paid by traveling along the grids on this path. The only exception is for the special case of type II path. In that case, you have to pay twice the cost (since it is a circle). The total cost of the game is the sum of costs for all the paths. Can you help me figure out the paths so that each grid is on exactly one path? If there exists such solution, what is the minimum possible cost? Input The first line of input consists of an integer T, which is the number of test cases. Each case begins with two integers, n and m, in a line (1≤n,m≤50). The next n lines describe the board. Each line consists of m nonnegative numbers, which describe the status of each column from left to right. If the number is zero, then the grid is empty; otherwise it indicates the number on the corresponding grid. The next n−1 lines each have m nonnegative numbers, which describe the cost of vertical connection. The j-th number in i-th line is the cost when travels from grid (i,j) to (i+1,j). The next n lines each have m−1 nonnegative numbers, which describe the cost of horizontal connection. The j-th number in i-th line is the cost for a path to go from grid (i,j) to (i,j+1). All the numbers, including the answer, can be represented using 32-bit signed integer. Output For each test case, first output the case number, then output a single number, which is the minimum cost possible to finish the game. When there is no solution available, simply output -1. Sample Input 3 3 3 1 0 0 1 0 0 2 0 2 1 2 1 2 1 1 3 1 5 6 1 4 1 4 1 1 2 2 1 2 3 3 5 0 0 0 0 0 0 5 0 6 0 0 0 0 0 0 1 1000 1000 1000 1 1 1000 1000 1000 1 1 1 1 1 1000 1 1 1000 1 1 1 1 Sample Output Case #1: 10 Case #2: -1 Case #3: 14
The Longest Detour Problem _course2017-10-15
Description Let G be a weighted graph, i.e., every edge in G is associated with a nonnegative integer weight. The length of a path is the sum of edge weights in the path. A shortest path between vertices r and s in G, denoted by PG(r, s), is defined as a path with the shortest length from r to s. The distance between vertices r and s, denoted by dG(r, s), is the length of the shortest path PG(r, s). For two vertices in a connected graph, there exists at least one shortest path between them. Let e = (u, v) be an edge in PG(r, s) with v closer to s than u (v may be s). Let G - e denote the subgraph obtained by removing edge e from G. A detour from u is the shortest path from u to s in G - e, or PG-e(u, s). Edge e is a detour -critical edge in PG(r, s) if the removal of e results in the maximum distance increment from u to s. In other words, if e is a detour -critical edge in PG(r, s), then dG-e(u, s) - dG(u, s) is maximum among all edges in PG(r, s). The longest detour problem is to find the maximum distance increment of a shortest path. !(http://poj.org/images/1340_1.jpg) Figure 4: A weighted graph G. For example, see Figure 4. PG(4, 1) =< 4, 3, 2, 1 > is the shortest path from vertex 4 to vertex 1. Path < 4, 6, 1 > is the detour from vertex 4 to vertex 1 if edge (4, 3) is removed. Path < 3, 5, 1 > is the detour from vertex 3 to vertex 1 if edge (3, 2) is removed. Path < 2, 5, 1 > is the detour from vertex 2 to vertex 1 if edge (2, 1) is removed. The detour -critical edge in PG(4, 1) is not edge (4, 3) or edge (2, 1) but edge (3, 2) since dG-(3,2)(3, 1) - dG(3, 1) = 600 - 200 = 400 is greater than dG-(4,3)(4, 1) - dG(4, 1) = 500 - 300 = 200 and dG-(2,1)(2, 1) - dG(2, 1) = 200 - 100 = 100. The algorithm for finding detours, as well as determining the detour-critical edges, is important from the viewpoint of network management. Due to a sudden edge failure from some vertex, the message must be retransmitted through a detour from the vertex adjacent to the faulty edge. Suppose that we have several networks. Each network is connected and contains at most n vertices, where 3 <= n <= 100. Assume now that you are hired to serve as a network administrator and have to determine the maximum distance increment caused by a detour-critical edge of a given shortest path for each network. Input The input consists of several test cases. The first line contains an integer indicating the number of test cases. Each test case starts with a positive integer n, where 3 <= n <= 100. The following n lines represent the adjacency matrix of a network. An adjacency matrix of a network G with n vertices, denoted by A(G) = [wu,v], is an n * n matrix such that wu,v > 0 if (u, v) is an edge of G, and wu,v= 0 otherwise, where wu,v in a nonnegative integer. Note that any two elements in each line of an adjacency matrix are separated by a space. The last line of each test case represents the sequence of vertices in a given shortest path in which there is also a space between two vertices. Note that the first and the last vertices denote the source and the destination vertices, respectively. For example, the adjacency matrix of the graph in Figure 4 is shown in test case 3 of the sample input. Output For each test case, output the maximum distance increment caused by the detour-critical edge of the given shortest path in one line. Sample Input 3 3 0 10 20 10 0 10 20 10 0 3 2 1 4 0 10 10 30 10 0 30 0 10 30 0 10 30 0 10 0 4 3 1 2 6 0 100 0 0 100 200 100 0 100 0 100 400 0 100 0 100 500 0 0 0 100 0 500 300 100 100 500 500 0 0 200 400 0 300 0 0 4 3 2 1 Sample Output 20 30 400
Six Degrees of Cowvin Bacon _course2017-10-13
Description The cows have been making movies lately, so they are ready to play a variant of the famous game "Six Degrees of Kevin Bacon". The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one 'degree' away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two 'degrees' away from each other (counted as: one degree to the cow they've worked with and one more to the other cow). This scales to the general case. The N (2 <= N <= 300) cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made M (1 <= M <= 10000) movies and it is guaranteed that some relationship path exists between every pair of cows. Input * Line 1: Two space-separated integers: N and M * Lines 2..M+1: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., Mi); the subsequent Mi integers tell which cows were. Output * Line 1: A single integer that is 100 times the shortest mean degree of separation of any of the cows. Sample Input 4 2 3 1 2 3 2 3 4 Sample Output 100
A sample Hamilton path _course2017-12-10
Problem Description Give you a Graph,you have to start at the city with ID zero. Input The first line is n(1<=n<=21) m(0<=m<=3) The next n line show you the graph, each line has n integers. The jth integers means the length to city j.if the number is -1 means there is no way. If i==j the number must be -1.You can assume that the length will not larger than 10000 Next m lines,each line has two integers a,b (0<=a,b<n) means the path must visit city a first. The input end with EOF. Output For each test case,output the shorest length of the hamilton path. If you could not find a path, output -1 Sample Input 3 0 -1 2 4 -1 -1 2 1 3 -1 4 3 -1 2 -1 1 2 -1 2 1 4 3 -1 1 3 2 3 -1 1 3 0 1 2 3 Sample Output 4 5 Hint
Ticket to Ride _course2017-05-23
Problem 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
Enigmatic Travel _course2017-10-17
Description Suhan and Laina live in an n-dimensional city where there are (n+1) locations. Any two locations (consider these locations as points) are equidistant from each other and connected by only one bi-directional road. They love to roam together around the city on their favourite bi-verbal (A kind of vehicle). Kiri, a tenth generation robot also lives in the same city and wants to kill Suhan out of jealousy. That is why Suhan and Laina are very careful about keeping their thoughts and plans secret. Therefore nobody knows a) Where Suhan and Laina lives. b) What their destination location is. c) Which roads will they use? So their journey can start from any location, ends in another location and they may use any road sequence they like. Their destination location may be same or different than the source location. For example when their tour is guaranteed to be a simple cycle their source and destination location are same. Given the number of locations in the city (L) you will have to find the expected cost (often considered as average) of one of their single travelling. You can assume that the cost of travelling from one location to another through the direct (also shortest) path is 1 universal joule. Input The input file contains several lines of input. Each line contains a single integer L(15 >= L > 2) that indicates the number of locations in the city. Input is terminated by a line where value of L is zero. This line should not be processed. Output For each line of input produce one line of output. This line contains three floating-point numbers F1, F2, F3. Here F1 is the expected cost when they travel along a path, F2 is the expected cost when it is guaranteed that they travel along a simple path and F3 is the expected cost when it is guaranteed that they travel along a simple cycle. All the floatingpoint numbers should be rounded up to four digits after the decimal point. You must assume that their travelling cost is not greater than (L). Travelling cost is always expressed in universal joule. Sample Input 3 4 5 0 Sample Output 2.4286 1.5000 3.0000 3.5500 2.2000 3.5000 4.6716 3.0625 4.2000
Circuit Board _course2017-09-20
On the circuit board, there are lots of circuit paths. We know the basic constrain is that no two path cross each other, for otherwise the board will be burned. Now given a circuit diagram, your task is to lookup if there are some crossed paths. If not find, print "ok!", otherwise "burned!" in one line. A circuit path is defined as a line segment on a plane with two endpoints p1(x1,y1) and p2(x2,y2). You may assume that no two paths will cross each other at any of their endpoints. Input The input consists of several test cases. For each case, the first line contains an integer n(<=2000), the number of paths, then followed by n lines each with four float numbers x1, y1, x2, y2. Output If there are two paths crossing each other, output "burned!" in one line; otherwise output "ok!" in one line. Sample Input 1 0 0 1 1 2 0 0 1 1 0 1 1 0 Sample Output ok! burned!
A Walk Through the Forest _course2017-10-25
Problem Description Jimmy experiences a lot of stress at work these days, especially since his accident made working difficult. To relax after a hard day, he likes to walk home. To make things even nicer, his office is on one side of a forest, and his house is on the other. A nice walk through the forest, seeing the birds and chipmunks is quite enjoyable. The forest is beautiful, and Jimmy wants to take a different route everyday. He also wants to get home before dark, so he always takes a path to make progress towards his house. He considers taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A. Calculate how many different routes through the forest Jimmy might take. Input Input contains several test cases followed by a line containing 0. Jimmy has numbered each intersection or joining of paths starting with 1. His office is numbered 1, and his house is numbered 2. The first line of each test case gives the number of intersections N, 1 < N ≤ 1000, and the number of paths M. The following M lines each contain a pair of intersections a b and an integer distance 1 ≤ d ≤ 1000000 indicating a path of length d between intersection a and a different intersection b. Jimmy may walk a path any direction he chooses. There is at most one path between any pair of intersections. Output For each test case, output a single integer indicating the number of different routes through the forest. You may assume that this number does not exceed 2147483647 Sample Input 5 6 1 3 2 1 4 2 3 4 3 1 5 12 4 2 34 5 2 24 7 8 1 3 1 1 4 1 3 7 1 7 4 1 7 5 1 6 7 1 5 2 1 6 2 1 0 Sample Output 2 4
The Game _course2017-01-24
Description One morning, you wake up and think: "I am such a good programmer. Why not make some money?'' So you decide to write a computer game. The game takes place on a rectangular board consisting of w * h squares. Each square might or might not contain a game piece, as shown in the picture. One important aspect of the game is whether two game pieces can be connected by a path which satisfies the two following properties: It consists of straight segments, each one being either horizontal or vertical. It does not cross any other game pieces. (It is allowed that the path leaves the board temporarily.) Here is an example: The game pieces at (1,3) and at (4, 4) can be connected. The game pieces at (2, 3) and (3, 4) cannot be connected; each path would cross at least one other game piece. The part of the game you have to write now is the one testing whether two game pieces can be connected according to the rules above. Input The input contains descriptions of several different game situations. The first line of each description contains two integers w and h (1 <= w,h <= 75), the width and the height of the board. The next h lines describe the contents of the board; each of these lines contains exactly w characters: a "X" if there is a game piece at this location, and a space if there is no game piece. Each description is followed by several lines containing four integers x1, y1, x2, y2 each satisfying 1 <= x1,x2 <= w, 1 <= y1,y2 <= h. These are the coordinates of two game pieces. (The upper left corner has the coordinates (1, 1).) These two game pieces will always be different. The list of pairs of game pieces for a board will be terminated by a line containing "0 0 0 0". The entire input is terminated by a test case starting with w=h=0. This test case should not be procesed. Output For each board, output the line "Board #n:", where n is the number of the board. Then, output one line for each pair of game pieces associated with the board description. Each of these lines has to start with "Pair m: ", where m is the number of the pair (starting the count with 1 for each board). Follow this by "ksegments.", where k is the minimum number of segments for a path connecting the two game pieces, or "impossible.", if it is not possible to connect the two game pieces as described above. Output a blank line after each board. Sample Input 5 4 XXXXX X X XXX X XXX 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0 0 0 Sample Output Board #1: Pair 1: 4 segments. Pair 2: 3 segments. Pair 3: impossible.
Description The Department of Recreation has decided that it must be more profitable, and it wants to sell advertising space along a popular jogging path at a local park. They have built a number of billboards (special signs for advertisements) along the path and have decided to sell advertising space on these billboards. Billboards are situated evenly along the jogging path, and they are given consecutive integer numbers corresponding to their order along the path. At most one advertisement can be placed on each billboard. A particular client wishes to purchase advertising space on these billboards but needs guarantees that every jogger will see it's advertisement at least K times while running along the path. However, different joggers run along different parts of the path. Interviews with joggers revealed that each of them has chosen a section of the path which he/she likes to run along every day. Since advertisers care only about billboards seen by joggers, each jogger's personal path can be identified by the sequence of billboards viewed during a run. Taking into account that billboards are numbered consecutively, it is sufficient to record the first and the last billboard numbers seen by each jogger. Unfortunately, interviews with joggers also showed that some joggers don't run far enough to see K billboards. Some of them are in such bad shape that they get to see only one billboard (here, the first and last billboard numbers for their path will be identical). Since out-of-shape joggers won't get to see K billboards, the client requires that they see an advertisement on every billboard along their section of the path. Although this is not as good as them seeing K advertisements, this is the best that can be done and it's enough to satisfy the client. In order to reduce advertising costs, the client hires you to figure out how to minimize the number of billboards they need to pay for and, at the same time, satisfy stated requirements. Input The first line of the input contains two integers K and N (1 <= K, N <= 1000) separated by a space. K is the minimal number of advertisements that every jogger must see, and N is the total number of joggers. The following N lines describe the path of each jogger. Each line contains two integers Ai and Bi (both numbers are not greater than 10000 by absolute value). Ai represents the first billboard number seen by jogger number i and Bi gives the last billboard number seen by that jogger. During a run, jogger i will see billboards Ai, Bi and all billboards between them. Output On the fist line of the output file, write a single integer M. This number gives the minimal number of advertisements that should be placed on billboards in order to fulfill the client's requirements. Then write M lines with one number on each line. These numbers give (in ascending order) the billboard numbers on which the client's advertisements should be placed. Sample Input 5 10 1 10 20 27 0 -3 15 15 8 2 7 30 -1 -10 27 20 2 9 14 21 Sample Output 19 -5 -4 -3 -2 -1 0 4 5 6 7 8 15 18 19 20 21 25 26 27
2020数学建模国赛A题及其数据 2020数学建模国赛A题及其数据2020数学建模国赛A题及其数据 2020数学建模国赛A题及其数据 2020数学建模国赛A题及其数据 2020数学建模国赛A题及其数据
限时福利1：购课进答疑群专享柳峰（刘运强）老师答疑服务。 为什么说每一个程序员都应该学习MySQL？ 根据《2019-2020年中国开发者调查报告》显示，超83%的开发者都在使用MySQL数据库。 使用量大同时，掌握MySQL早已是运维、DBA的必备技能，甚至部分IT开发岗位也要求对数据库使用和原理有深入的了解和掌握。 学习编程，你可能会犹豫选择 C++ 还是 Java；入门数据科学，你可能会纠结于选择 Python 还是 R；但无论如何， MySQL 都是 IT 从业人员不可或缺的技能！ 【课程设计】 在本课程中，刘运强老师会结合自己十多年来对MySQL的心得体会，通过课程给你分享一条高效的MySQL入门捷径，让学员少走弯路，彻底搞懂MySQL。 本课程包含3大模块： 一、基础篇： 主要以最新的MySQL8.0安装为例帮助学员解决安装与配置MySQL的问题，并对MySQL8.0的新特性做一定介绍，为后续的课程展开做好环境部署。 二、SQL语言篇： 本篇主要讲解SQL语言的四大部分数据查询语言DQL，数据操纵语言DML，数据定义语言DDL，数据控制语言DCL，学会熟练对库表进行增删改查等必备技能。 三、MySQL进阶篇： 本篇可以帮助学员更加高效的管理线上的MySQL数据库；具备MySQL的日常运维能力，语句调优、备份恢复等思路。
微信小程序 实例汇总 完整项目源代码2016-11-01
微信小程序 实例汇总 完整项目源代码
所含文章如下： simplescalar简介.pdf SimpleScalar安装报告.doc simplescalar实验.pdf Cache低功耗技术研究及SimpleScalar模拟器分析.nh
从简单到难的200来个经典C程序 第一部分 基础篇 001 第一个C程序 002 运行多个源文件 003 求整数之积 004 比较实数大小 005 字符的输出 006 显示变量所占字节数 007 自增
- 学院 3天计算机视觉精进训练营
- 下载 基于IEEE 802．15．4 CSMA／CA机制的无线非均匀传感网络实时性能分析
- 学院 PHP微信小程序家具家居商城 大学生毕业设计 教学视频
- 学院 视觉应用工程师---第32期
- 学院 项目管理工具箱
- 博客 冒泡排序代码笔记
- 学院 JavaWeb珠宝首饰购物商城毕业设计 大学生毕业设计教学视频
- 博客 Python的JAVA胶水——jpype
- 下载 vue.js入门教程之计算属性
- 学院 JVM从入门到入魔
- 博客 1092 To Buy or Not to Buy（散列）
- 学院 3小时快速学习计算机基础
- 博客 k8s cheat sheet
- 学院 Unity热更新框架-基于ILRuntime
- 下载 网络安全等级保护测评要求.pdf
- 学院 系统学习Linux命令
- 博客 每日一题——长键输入
- 学院 Java微信小程序母婴用品商城 大学生毕业设计教学视频
- 下载 众智图纸管理 众智图纸管理软件 v8.1
- 学院 python基础快速处理Excel
- 博客 关于Java和C#的类型对比
- 博客 图像边缘检测四个算子
- 下载 js实现String.Fomat的实例代码
- 学院 FFmpeg4.3开发系列之七：WEB音视频转码器Java版
- 下载 数据透视表应用大全100集动画教程
- 博客 JAVA实现打字小游戏
- 下载 knockoutjs动态加载外部的file作为component中的template数据源的实现方法
- 学院 Java微信小程序服装商城 大学生毕业设计教学视频
- 下载 显示/光电技术中的多重选择电容式触摸屏平板电脑解决方案
- 博客 力扣 925. 长按键入