Description

 A group of judges must get together to judge a contest held in a particular city, and they need to figure out the cheapest way of renting cars in order to get everyone to the contest. They observed that it might be cheaper if several judges share a rental car during all or part of the trip, thus reducing the overall cost. Your task is to identify the routes the judges should take in order to minimize the total cost of their car rentals.

• The cost of a rental car is proportional to the distance it is driven. There are no charges for more than one occupant in the car, fuel, insurance, or leaving the car in a city other than that in which it was rented.
• All rental cars are billed at the same rate per mile.
• A rental car can accommodate any number of passengers.
• At most one road directly connects any pair of cities. Each road is two-way and has an integer length greater than zero.
• There is at least one route from every judge's starting city to the city in which the contest is held.
• All judges whose routes to the contest take them from or through the same city travel from that city to the contest together. (A judge might arrive at a city in one car and leave that city in a different car.)

Input

 The input contains several test cases. Each test case includes a route map, the destination city where the contest is being held, and the cities where the judges are initially located.

• NC-the number of cities that appear in the route map; this will be no larger than 20.
• DC-the number of the destination city, assuming the cities are numbered 1 to NC.
• NR-the number of roads in the route map. Each road connects a distinct pair of cities.
• For each of the NR roads, three integers C1, C2, and DIST. C1 and C2 identify two cities connected by a road, and DIST gives the distance between these cities along that road.
• NJ-the number of judges. This number will be no larger than 10.
• NJ-integers, one for each judge each of these is a city number identifying the initial location of that judge.

Output

 For each test case, display the case number (1, 2,...) and the shortest total distance traveled by the rental cars conveying the judges to the contest. Then display the list of routes used by the judges, each route on a separate line, in the same order as the ordering of starting cities given in the input. Each route consists of the cities that the corresponding judge must visit, listed in the order in which they are visited, starting with the judge's starting city and ending with the contest city. Any other cities along the route are listed in the order in which they are visited during the judge's travels. Separate the numbers in the route with `-', and precede each route by three spaces.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

The aim of data compression is to reduce redundancy in stored or communicated data. This increases effective data density and speeds up data transfer rates. One possible method to compress any binary message is the following:

Replace any maximal sequence of n 1's with the binary version of n whenever it shortens the length of the message.

For example, the compressed form of the data 11111111001001111111111111110011 becomes 10000010011110011. The original data is 32 bits long while the compressed data is only 17 bits long.

The drawback of this method is that sometimes the decompression process yields more than one result for the original message, making it impossible to obtain the original message. Write a program that determines if the original message can be obtained from the compressed data when the length of the original message (L), the number of 1's in the original message (N) and the compressed data are given. The original message will be no longer than 16 Kbytes and the compressed data will be no longer than 40 bits.

Input

The input file contains several test cases. Each test case has two lines. The first line contains L and N and the second line contains the compressed data.

The last case is followed by a line containing two zeroes.

Output

For each test case, output a line containing the case number (starting with 1) and a message `YES', `NO' or `NOT UNIQUE'. `YES' means that the original message can be obtained. `NO' means that the compressed data has been corrupted and the original message cannot be obtained. `NOT UNIQUE' means that more than one message could have been the original message. Follow the format shown in the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Millions of years ago massive fields of ice carved deep grooves in the mountains of Norway. The sea filled these grooves with water. The Norwegian people call them fjords. This landscape of mountains and water is beautiful, but it makes traveling difficult. The usual scheme is: drive some kilometers, wait for a ferry, cross a fjord with the ferry, drive some more kilometers, and so on until the destination has been reached. To reach a destination as early as possible, most people have the following strategy: drive as fast as allowed (the maximum speed is 80 km/h) to the next ferry, and wait until it goes. Repeat until the destination has been reached.

Since driving fast requires more fuel than driving slow, this strategy is both expensive and harmful to the environment. The new generation of cruise control systems is designed to help. Given the route you want to go, these systems will gather information about the ferries involved, calculate the earliest possible time of arrival at the final destination, and calculate a driving scheme that avoids driving faster than needed. The systems will calculate your road speed so that you board the next ferry the moment it leaves.

Given a route (a sequence of road-pieces and crossings with ferries), you must write a program to calculate the minimal time it takes to complete this route. Moreover, your program must find a driving scheme such that the maximal driving speed at any point during the trip is as small as possible.

Input

The input file contains one or more test cases. Each test case describes a route. A route consists of several sections, each section being either a piece of road or a crossing. The first line in the description contains a single number s (s > 0), which is the number of sections in the route. The next s lines contain the descriptions of the sections. Every line describing a section starts with two names: the place of departure and the place of arrival, followed by either the word ‘road’ or the word ‘ferry’ indicating what kind of section it is. If the section is a road, its length (a positive integer) is given in km. For example:

Dryna Solholmen road 32

Lines describing ferry sections have more information. Following the word “ferry”, the duration of the ferry crossing, in minutes (a positive integer) is given. This is followed by the frequency f (f > 0) of the ferry, that is, the number of times the ferry departs in a single hour. The next f integers give the departure times of the ferry, in ascending order. For example:

Manhiller Fodnes ferry 20 2 15 35

The ferry travels from Manhiller to Fodnes in 20 minutes, and it leaves twice an hour (on 0h15, 0h35, 1h15, 1h35,…). The beginning of the entire trip always starts at a full hour. The sections in a route are consecutive, that is, if a section goes from A to B then the next section starts at B. Every route in the input can be traveled in no more than 10 hours.

The input is terminated by the number zero on a line by itself.

Output

Output for each test case is a single line containing three items. The first item is the test case number. The second is the total travel time for an optimal scheme in the form hh:mm:ss. The third item is the maximal road speed in an optimal scheme rounded to two digits to the right of the decimal point.

Place a blank line after the output of each test case.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

A packet-switching network handles information in small units, breaking long messages into multiple packets before routing. Although each packet may travel along a different path, and the packets comprising a message may arrive at different times or out of order, the receiving computer reassembles the original message correctly.

The receiving computer uses a buffer memory to hold packets that arrive out of order. You must write a program that calculates the minimum buffer size in bytes needed to reassemble the incoming messages when the number of messages (N ), the number of packets (M ), the part of the messages in each packet, the size of each message, and the order of the incoming packets are given.

When each packet arrives, it may be placed into the buffer or moved directly to the output area. All packets that are held in the buffer are available to be moved to the output area at any time. A packet is said to ``pass the buffer" when it is moved to the output area. A message is said to ``pass the buffer" when all of its packets have passed the buffer.

The packets of any message must be ordered so the data in the sequence of packets that pass the buffer is in order. For example, the packet containing bytes 3 through 5 of a message must pass the buffer before the packet containing bytes 6 through 10 of the same message. Messages can pass the buffer in any order, but all packets from a single message must pass the buffer consecutively and in order (but not necessarily at the same time). Note that unlike actual buffering systems, the process for this problem can look ahead at all incoming packets to make its decisions.

The packets consist of data and header. The header contains three numbers: the message number, the starting byte number of data in the packet, and the ending byte number of data in the packet respectively. The first byte number in any message is 1.

For example, the figure below shows three messages (with sizes of 10, 20, and 5 bytes) and five packets. The minimum buffer size for this example is 10 bytes. As they arrive, packet #1 and packet #2 are stored in the buffer. They occupy 10 bytes. Then packet #3 passes the buffer directly. Packet #4 passes the buffer directly and then packet #2 exits the buffer. Finally, packet #5 passes the buffer directly and packet #1 exits the buffer.

Input

The input file contains several test cases. The first line of each test case contains two integers N (1 ≤ N ≤ 5) and M (1 ≤ M ≤ 1000) . The second line contains N integers that are the sizes of messages in bytes; the first number denotes the size of message #1, the second number denotes the size of message #2, and so on. Each of the following M lines describes a packet with three integers: the message number and the starting and ending byte numbers of data in the packet. No packet contains more 64 bytes of data.

The last test case is followed by a line containing two zeroes.

Output

For each test case, print a line containing the test case number (beginning with 1) followed by the minimum buffer size in bytes required to reassemble the original messages. Put a blank line after the output for each test case. Use the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dr. Wolf is an employee of Academic Cipher Machinery (ACM). His work is to secure a plenty of electronic documents by using a cipher machine invented by ACM. Given a document, the cipher machine is capable of making it encrypted whenever an arbitrary prime number, called the key prime, is provided. In mathematics, a prime number is a positive integer which has exactly two distinct positive divisors: 1 and itself. Of course, an encrypted document can be decrypted if the corresponding key prime is available.

As a consequence, Dr. Wolf picked many key primes for those documents to be secured. This seems to be an easy task. However, Dr. Wolf found that it is very difficult for him to remember so many key primes. Therefore, he decided to write down some information of the key primes in a notebook. To ensure safety, only a clue is recorded for each key prime. Let k₀ be a key prime. Dr. Wolf produces a clue C for k₀ according to the following strategy. Initially, C is an empty sequence. In Step 1, select an integer r ≥ 1 as well as r − 1 prime numbers k₁, k₂, . . ., k_r−1 that are not larger than k₀, and then include r into C. In Step 2, for each k_i, 0 ≤ i ≤ r − 1, either include k_i into C, or partition k_i into smaller positive integers (adding up to exactly k_i) and then include the smaller integers into C. Finally, in Step 3, rearrange the integers in C non-decreasingly. For example, a clue for k₀ = 13 is made as follows. In Step 1, select r = 4 and (k₁, k₂, k₃) = (5, 5, 7), and include 4 into C. In Step 2, partition k₀ = 13 into (2, 4, 7), partition k₁ = 5 into (1, 4), partition k₂ = 5 into (2, 3), and partition k₃ = 7 into (1, 1, 5). After Step 2, we have C = (4, 2, 4, 7, 1, 4, 2, 3, 1, 1, 5). Finally, in Step 3, we obtain a clue C = (1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 7).

Dr. Wolf would use clues to recover the original key primes. Unfortunately, Dr. Wolf found that there is a drawback in his strategy: the key prime that can be inferred from a given clue may not be unique! For example, consider the clue C = (1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 7). We may conclude k₀ = 13 by letting r = 4 and (k₀, k₁, k₂, k₃) = (2+4+7, 1+4, 2+3, 1+1+5) = (13, 5, 5, 7). However, we may also conclude k₀ = 17 by letting r = 4 and (k₀, k₁, k₂, k₃) = (2+4+7+4, 1+2, 3, 1+1+5) = (17, 3, 3, 7), or conclude k₀ = 29 by letting r = 2 and (k₀, k₁) = (2+3+4+4+4+5+7, 1+1+1) = (29, 3). To overcome this drawback, Dr. Wolf calls a clue of a key prime k₀ good if the largest key prime that can be inferred from it is k₀. In the above example, C = (1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 7) is good if k₀ = 29. In order to produce good clues, Dr. Wolf needs a program that computes the largest key prime that can be inferred from a given clue. Therefore, Dr. Wolf seeks for your help.

Input

Technical Specification

Output

 For each test case, print a line containing the test case number (beginning with 1) followed by

print “not a valid clue”. (Dr. Wolf may make mistakes in Step 2, during the production of

a clue.) Use the format of the sample output.

Sample Input  Download

Sample Output  Download

Tags

Discuss