We're trotting through the Round 1s one weekend at a time, and Round 1B
featured a lot of horsepower. Perhaps you used a test harness, or
accidentally started your Java program with
`public static void mane`

, or tried to print in C++ using
`colt << `

, or attempted to reserve memory in C using
`gallop`

. At least we didn't give you a problem on the
Canter set or make you
write an
(e)quine!

*Steed 2: Cruise Control* riffed on a
1990s movie franchise;
its author came up with it while stuck in slow traffic! It was a potentially
complicated-looking problem that turned out to have a straightforward
solution. In *Stable Neigh-bors*, figuring out how to arrange unicorns
was only half the fun; the implementation was potentially tricky! Finally,
*Pony Express* was a graph problem with an unconventional solution.

This round's hardest problem proved significantly easier than Round 1A's, allowing JAPLJ to claim first place really early with a perfect score with no wrong tries in under 40 minutes! When the dust settled, 347 contestants achieved perfect scores. About 800 other contestants managed to solve all problems except one Large, and most of them had enough points or a low enough penalty to qualify to Round 2.

Our top 1,000 from this round advance to Round 2, joining the 1,000 who advanced from Round 1A. There's still one more chance to advance in Round 1C next week!

**Cast**

Problem A (Steed 2: Cruise Control): Written and prepared by Ian Tullis.

Problem B (Stable Neigh-bors): Written and prepared by Ian Tullis.

Problem C (Pony Express): Written by Pablo Heiber. Prepared by Philipp Hoffmann.

Solutions and other problem preparation and review by Liang Bai, Shane Carr, Md Mahbubul Hasan, Taman (Muhammed) Islam, Lalit Kundu, Petr Mitrichev, Rohan Mukkamala, Igor Naverniouk, Chieu Nguyen, and Josef Ziegler.

Analysis authors:

- Steed 2: Cruise Control: Ian Tullis
- Stable Neigh-bors: Ian Tullis
- Pony Express: Pablo Heiber

Annie is a bus driver with a high-stress job. She tried to unwind by going on a Caribbean cruise, but that also turned out to be stressful, so she has recently taken up horseback riding.

Today, Annie is riding her horse to the east along a long and narrow one-way
road that runs west to east. She is currently at kilometer 0 of the road, and
her destination is at kilometer **D**; kilometers along the road are
numbered from west to east.

There are **N** other horses traveling east on the same road; all of them
will go on traveling forever, and all of them are currently between Annie's
horse and her destination. The i-th of these horses is initially at kilometer
**K _{i}** and is traveling at its maximum speed of

Horses are very polite, and a horse H_{1} will not pass (move ahead
of) another horse H_{2} that started off ahead of H_{1}. (Two
or more horses can share the same position for any amount of time; you may
consider the horses to be single points.) Horses (other than Annie's) travel
at their maximum speeds, except that whenever a horse H_{1} catches
up to another slower horse H_{2}, H_{1} reduces its speed to
match the speed of H_{2}.

Annie's horse, on the other hand, does not have a maximum speed and can travel at any speed that Annie chooses, as long as it does not pass another horse. To ensure a smooth ride for her and her horse, Annie wants to choose a single constant "cruise control" speed for her horse for the entire trip, from her current position to the destination, such that her horse will not pass any other horses. What is the maximum such speed that she can choose?

The first line of the input gives the number of test cases, **T**;
**T** test cases follow. Each test case begins with two integers **D**
and **N**: the destination position of all of the horses (in kilometers)
and the number of other horses on the road. Then, **N** lines follow. The
i-th of those lines has two integers **K _{i}** and

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is the maximum constant speed (in kilometers per hour) that Annie can use
without colliding with other horses. `y`

will be considered
correct if it is within an absolute or relative error of 10^{-6} of
the correct answer. See the
FAQ for an explanation of what
that means, and what formats of real numbers we accept.

1 ≤ **T** ≤ 100.

0 < **K _{i}** <

1 ≤

Time limit: 20 seconds per test set.

Memory limit: 1GB.

1 ≤ **N** ≤ 2.

1 ≤ **N** ≤ 1000.

Sample Input

3 2525 1 2400 5 300 2 120 60 60 90 100 2 80 100 70 10

Sample Output

Case #1: 101.000000 Case #2: 100.000000 Case #3: 33.333333

In Sample Case #1, there is one other (very slow!) horse on the road; it will reach Annie's destination after 25 hours. Anything faster than 101 kilometers per hour would cause Annie to pass the horse before reaching the destination.

In Sample Case #2, there are two other horses on the road. The faster horse will catch up to the slower horse at kilometer 240 after 2 hours. Both horses will then go at the slower horse's speed for 1 more hour, until the horses reach Annie's destination at kilometer 300. The maximum speed that Annie can choose without passing another horse is 100 kilometers per hour.

You are lucky enough to own **N** pet unicorns. Each of your unicorns has
either one or two of the following kinds of hairs in its mane: red hairs,
yellow hairs, and blue hairs. The color of a mane depends on exactly which
sorts of colored hairs it contains:

- A mane with only one color of hair appears to be that color. For example, a mane with only blue hairs is blue.
- A mane with red and yellow hairs appears orange.
- A mane with yellow and blue hairs appears green.
- A mane with red and blue hairs appears violet.

You have **R**, **O**, **Y**, **G**, **B**, and **V**
unicorns with red, orange, yellow, green, blue, and violet manes,
respectively.

You have just built a circular stable with **N** stalls, arranged in a
ring such that each stall borders two other stalls. You would like to put
exactly one of your unicorns in each of these stalls. However, unicorns need
to feel rare and special, so no unicorn can be next to another unicorn that
shares at least one of the hair colors in its mane. For example, a unicorn
with an orange mane cannot be next to a unicorn with a violet mane, since
both of those manes have red hairs. Similarly, a unicorn with a green mane
cannot be next to a unicorn with a yellow mane, since both of those have
yellow hairs.

Is it possible to place all of your unicorns? If so, provide any one arrangement.

The first line of the input gives the number of test cases, **T**. **T**
test cases follow. Each consists of one line with seven integers: **N**,
**R**, **O**, **Y**, **G**, **B**, and **V**.

For each test case, output one line containing `Case #x: y`

, where
`x`

is the test case number (starting from 1) and `y`

is `IMPOSSIBLE`

if it is not possible to place all the unicorns,
or a string of **N** characters representing the placements of unicorns in
stalls, starting at a point of your choice and reading clockwise around the
circle. Use `R`

to represent each unicorn with a red mane,
`O`

to represent each unicorn with an orange mane, and so on with
`Y`

, `G`

, `B`

, and `V`

. This
arrangement must obey the rules described in the statement above.

If multiple arrangements are possible, you may print any of them.

Time limit: 20 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

3 ≤ **N** ≤ 1000.

**R** + **O** + **Y** + **G** + **B** + **V** =
**N**.

0 ≤ Z for each Z in {**R**, **O**, **Y**, **G**, **B**,
**V**}.

**O** = **G** = **V** = 0. (Each unicorn has only one hair color in
its mane.)

No restrictions beyond the general limits. (Each unicorn may have either one
or two hair colors in its mane.)

Sample Input

4 6 2 0 2 0 2 0 3 1 0 2 0 0 0 6 2 0 1 1 2 0 4 0 0 2 0 0 2

Sample Output

Case #1: RYBRBY Case #2: IMPOSSIBLE Case #3: YBRGRB Case #4: YVYV

Note that the last two sample cases would not appear in the Small dataset.

For sample case #1, there are many possible answers; for example, another is
`BYBRYR`

. Note that `BYRYRB`

would *not* be a
valid answer; remember that the stalls form a ring, and the first touches
the last!

In sample case #2, there are only three stalls, and each stall is a neighbor of the other two, so the two unicorns with yellow manes would have to be neighbors, which is not allowed.

For sample case #3, note that arranging the unicorns in the same color
pattern as the Google logo (`BRYBGR`

) would not be valid, since a
unicorn with a blue mane would be a neighbor of a unicorn with a green mane,
and both of those manes share blue hairs.

In sample case #4, no two unicorns with yellow manes can be neighbors, and no two unicorns with violet manes can be neighbors.

It's the year 1860, and the Pony Express is the fastest mail delivery system
joining the East and West coasts of the United States. This system
serves **N** different cities. In each city, there is one horse (as in the
expression "one-horse town"); each horse travels at a certain constant speed
and has a maximum total distance it can travel before it becomes too tired to
continue.

The Pony Express rider starts off on the starting city's horse. Every time the rider reaches a city, they may continue to use their current horse or switch to that city's horse; switching is instantaneous. Horses never get a chance to rest, so whenever part of a horse's maximum total distance is "used up", it is used up forever! When the rider reaches the destination city, the mail is delivered.

The routes between cities were established via complicated negotiations between company owners, lawmakers, union delegates, and cousin Pete. That means that the distances between cities do not necessarily follow common sense: for instance, they do not necessarily comply with the triangle inequality, and the distance from city A to city B might be different from the distance from city B to city A!

You are a time traveling entrepreneur, and you have brought a fast computer from the future. A single computer is not enough for you to set up an e-mail service and make the Pony Express obsolete, but you can use it to make optimal routing plans for the Pony Express. Given all data about routes between cities and the horses in each city, and a list of pairs of starting and ending cities, can you quickly calculate the minimum time necessary for each delivery? (You should treat all of these deliveries as independent; using cities/horses on one route does not make them unavailable on other routes.)

The first line of the input gives the number of test cases, **T**.
**T** test cases follow. Each test case is described as follows:

- One line with two integers:
**N**, the number of cities with horses, and**Q**, the number of pairs of stops we are interested in. Cities are numbered from 1 to**N**. -
**N**lines, each containing two integers**E**_{i}, the maximum total distance, in kilometers, the horse in the i-th city can go and**S**_{i}, the constant speed, in kilometers per hour, at which the horse travels. -
**N**lines, each containing**N**integers. The j-th integer on the i-th of these lines,**D**_{ij}, is -1 if there is no direct route from the i-th to the j-th city, and the length of that route in kilometers otherwise. -
**Q**lines containing two integers**U**_{k}and**V**_{k}, the starting and destination point, respectively, of the k-th pair of cities we want to investigate.

For each test case, output one line containing `Case #x: y`

, where _{1}
y_{2} ... y_{Q}`x`

is the
test case number (starting from 1) and `y`

is the
minimum time, in hours, to deliver a letter from city _{k}**U**_{k} to
city **V**_{k}.

Each `y`

will be considered correct if it is within an
absolute or relative error of 10_{k}^{-6} of the correct answer. See
the FAQ for an explanation of
what that means, and what formats of real numbers we accept.

Time limit: 20 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100.

2 ≤ **N** ≤ 100.

1 ≤ **E**_{i} ≤ 10^{9}, for all i.

1 ≤ **S**_{i} ≤ 1000, for all i.

-1 ≤ **D**_{ij} ≤ 10^{9}, for all i, j.

**D**_{ii} = -1, for all i. (There are no direct routes from a city to itself.)

**D**_{ij} ≠ 0, for all i, j.

**U**_{k} ≠ **V**_{k}, for all k.

It is guaranteed that the delivery from **U**_{k} to **V**_{k} can be
accomplished with the given horses, for all k.

**U**_{l} ≠ **U**_{m} and/or **V**_{l} ≠ **V**_{m},
for all different l, m. (No ordered pair of cities to investigate is repeated within a test case.)

**D**_{ij} = -1, for all i, j where i + 1 ≠ j.
(The cities are in a single line; each route goes from one city to the next city in line.)

**Q** = 1.

**U**_{1} = 1.

**V**_{1} = **N**.
(The only delivery to calculate is between the first and last cities in the line).

1 ≤ **Q** ≤ 100.

1 ≤ **U**_{k} ≤ **N**, for all k.

1 ≤ **V**_{k} ≤ **N**, for all k.

Sample Input

3 3 1 2 3 2 4 4 4 -1 1 -1 -1 -1 1 -1 -1 -1 1 3 4 1 13 10 1 1000 10 8 5 5 -1 1 -1 -1 -1 -1 1 -1 -1 -1 -1 10 -1 -1 -1 -1 1 4 4 3 30 60 10 1000 12 5 20 1 -1 10 -1 31 10 -1 10 -1 -1 -1 -1 10 15 6 -1 -1 2 4 3 1 3 2

Sample Output

Case #1: 0.583333333 Case #2: 1.2 Case #3: 0.51 8.01 8.0

Note that the last sample case would not appear in the Small dataset.

In Case #1 there are two options: use the horse in city 1 for the entire trip, or change horses in city 2. Both horses have enough endurance, so both options are viable. Since the horse in city 2 is faster, it is better to change, for a total time of 1/3 + 1/4.

In Case #2 there are two intermediate cities in which you can change horses. If you change horses in city 2, however, your new horse, while blazingly fast, will not have enough endurance, so you will be forced to change again in city 3. If you keep your horse, you will have the option to change horses (or not) in city 3. So, the three options, with their total times, are:

- Change horses in both city 2 and 3 (1/10 + 1/1000 + 10/8 = 1.351).
- Change horses just in city 3 (2/10 + 10/8 = 1.45).
- Never change horses (12/10 = 1.2).

In Case #3, there are lots of alternatives for each delivery. The optimal one for the first delivery (city 2 to city 4) is to go to city 1 in time 10/1000, change horses, and then go to cities 2, 3 and 4, in that order, using the horse from city 1, which takes time (10 + 10 + 10) / 60.

For the second delivery (city 3 to city 2) you have no choice but to first go to city 4 which takes time 10/5. Your relatively fast horse does not have enough endurance to get anywhere else, so you need to grab the horse in city 4. You could use it to get directly to city 1 in time 15, but that would be slower than riding it to city 2 in time 6 and then using the blazingly fast horse in city 2 to get to city 1 in just 10/1000 extra time.

In the third delivery (city 3 to city 1) of Case #3 it is optimal to use the first two steps of the previous one, for a total time of 10/5 + 6 = 8.

Pop quiz, hotshots! This problem seems pretty complicated at first glance. What do you do?

One natural strategy is to try binary searching on Annie's speed, but it is difficult to directly determine whether a given speed avoids passing another horse; the input data alone does not tell us where each horse is at any given time, because horses might slow other horses down. In theory, we could figure out when faster horses catch up to slower horses and slow down, determine the exact path of each horse, and check whether our chosen speed crosses any of those paths. With only up to two horses in test set 1, this sort of calculation is feasible, but it would be laborious for test set 2.

However, we can avoid all of that work via some observations. To maximize
cruising speed, Annie's horse should reach the destination at exactly the
same time as the horse ahead of her (let's call it Horse A); there is no
reason to leave a gap. Either Horse A will reach the destination without
having to slow down (and so it will be the one that directly limits Annie's
speed), or it will be slowed down at some point by the horse ahead of it
(let's call it Horse B). The same is true for Horse B: either it will never
have to slow down (and so it will be the one that ultimately limits Annie's
speed), or it will be slowed down by the horse ahead of *it*, and so on.
So there will be a single "limiting horse" on the road that ultimately
determines how fast Annie's horse can reach the destination. We claim that
this "limiting horse" is the only horse that matters, and we can disregard
all of the others!

It is easy to see that we can ignore the horses to the east of the limiting
horse; they will reach and pass the destination before the limiting horse
gets there. What about the "intermediate horses" between Annie and the
limiting horse? We know from the way we have defined the limiting horse that
every intermediate horse will catch up to the limiting horse before reaching
the destination. (If one did not, then *it* would be the limiting
horse.) Suppose that Annie chooses a cruising speed that gets her to the
destination at exactly the same time as the limiting horse. We certainly
cannot go faster than this. Moreover, this speed is safe: it cannot possibly
cause Annie to pass any of the intermediate horses. If she were going fast
enough to overtake an intermediate horse, then she would definitely be
going fast enough to pass the limiting horse, since every intermediate
horse will catch up to the limiting horse. This would cause a contradiction.
Therefore, we do not need to worry about the intermediate horses or their
interactions with each other.

So, once we have identified the limiting horse, the strategy is simple: go at
the exact speed that will cause Annie to reach the destination at the same
time as the limiting horse. This speed can be found in constant time. We could
identify the limiting horse directly via the argument in our third paragraph
above, but even this would be unnecessary work. Instead, for each horse in
turn, we can pretend that it is the limiting horse and calculate the cruising
speed that it would force. Then the smallest of those speeds is our answer.
(If any horse allows a faster cruising speed than another, it cannot be the
limiting horse, because that cruising speed would cause Annie to pass the
true limiting horse.) This takes O(**N**) time.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In the Small dataset, all of the unicorns have manes with only a single
primary color: red, yellow, or blue. None of these manes share any primary
colors, so our only restriction is that two unicorns with the same mane color
cannot be next to each other. However, one color might be so common that it
is impossible to avoid putting two unicorns with that color next to each
other. If we space unicorns with the most common color out, with some other
unicorn between each pair of them, then we can accommodate up to
floor(**N**/2) of the most common color. If we have more than that number
with any color, the case is impossible.

Otherwise, we can extend this "every other stall" strategy to work for any
case. Start at some arbitrary position on the ring of stalls, and place
unicorns in the first, third, fifth, etc. stalls, all the way around the
ring. When you reach the starting point again, continue to place unicorns in
the second, fourth, sixth, etc. stalls. As you do this, place all of the
unicorns with the most common mane color, and then all the unicorns with the
next most common mane color, and then all the rest. Because all of these
colors have a frequency no greater than floor(**N**/2), it is not possible
for this placement strategy to put two unicorns with the same color next to
each other.

The Large dataset introduces more complications. Unicorns with a secondary-colored mane (orange, green, or violet) can only have one type of neighbor. An orange-maned unicorn must be next to two blue-maned unicorns; similarly, a yellow must be next to purples, and a red must be next to greens.

How many instances of a primary color do we need to "surround" all unicorns
with the corresponding secondary-colored mane? If the secondary color and its
primary neighbor are the only two colors available, then there must be equal
numbers of those two colors. Otherwise, if there are *S* instances of
the secondary color, we need at least *S* + 1 instances of the primary
color.

Moreover, we might as well put all secondary colors of the same type together (separated by the primary color, of course) in a single chain. Any valid arrangement without that property can be rearranged to have that property. For instance, suppose that we have two separate R-G-R chains separated by two other valid chains Z and Z': R-G-R-Z-R-G-R-Z'-. We can just rearrange this to R-G-R-G-R-Z-R-Z'-, which must also be valid.

A final useful insight is that an R-G-R-G-R chain, for example, acts just like a single R in terms of what can neighbor it on either side. So one strategy for the Large is: first, check for the case mentioned above in which only one secondary color and its neighboring primary color are present. Otherwise, for each secondary color, check that there are enough primary-color unicorns to surround the secondary-color unicorns in a chain. Then pretend that each of these chains is just a single instance of the primary-colored mane from that chain; this reduces the problem to primary colors, and the algorithm for the Small dataset works. You can substitute each chain back in (for some arbitrary instance of the appropriate primary color) once that algorithm has finished.

These Small and Large solutions run in O(**N**) time, and they are bound
by reading the input, checking color frequencies, and printing the output.
Other, more complex solutions (e.g., dynamic programming) also exist.

Test Data

We recommend that you practice debugging solutions without looking at the test data.

In the Small dataset, we are given a line of cities and the distances between them, and we want to go from the first to the last city in the line. However, we need to minimize the time and not the distance, and the obvious way to transform between the two (divide by speed) does not work directly, because the horses we can use have different speeds. The solution, as in many minimization algorithms on a path that only moves forward, is to use dynamic programming.

Let us define f(i) as the quickest way to get from city i to the finish line, assuming we start using the horse at city i. Of course, f(1) is the answer to the only query.

We do not know where we need to change horses, but we can try every possible intermediate city j to change horses, thus completely defining f(i) by:

- f(i) = min { distance(i, j) / speed(i) + f(j) : for all j such that distance(i, j) ≤
endurance(i) }, for i <
**N**. - f(
**N**) = 0.

This solves the problem in O(**N**^{2}) because the domain of f is of size **N**
and the iteration to calculate each value of the domain takes time O(**N**) if we memoize the
results. There are other dynamic programming approaches that also work in the same amount of time.

In the Large dataset, we are given a graph G of cities with distances between them instead of just a line, but the setup of the problem is otherwise the same.

As mentioned above, one relatively unusual feature of this graph problem is that the desired result (time) is not in the same units as the weights of the graph's edges (distance). Moreover, the obvious way to transform between the two (speed) is not a constant. This observation leads to a key insight: we should construct a new graph with weights of time instead of distance. That way, we can apply a shortest path algorithm to get the result we want.

We can do this by defining a graph G' that has the same nodes as G, but in which the weight of edge (i, j) is the time that it takes to go from city i to city j. As we said above, there is no fixed speed, but we can fix it. The edge (i, j) then represents the time it takes to go from city i to city j using a single horse, and the obvious choice is to use the horse at the departure city i. Let us call that horse h. In this way, the edge (i, j) on G' represents a path on G, traversed using a single horse. That means the edge (i, j) exists if and only if there is a path between i and j in G with distance less than or equal to h's endurance. Moreover, the weight (i, j) is a time now defined by a single speed, h's speed, and thus it is just the distance between i and j in G, divided by h's speed. You can see that a minimum path from a to b in G' represents a succession of edges in G', that is, a succession of single-horse paths in G, which is exactly what a solution looks like!

Since the limits are low enough, and we need all shortest paths in G to construct G', and many shortest paths in G' to answer many queries, the best option is to use an all-pairs shortest path algorithm. Floyd-Warshall is the easiest and fastest to implement, but others would work too. To also check for existence of paths, you can use the trick of setting weights to "infinity", that is, a distance too large for an actual shortest path (larger than maximum distance × number of total edges). Thus, an infinity distance simply means the edge or path does not exist in the graph.

To summarize, this pseudocode solves the problem:

- Apply Floyd-Warshall to input G getting distances between all pairs of nodes.
- Create G' by adding all edges (i, j) such that the distance between i and j in G is less than or equal to the horse starting at city i's endurance, and set their weights to that same distance divided by that horse's speed.
- Apply Floyd-Warshall to G' to get minimum times between all pairs of nodes.
- Read queries and answer immediately from the output of the last step.

This solution takes time O(**N**^{3}). Both uses of Floyd-Warshall take time
O(**N**^{3}), and creating G' as an adjacency matrix only takes time
O(**N**^{2}).

Test Data

We recommend that you practice debugging solutions without looking at the test data.