Question 2: File Fragmentation
The Problem
Your friend, a biochemistry major, tripped while carrying a tray of computer files through the lab. All of the files fell to the ground and broke. Your friend picked up all the file fragments and called you to ask for help putting them back together again.
Fortunately, all of the files on the tray were identical, all of them broke into exactly two fragments, and all of the file fragments were found. Unfortunately, the files didn't all break in the same place, and the fragments were completely mixed up by their fall to the floor.
You've translated the original binary fragments into strings of ASCII 1's and 0's, and you're planning to write a program to determine the bit pattern the files contained.
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
Input will consist of a sequence of ``file fragments'', one per line, terminated by the end-of-file marker. Each fragment consists of a string of ASCII 1's and 0's.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.Output is a single line of ASCII 1's and 0's giving the bit pattern of the original files. If there are 2N fragments in the input, it should be possible to concatenate these fragments together in pairs to make N copies of the output string. If there is no unique solution, any of the possible solutions may be output.
Your friend is certain that there were no more than 144 files on the tray, and that the files were all less than 256 bytes in size.
Sample Input
1 011 0111 01110 111 0111 10111
Sample Output
01110111
'ACM' 카테고리의 다른 글
10039 - Railroads (0) | 2009.06.02 |
---|---|
10110 - Light, more light (0) | 2009.06.02 |
10099 - The Tourist Guide (0) | 2009.06.02 |
10004 - Bicoloring (0) | 2009.06.02 |
100 - The 3n + 1 problem (0) | 2009.06.02 |
10099 - The Tourist GuideTime limit: 3.000 seconds |
Problem D
The Tourist Guide
Input: standard input
Output: standard output
Mr. G. works as a tourist guide. His current assignment is to take some tourists from one city to another. Some two-way roads connect the cities. For each pair of neighboring cities there is a bus service that runs only between those two cities and uses the road that directly connects them. Each bus service has a limit on the maximum number of passengers it can carry. Mr. G. has a map showing the cities and the roads connecting them. He also has the information regarding each bus service. He understands that it may not always be possible for him to take all the tourists to the destination city in a single trip. For example, consider the following road map of 7 cities. The edges connecting the cities represent the roads and the number written on each edge indicates the passenger limit of the bus service that runs on that road.
Now, if he wants to take 99 tourists from city 1 to city 7, he will require at least 5 trips, since he has to ride the bus with each group, and the route he should take is : 1 - 2 - 4 - 7.
But, Mr. G. finds it difficult to find the best route all by himself so that he may be able to take all the tourists to the destination city in minimum number of trips. So, he seeks your help.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: N (N<= 100) and Rrepresenting respectively the number of cities and the number of road segments. Then R lines will follow each containing three integers: C1, C2 and P. C1 and C2 are the city numbers and P (P> 1) is the limit on the maximum number of passengers to be carried by the bus service between the two cities. City numbers are positive integers ranging from 1 to N. The (R + 1)-th line will contain three integers: S, D and T representing respectively the starting city, the destination city and the number of tourists to be guided.
The input will end with two zeroes for N and R.
Output
For each test case in the input first output the scenario number. Then output the minimum number of trips required for this case on a separate line. Print a blank line after the output of each test case.
Sample Input
7 101 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0
Sample Output
Scenario #1Minimum Number of Trips = 5
'ACM' 카테고리의 다른 글
10039 - Railroads (0) | 2009.06.02 |
---|---|
10110 - Light, more light (0) | 2009.06.02 |
10132 - File Fragmentation (0) | 2009.06.02 |
10004 - Bicoloring (0) | 2009.06.02 |
100 - The 3n + 1 problem (0) | 2009.06.02 |
Bicoloring
In 1976 the ``Four Color Map Theorem" was proven with the assistance of a computer. This theorem states that every map can be colored using only four colors, in such a way that no region is colored using the same color as a neighbor region.
Bicoloring |
Here you are asked to solve a simpler similar problem. You have to decide whether a given arbitrary connected graph can be bicolored. That is, if one can assign colors (from a palette of two) to the nodes in such a way that no two adjacent nodes have the same color. To simplify the problem you can assume:
- no node will have an edge to itself.
- the graph is nondirected. That is, if a node a is said to be connected to a node b, then you must assume that b is connected to a.
- the graph will be strongly connected. That is, there will be at least one path from any node to any other node.
Input
The input consists of several test cases. Each test case starts with a line containing the number n ( 1 < n < 200) of different nodes. The second line contains the number of edges l. After this, l lines will follow, each containing two numbers that specify an edge between the two nodes that they represent. A node in the graph will be labeled using a number a ( ).An input with n = 0 will mark the end of the input and is not to be processed.
Output
You have to decide whether the input graph can be bicolored or not, and print it as shown below.Sample Input
3 3 0 1 1 2 2 0 9 8 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0
Sample Output
NOT BICOLORABLE. BICOLORABLE.
'ACM' 카테고리의 다른 글
10039 - Railroads (0) | 2009.06.02 |
---|---|
10110 - Light, more light (0) | 2009.06.02 |
10132 - File Fragmentation (0) | 2009.06.02 |
10099 - The Tourist Guide (0) | 2009.06.02 |
100 - The 3n + 1 problem (0) | 2009.06.02 |