| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 10659 | The Net |
|
| 10660 | Identifying Concurrent Events |
|
| 10661 | Sum it up |
|
| 10662 | Knights in FEN |
|
Description
[BFS]
Taking into account the present interest in the Internet, a smart information routing becomes a must. This job is done by routers situated in the nodes of the network. Each router has its own list of routers which are visible for him (so called ``routing table"). It is obvious that the information should be directed in the way which minimizes number of routers it has to pass (so called ``hop count").
Your task is to find an optimal route (minimal hop count) for the given network form the source of the information to its destination.
Input
First line contains number of routers in the network (n). Next n lines contain description of the network. Each line contains router ID (1 ≤ ID ≤ n), followed by a hyphen and comma separated list of IDs of visible routers. The list is sorted in ascending order. Next line contains a number of routes (m ≤ 1000) you should determine. The consecutive m lines contain starting and ending routers for the route separated by a single space.
Input data may contain descriptions of many networks (at most 10).
Output
For each network you should output a line with 5 hyphens and then, for each route, a list of routers passed by information sent from starting to destination routers.
In case passing of information is impossible (no connection exists) you should output a string ``connection impossible". In case of multiple routes with the same `hop count' the one with lower IDs should be outputted (in case of route form router 1 to 2 as 1 3 2 and 1 4 2 the 1 3 2 should be outputted).
Assumptions: A number of routers is not greater than 300 and there are at least 2 routers in the network. Each routers ``sees" no more than 50 routers.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[All-pairs Shortest Paths]
It is important in distributed computer systems to identify those events (at identifiable points in time) that are concurrent, or not related to each other in time. A group of concurrent events may sometimes attempt to simultaneously use the same resource, and this could cause problems.
Events that are not concurrent can be ordered in time. For example, if event e1 can be shown to always precede event e2 in time, then e1 and e2 are obviously not concurrent. Notationally we indicate that e1 precedes e2 by writing e1 → e2. Note that the precedes relation is transitive, as expected. Thus if e1 → e2 and e2 → e3, then we can also note that e1 → e3.
Sequential events in a single computation are not concurrent. For example, if a particular computation performs the operations identified by events e1, e2 and e3 in that order, then clearly e1 → e2 and e2 → e3.
Computations in a distributed system communicate by sending messages. If event esend corresponds to the sending of a message by one computation, and event erecv corresponds to the reception of that message by a different computation, then we can always note that esend → erecv, since a message cannot be received before it is sent.
In this problem you will be supplied with lists of sequential events for an arbitrary number of computations, and the identification of an arbitrary number of messages sent between these computations. Your task is to identify those pairs of events that are concurrent.
Input
A number of test cases will be supplied (at most 50). For each test case the input will include first an integer, NC, specifying the number of computations in the test case. For each of these NC computations there will be a single line containing an integer NEi that specifies the number of sequential events in the computation followed by NEi event names. There are at most 100 events. (i.e., ∑i NEi ≤ 100) Event names will always contain one to five alphanumeric characters, and will be separated from each other by at least one blank. Following the specification of the events in the last computation there will be a line with a single integer, NM, that specifies the number of messages that are sent between computations. Finally, on each of the following NM lines there will be a pair of event names specifying the name of the event associated with the sending of a message, and the event associated with the reception of the message. These names will have previously appeared in the lists of events associated with computations, and will be separated by at least one blank. The last test case will be followed by the single integer 0 on a line by itself.
Output
For each test case, print the test case number (they are numbered sequentially starting with 1), the number of pairs of concurrent events for the test case. And if there are no concurrent events, then state that fact. See the sample output for more details.
Example
Consider the following input data:
2
2 e1 e2
2 e3 e4
1
e3 e1
0
There are two computations. In the first e1 → e2 and in the second e3 → e4. A single message is sent from e3 to e1, which means e3 → e1. Using the transitive property of the precedes relation we can additionally determine that e3 → e2. This leaves the pairs (e1,e4) and (e2,e4) as concurrent events.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[Branch and Bound I]
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t = 4, n = 6, and the list is [4, 3, 2, 2, 1, 1], then there are four different sums that equal 4: 4, 3+1, 2+2, and 2+1+1. (A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.) Your job is to solve this problem in general.
Input
The input file will contain one or more test cases (at most 100), one per line. Each test case contains t, the total, followed by n, the number of integers in the list, followed by n integers x1, …, xn. If n = 0 it signals the end of the input; otherwise, t will be a positive integer no more than 1000, n will be an integer between 1 and 12 (inclusive), and x1, …, xn will be positive integers no more than 1000. All numbers will be separated by exactly one space. The numbers in each list appear in nonincreasing order, and there may be repetitions.
Output
For each test case, first output a line containing `Sums of ', the total, and a colon. Then output each sum, one per line; if there are no sums, output the line `NONE'. The numbers within each sum must appear in nonincreasing order. A number may be repeated in the sum as many times as it was repeated in the original list. The sums themselves must be sorted in decreasing order based on the numbers appearing in the sum. In other words, the sums must be sorted by their first number; sums with the same first number must be sorted by their second number; sums with the same first two numbers must be sorted by their third number; and so on. Within each test case, all sums must be distinct; the same sum cannot appear twice.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
[Branch and Bound II]
There are black and white knights on a 5 by 5 chessboard. There are twelve of each color, and there is one square that is empty. At any time, a knight can move into an empty square as long as it moves like a knight in normal chess (what else did you expect?).
Given an initial position of the board, the question is: what is the minimum number of moves in which we can reach the final position which is:
(圖片請參考紙本題目)
Input
First line of the input file contains an integer N (N < 14) that indicates how many sets of inputs are there. The description of each set is given below:
Each set consists of five lines; each line represents one row of a chessboard. The positions occupied by white knights are marked by 0 and the positions occupied by black knights are marked by 1. The space corresponds to the empty square on board.
There is no blank line between the two sets of input.
The first set of the sample input below corresponds to this configuration:
(圖片請參考紙本題目)
Output
For each set your task is to find the minimum number of moves leading from the starting input configuration to the final one. If that number is bigger than 10, then output one line stating
Unsolvable in less than 11 move(s).
otherwise output one line stating
Solvable in n move(s).
where n ≤ 10.
The output for each set is produced in a single line as shown in the sample output.