Each puzzle solution in the input starts with a line containing two integers r and c (1² r ²10 and 1² c ²10), where r (the first number) is the number of rows in the puzzle and c (the second number) is the number of columns. The r rows of input which follow each contain c characters (excluding the end-of-line) which describe the solution. Each of those c characters is an alphabetic character which is part of a word or the character "*", which indicates a black square. The end of input is indicated by a line consisting of the single number 0.
Output for each puzzle consists of an identifier for the puzzle (puzzle #1, puzzle #2, etc.) and the list of across words followed by the list of down words. Words in each list must be output one-per-line in increasing order of the number of their corresponding definitions. The heading for the list of across words is “Across”. The heading for the list of down words is “Down”. In the case where the lists are empty (all squares in the grid are black), the Across and Down headings should still appear.
Output for the Sample Input
The Green Earth Trading Company sells 4 different sizes of energy-efficient fluorescent light bulbs for use in home lighting fixtures. The light bulbs are expensive, but last much longer than ordinary incandescent light bulbs and require much less energy. To encourage customers to buy and use the energy-efficient light bulbs, the company catalogue lists special packages which contain a variety of sizes and numbers of the light bulbs. The price of a package is always substantially less than the total price of the individual bulbs in the package. Customers typically want to buy several different sizes and numbers of bulbs. You are to write a program to determine the least expensive collection of packages that satisfy any customer’s request.
The input file is divided into two parts. The first one describes the packages which are listed in the catalogue. The second part describes individual customer requests. The 4 sizes of light bulbs are identified in the input file by the characters "a", "b", "c", and "d".
The first part of the input file begins with an integer n (1² n ²50) indicating the number of packages described in the catalogue. Each of the n lines that follows is a single package description. A package description begins with a catalogue number (a positive integer) followed by a price (a real number), and then the sizes and corresponding numbers of the light bulbs in the package. Between 1 and 4 different sizes of light bulbs will be listed in each description. The listing format for these size-number pairs is a blank, a character ("a", "b", "c", or "d") representing a size, another blank, and then an integer representing the number of light bulbs of that size in the package. These size-number pairs will not appear in any particular order, and there will be no duplicate sizes listed in any package. The following line describes a package with catalogue number 210 and price $76.95 which contains 3 size "a" bulbs, 1 size "c" bulb, and 4 size "d" bulbs.
210 76.95 a 3 c 1 d 4
The second part of the input file begins with a line containing a single positive integer m representing the number of customer requests. Each of the remaining m lines is a customer request. A listing of sizes and corresponding numbers of light bulbs constitutes a request. Each list contains only the size-number pairs, formatted the same way that the size-number pairs are formatted in the catalogue descriptions. Unlike the catalogue descriptions, however, a customer request may contain duplicate sizes. The following line represents a customer request for 1 size "a" bulb, 2 size "b" bulbs, 2 size "c" bulbs, and 5 size "d" bulbs.
a 1 d 5 b 1 c 2 b 1
For each request, print the customer number (1 through m, 1 for the first customer request, 2 for the second, É, m for the mth customer), a colon, the total price of the packages which constitute the least expensive way to fill the request, and then the combination of packages that the customer should order to fill that request.
Prices should be shown with exactly two significant digits to the right of the decimal. The combination of packages must be written in ascending order of catalogue numbers. If more than one of the same type package is to be ordered, then the number ordered should follow the catalogue number in parentheses. You may assume that each customer request can be filled. In some cases, the least expensive way to fill a customer request may contain more light bulbs of some sizes than necessary to fill the actual request. This is acceptable. What matters is that the customers receive at least what they request.
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
b 3 c 2
b 1 a 1 c 1 d 1 a 1
b 1 b 2 c 3 c 1 a 1 d 1
b 3 c 2 d 1 c 1 d 2 a 1
Output for the Sample Input
1: 27.50 55
2: 50.00 10(2)
3: 65.50 3 10 55
4: 52.87 6
5: 90.87 3 6 10
6: 100.45 55(3) 502
CPN (The Couch Potato Network) owns several cable channels. They would like to arrange the timing of programmes so viewers can switch channels without missing the end of one programme or the beginning of another. To do this they have identified certain times, called “alignment points,” where ideally one programme should end and another should begin. Some of these alignment points are more important than others. For example, the time when the nightly news begins is an important alignment point. Since many viewers watch the news, they would be less likely to watch a CPN programme whose ending time causes them to miss the beginning of the news, or which starts before the news finishes. Your task is to write a solution which determines the best order in which programmes can be shown on one channel.
A “miss” time is the absolute value of the difference between the time of an alignment point and the nearest time of the beginning or end of a programme. The “total miss time” at a particular level of importance is the sum of all the miss times for alignment points at that level of importance. One programme order is better than another if it has a lower total miss time at some level of importance and the same total miss time at all higher levels of importance (if any).
Your solution must accept multiple input data sets. Each set will begin with an integer, p (0² p ²8), specifying the number of programmes to be ordered. When a data set beginning with 0 is encountered, your solution should terminate. Following p on the same line will be p integers specifying the lengths of the programmes in minutes. There is no significance to the order in which these are given.
The next line of input specifies the alignment points. The total number of such points, a (0² a ²8), appears first followed by a pairs of integers. The first integer in each pair, i (1² i ²5), gives the importance of the alignment point. Alignment points marked 1 are most important; those marked 2 are of secondary importance, etc. The second integer in each pair, t, specifies the time when the alignment point occurs. No two alignment points in the same data set will have the same value of t.
Your solution must output three lines for each data set. The first line identifies the data set being processed and should be in the form:
Data set n
where n is the number of the data set (1 for the first data set, 2 for the second, etc.). On the following line, your solution should output the lengths of the programmes in the order in which they should be shown to achieve the best synchronization with the alignment points. On the third line, output the total number of minutes by which the alignment points were missed (the sum of all total miss times).
There may be more than one best programme order for an input data set. Any one of these best orders is acceptable.
4 30 45 45 15
3 1 60 2 90 3 15
6 10 15 13 18 25 33
4 1 30 2 15 2 45 1 60
Output for the Sample Input
Data set 1
Order: 15 45 30 45
Data set 2
Order: 15 13 33 25 18 10
Proportional fonts are so called because characters require varying amounts of space on the printed line. The size in which text is “set,” usually measured in points, also affects the space required for each character. In this problem you are given a number of paragraphs of text to set. Each paragraph may include special “words” to select the font and point size.
The input starts with the font width table. These data give the widths of 10-point characters in six different fonts. The first line contains the number of characters in the table, N (0² N ²100). Each of the next N lines contain a character in column 1 and then 6 integers representing the width of that character in each of the 6 different fonts. Widths are given in an arbitrary measurement called “units.” The width of each 10-point character will be greater than zero units, and less than 256 units. Character widths scale linearly with point size. Thus if a 10-point “A” is 12 units wide, a 20-point “A” is 24 units wide.
The remainder of the input consists of paragraphs to be typeset. Each paragraph begins with a line containing two integers, L and W. L is the number of input lines of text for the paragraph (these immediately follow the first line), and W is the width allowed for each typeset line, in units. The initial font at the beginning of each paragraph is always font 1, and the initial point size in which characters are to be set is 10. Fonts are numbered 1 through 6, corresponding to columns 1 through 6 in the font width table. An empty paragraph (one for which L is 0) will mark the end of the input data. No output is to be produced for this empty paragraph.
The words in each paragraph are sequences of no more than 8 non-blank characters separated by spaces (that is, blanks—no tab characters will appear in the input). Spaces at the ends of input lines are irrelevant, and spaces between words are significant only to the extent that they separate words. Each character in each word will appear in the width table. Case is significant for all characters in the input data.
The special tokens "*f1", "*f2", "*f3", "*f4", "*f5", and "*f6" are used to select a particular font to be used in setting the text that follows it. The token "*sN", where N is an integer in the range 1 to 99 indicates that N point characters are to be used in setting the following text. These tokens will always be separated from words and other tokens by at least one blank. Note that style and size changes made in one paragraph do not carry over to the next paragraph, and that many such changes may appear in a single paragraph.
For each paragraph, try to set as many words per line as possible, ensuring that each word is followed by at least the width of a blank (which will always appear in the font width table) with the same point size and style as the characters in the preceding word, except for the last word on the line. The last word in a typeset line must not have any following space.
When scaling fonts, round the scaled character widths to the nearest integer, rounding upward in cases where the rounded value is half way between two consecutive integers. Thus, if a particular 10 point character occupies 9 units of space, a 15 point character would occupy 14 units of space, as would a 16 point character. A 14 point character, however, would occupy only 13 units of space.
For each paragraph, first display the paragraph number (1, 2, ...). Then, for each typeset line in the paragraph, display the line number, the first and last words on that line, and the total number of units of white space that follow the last character printed on the line. (This is just the number of units of space available on the line not occupied by characters or spaces between characters.)
If a single word exceeds the width of a line, set it on a line by itself. In the output for that line, show only that single word, and a negative amount of white space equal to the excess width of the word.
A 10 20 30 12 22 32
B 1 2 3 4 5 6
C 9 10 8 3 5 2
2 4 6 3 5 7
*f2 AAA BBB CCC
ABC *s15 CBA AABC CACA
AAA BBB CCC
ABC CBA AABC CACA
Output for the Sample Input
Line 1: AAA ... BBB (10 whitespace)
Line 2: CCC ... ABC (14 whitespace)
Line 3: CBA ... CBA (32 whitespace)
Line 4: AABC ... AABC (2 whitespace)
Line 5: CACA (-10 whitespace)
Line 1: AAA ... CCC (4 whitespace)
Line 2: ABC ... AABC (26 whitespace)
Line 3: CACA ... CACA (62 whitespace)
VTAS - Vessel Traffic Advisory Service
In order to promote safety and efficient use of port facilities, the Association of Coastal Merchants (ACM) has developed a concept for a Vessel Traffic Advisory Service (VTAS) that will provide traffic advisories for vessels transiting participating ports.
The concept is built on a computer program that maintains information about the traffic patterns and reported movements of vessels within the port over multiple days. For each port, the traffic lanes are defined between waypoints. The traffic lanes have been designated as directional to provide traffic separation and flow controls. Each port is represented by a square matrix containing the distances (in nautical miles) along each valid traffic lane. The distances are defined from each row waypoint to each column waypoint. A distance of 0 indicates that no valid traffic lane exists between the two waypoints.
Vessel traffic enters the port at a waypoint and transits the traffic lanes. A vessel may begin its transit at any of the waypoints and must follow a valid connected route via the valid traffic lanes. A vessel may end its transit at any valid waypoint.
The service provided by the VTAS to transiting vessels includes:
• Projected encounters with other vessels on each leg of the transit. An “encounter” occurs when two vessels are between common waypoints (either traffic lane) at a common time
• Warning of close passing with another vessel in the vicinity of a waypoint (within 3 minutes of projected waypoint arrival)
Reported times will be rounded to the nearest whole minute. Time is maintained based on a 24 hour clock (i.e. 9 am is 0900, 9 PM is 2100, midnight is 0000). Speed is measured in knots which is equal to 1 nautical mile per hour.
The input file for the computer program include a Port Specification to provide the description of the traffic patterns within the port and a Traffic List which contains the sequence of vessels entering the port and their intended tracks. The end of the input is indicated by a Vessel Name beginning with an "*"
Port Specification : Number of Waypoints in Port (an integer N)
Waypoint ID List (N single-character designators)
Waypoint Connection Matrix (N rows of N real values specifying the distances between waypoints in nautical miles)
Traffic List: Vessel Name (alphabetic characters)
Time at first waypoint (on 24-hour clock) & Planned Transit Speed (in knots)
Planned Route (ordered list of waypoints)
The output shall provide for each vessel as it enters the port a listing indicating the arrival of the vessel and its planned speed followed by a table containing the waypoints in its route and projected arrival at each waypoint. Following this table will be appropriate messages indicating:
• Notification of Invalid Routes
• Projected Encounters on each leg
• Warning of close passing at waypoints
All times are to be printed as four-digit integers with leading zeros when necessary.
Assumptions & Limitations
1. Vessel names are at most 20 characters long.
2. There are at most 20 waypoints in a port and at most 20 waypoints in any route.
3. There will be at most 20 vessels in port at any time.
4. A vessel will complete its transit in at most 12 hours.
5. No more than 24 hours will elapse between vessel entries.
0 3 0 0 0 0
3 0 0 2 0 0
0 3 0 0 0 0
0 0 0 0 3 0
0 0 2 0 0 4
0 0 0 0 4 0
Output for the Sample Input
Tug entering system at 2330 with a planned speed of 12.0 knots
Waypoint: A B D E F
Arrival: 2330 2345 2355 0010 0030
WhiteSailboat entering system at 2345 with a planned speed of 6.0 knots
Waypoint: E C B D E
Arrival: 2345 0005 0035 0055 0125
TugWBarge entering system at 2355 with a planned speed of 5.0 knots
Waypoint: D E C B A
Arrival: 2355 0031 0055 0131 0207
Projected encounter with Tug on leg between Waypoints D & E
** Warning ** Close passing with Tug at Waypoint D
PowerCruiser entering system at 0000 with a planned speed of 15.0 knots
Waypoint: F E C B A
Arrival: 0000 0016 0024 0036 0048
Projected encounter with Tug on leg between Waypoints F & E
Projected encounter with WhiteSailboat on leg between Waypoints C & B
** Warning ** Close passing with WhiteSailboat at Waypoint B
LiberianFreighter entering system at 0007 with a planned speed of 18.0 knots
**> Invalid Route Plan for Vessel: LiberianFreighter
ChineseJunk entering system at 0045 with a planned speed of 8.0 knots
A researcher at a rehabilitation facility is studying the use that a patient makes of a motorized wheelchair in a restricted area at the facility. The chair’s motor is connected to the axle by a chain drive. Therefore both wheels turn at the same speed and the chair can travel only in a straight line. The patient can stop the chair, rotate the wheels, and thereby change the direction only while the wheelchair is stopped. To help monitor its usage, the chair is equipped with a compass, a clock, and a speedometer. A recording device records each time interval that the chair is in motion, the average speed during the time interval, and the compass bearing during the time interval. The compass is a standard compass in which 0û is north, 90û is east, and so forth.
A map of the restricted area is shown. The restricted area is a 200 ft by 400 ft rectangular area of the lawn. Patients enter the restricted area from the door of a building located on the southern edge of the restricted area. The door is at the center of the 400 ft southern boundary, as shown in the figure.
The recording device turns itself on when the patient enters the restricted area through the door and monitors the patient’s movements for up to 1 hour. Time is measured in seconds from 0 to 3600, with time 0 being the time the patient initially enters the restricted area through the door. The device records 4 numbers to describe the motion of the wheelchair during any interval when the motor is in operation. The first two numbers give the time the motion begins and ends; the third number gives the speed during the time interval; and the fourth number gives the compass bearing during the time interval. (During each time interval the wheelchair maintains constant speed and bearing.) For example, the recorded line
10.6 15.9 2.8 274
would indicate that between times t1 = 10.6 and t2 = 15.9 seconds the wheelchair was traveling at speed of 2.8 ft/sec with compass bearing (direction) 274û. Times are recorded to 0.1 sec, speeds are recorded to 0.1 ft/sec, and bearings are recorded to a whole number of degrees.
Your job is to analyze the data from the wheelchair’s recording device. Specifically, you must determine the following:
1) Did the patient ever leave the restricted area? If so, determine the first time that the patient left the restricted area and determine at what point on the perimeter of the restricted area the wheelchair crossed out of the restricted area. If the patient did not leave the restricted area, what was the distance from the door to the farthest point the patient reached within the area?
2) What was the total distance that the patient traveled?
For the purpose of answering these questions, use coordinates with the location (0,0) corresponding to the southwest corner of the restricted area and the location (400,200) corresponding to the northeast corner. Since the recorder switches on when the patient passes through the door, the position of the patient at time t = 0.0 is always (200,0). Patients will be traveling north when they enter the restricted area.
The input data consists of several data sets. The first line of each data set has an integer which is the number of lines recorded by the device. Each subsequent line in the data set consists of the four numbers recorded by the device during a particular time interval. The end of data is indicated by a data set whose first line consists of the number 0.
In the first data set of the sample input, the patient entered through the door (at time 0.0) and for the first 5 seconds was traveling due north at 3 ft/sec. From time t = 7 to t = 9 he traveled at a speed of 2 ft/sec with a compass bearing of 30û. He then stopped, changed his bearing to 60û, and then traveled at 4 ft/sec from time t = 10 to time t = 100. Ten seconds later (at time t = 110) he headed due north at 2 ft/sec until t = 200.
The output for each data set begins with an identification of that case. The output indicates whether the patient departed from the restricted area and if so the time and point of departure on the perimeter . If not, the maximum distance the patient reached from the door is provided. For each case, the total distance that the patient traveled is provided. Format your output so that the same labeling information is included as shown in the sample output, with a line of asterisks separating the cases.
0.0 5.0 3.0 0
7.0 9.0 2.0 30
10.0 100.0 4.0 60
110.0 200.0 2.0 0
0.0 20.0 2.0 0
500.0 600.0 1.0 270
3000.0 3100.0 1.0 0
0.0 5.3 2.1 0
19.8 35.6 2.7 346
42.0 78.4 2.3 15
1181.4 1192.1 1.7 117
2107.0 2193.6 2.1 295
2196.3 2201.2 2.0 298
2704.3 2709.2 1.5 208
Output for the Sample Input
Case Number 1
Left restricted area at point (400.0,132.8) and time 67.2 sec.
Total distance traveled was 559.0 feet
Case Number 2
No departure from restricted area
Maximum distance patient traveled from door was 172.0 feet
Total distance traveled was 240.0 feet
Case Number 3
Left restricted area at point (67.0,200.0) and time 2191.4 sec.
Total distance traveled was 354.7 feet
Assumptions and requirements
1. Within each data set, time intervals will be listed in chronological order, with the first time interval always having time 0.0 as the time of entry into the restricted area. All times will be given with one decimal place accuracy and will be in the range 0.0 to 3600.0 inclusive. For each time interval specified, the duration of the time interval will be positive, i.e. the second time specified will be greater than the first.
2. Speeds will be in the range 0.1 to 9.9 ft/sec.
3. Compass bearings will be given as a whole number of degrees and will be in the range 0 to 359 inclusive. The initial compass bearing for the first line of data in each data set will be 0.
4. Within each line of data, numbers will be separated by at least one blank space.
5. All numerical results will be displayed with one decimal place of accuracy as shown in the sample output.
6. If the patient goes out of the restricted area, his location may include negative coordinates. However, you don't have to worry about the wheelchair crashing through the walls of the building.