In the last match of Round 1, the competition was as exciting as the first two.

Interestingly, when the author created the first problem with a nice story, he did not notice that it actually was a mixture of flavors from the first problems (Multi-base Happiness and The Next Number) from the other two matches. The second problem turns out to be a simple exercise in geometry. And the third one, standard dynamic programming.

183 people enjoyed full scores, while 2337 contestants has at least one correct submission. As in Round 1B, solving all three small inputs correctly was not sufficient to advance.

We hope the problems were educational and pleasant, and all of you had fun.

Cast

Problem A. *All Your Base* Written and prepared by Bartholomew Furrow.

Problem B. *Center of Mass* Written by Xiaomin Chen. Prepared by Xiaomin Chen and Igor Naverniouk.

Problem C. *Bribe the Prisoners* Written by Nandini Seshadri. Prepared by John Dethridge.

Contest analysis presented by Bartholomew Furrow, Xiaomin Chen, and Marius Andrei.

Solutions and other problem preparation provided by Marius Andrei, Tomek Czajka, Derek Kisman, Petr Mitrichev, Fábio Moreira, and Daniel Rocha.

In A.D. 2100, aliens came to Earth. They wrote a message in a cryptic language, and next to it they wrote a series of symbols. We've come to the conclusion that the symbols indicate a number: the number of seconds before war begins!

Unfortunately we have no idea what each symbol means. We've decided that each symbol indicates one digit, but we aren't sure what each digit means or what base the aliens are using. For example, if they wrote "ab2ac999", they could have meant "31536000" in base 10 -- exactly one year -- or they could have meant "12314555" in base 6 -- 398951 seconds, or about four and a half days. We are sure of three things: the number is positive; like us, the aliens will never start a number with a zero; and they aren't using unary (base 1).

Your job is to determine the minimum possible number of seconds before war begins.

The first line of input contains a single integer, **T**. **T** test cases follow. Each test case is a string on a line by itself. The line will contain only characters in the 'a' to 'z' and '0' to '9' ranges (with no spaces and no punctuation), representing the message the aliens left us. The test cases are independent, and can be in different bases with the symbols meaning different things.

For each test case, output a line in the following format:

Case #WhereX:V

Time limit: 20 seconds per test set.

Memory limit: 1 GB.

1 ≤ **T** ≤ 100

The answer will never exceed 10^{18}

1 ≤ the length of each line < 10

1 ≤ the length of each line < 61

Sample Input

3 11001001 cats zig

Sample Output

Case #1: 201 Case #2: 75 Case #3: 11

You are studying a swarm of **N** fireflies. Each firefly is moving in a straight line at a constant speed. You are standing at the center of the universe, at position

You know the position and velocity of each firefly at t = 0, and are only interested in **N** fireflies at time t. Let d(t) be the distance between your position and M(t) at time t. Find the minimum value of d(t), d_{min}, and the earliest time when d(t) = d_{min}, t_{min}.

The first line of input contains a single integer **T**, the number of test cases. Each test case starts with a line that contains an integer **N**, the number of fireflies, followed by **N** lines of the form

x y z vx vy vzEach of these lines describes one firefly: (x, y, z) is its initial position at time t = 0, and (vx, vy, vz) is its velocity.

For each test case, output

Case #X: dwhere_{min}t_{min}

Time limit: 20 seconds per test set.

Memory limit: 1 GB.

All the numbers in the input will be integers.

1 ≤ **T** ≤ 100

The values of x, y, z, vx, vy and vz will be between -5000 and 5000, inclusive.

3 ≤ **N** ≤ 10

3 ≤ **N** ≤ 500

Sample Input

3 3 3 0 -4 0 0 3 -3 -2 -1 3 0 0 -3 -1 2 0 3 0 3 -5 0 0 1 0 0 -7 0 0 1 0 0 -6 3 0 1 0 0 4 1 2 3 1 2 3 3 2 1 3 2 1 1 0 0 0 0 -1 0 10 0 0 -10 -1

Sample Output

Case #1: 0.00000000 1.00000000 Case #2: 1.00000000 6.00000000 Case #3: 3.36340601 1.00000000

Given **N** points (x_{i}, y_{i}, z_{i}), their center of the mass is the point (x_{c}, y_{c}, z_{c}), where:

x_{c}= (x_{1}+ x_{2}+ ... + x_{N}) / N y_{c}= (y_{1}+ y_{2}+ ... + y_{N}) / N z_{c}= (z_{1}+ z_{2}+ ... + z_{N}) / N

In a kingdom there are prison cells (numbered 1 to **P**) built to form a straight line segment. Cells number **i** and **i+1** are adjacent, and prisoners in adjacent cells are called "neighbours." A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner's neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to *his* other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell **P**, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell **A**, all prisoners housed on either side of cell **A** - until cell 1, cell **P** or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of **Q** prisoners to be released in **Q** days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

The first line of input gives the number of cases, **N**. **N** test cases follow. Each case consists of 2 lines.
The first line is formatted as

P Qwhere

This will be followed by a line with

For each test case, output one line in the format

Case #X: Cwhere

Memory limit: 1 GB.

1 ≤ **N** ≤ 100

**Q** ≤ **P**

Each cell number is between 1 and **P**, inclusive.

Time limit: 20 seconds.

1 ≤ **P** ≤ 100

1 ≤ **Q** ≤ 5

Time limit: 30 seconds.

1 ≤ **P** ≤ 10000

1 ≤ **Q** ≤ 100

Sample Input

2 8 1 3 20 3 3 6 14

Sample Output

Case #1: 7 Case #2: 35

In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.

```
IN A.D. 2101
```

WAR WAS BEGINNING

...

CATS: HOW ARE YOU GENTLEMEN !!

CATS: ALL YOUR BASE ARE BELONG TO US

This problem, of course, takes place in the halcyon days of A.D. 2100, before all our base became belong to Cats. It also firmly demonstrates that its author still lives in A.D. 2001.

In this problem our job is to read a series of symbols and interpret them as digits of a number in some base. In order to *minimize* the number, we'll want to use the smallest base possible. We can check how many different characters show up in the number; if that number of characters is **k**, then we can work in base `max(`

(base 1 is not allowed). From there, it's simply a matter of assigning values from 0 to **k**,2)**k** to all of the characters. We can't start with a 0, so we should make the first digit a 1; and after that, simply assign the lowest number available to characters from left to right. In that way, "ab2ac999" becomes "10213444" in base 5, or 85499 seconds.

The following is a brief solution in Python:

import sys N = int(sys.stdin.readline().strip()) for qw in range(1, N+1): print 'Case #%d:' % qw, num = sys.stdin.readline().strip() values = {num[0]: 1} for c in num: if c not in values: sz = len(values) if sz == 1: values[c] = 0 else: values[c] = sz result = 0 base = max(len(values), 2) for c in num: result *= base result += values[c] print result

One final note: on our official Google Group, user Damien pointed out the following:

"The first example case in All Your Base implies the alien language uses a left-right notation. If that assumption is wrong and they actually used right-left you'd be 54 seconds late for the war: 11001001 binary = 201 decimal, but the reverse 10010011 is 147 decimal. Dangerous assumption to make don't you think? :-)"

I hate to say it, but he's right; even though 2219 people solved this problem, we may still be taken by surprise!

Test Data

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

Let P_{i} and V_{i} be the initial position and the velocity of the i-th firefly; its position at time t is given by P_{i} + tV_{i}. Therefore, the center of mass at time t is

M(t) = ∑ (Pwhere P_{i}+ t V_{i}) / n = ∑ P_{i}/ n + t ∑ V_{i}/ n = P_{ave}+ t V_{ave},

So, the problem is actually finding the closest distance from a point (the origin) to a ray, an elementary geometry problem. This is an easy exercise with many possible short solutions. One can use basic manipulations or calculus to derive the exact formula for the answers. One may also notice that the distance function d(t) is convex in t, thus use trinary search to find the best t. As always, we encourage the readers to download correct solutions from the scoreboard.

We did the calculations using vectors. It can also be carried out with 3-dimensional coordinates.

The exact formula of the distance from a point to a line in 3d space.

Test Data

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

This problem is solved by dynamic programming. For each pair of cells a ≤ b, we want to compute dp[a][b], the best answer if we only have prisoners in cells from a to b, inclusive. Once we decide the location of c, the first prisoner between a and b to be released, we face the smaller sub-problems dp[a][c-1] and dp[c+1][b]. The final answer we want is dp[1][P].

It is clear we only need to solve those dp[a][b]'s where both a and b are either 1, P, or adjacent to a prisoner to be released. Thus the number of sub-problems we need to solve is just O(Q^{2}).

Here is the annotated judge's solution.

int p[200]; // prisoners to be released. map<pair<int, int>, int> dp; // Finds the minimum amount of gold needed, // if we only consider the cells from a to b, inclusive. int Solve(int a, int b) { // First, look up the cache to see if the // result is computed before. pair<int, int> pr(a, b); if(mp.find(pr) != mp.end()) return mp[pr]; // Start the computation. int r = 0; for(int i=0; i<Q; i++) { if(p[i] >= a && p[i] <= b) { int tmp = (b-a) + Solve(a, p[i]-1) + Solve(p[i]+1, b); if (!r || tmp<r) r=tmp; } } mp[pr]=r; return r; }

Test Data

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