# Google Kick Start Archive — Round A 2016 problems

## A. Country Leader

### Problem

The Constitution of a certain country states that the leader is the person with the name containing the greatest number of different alphabet letters. (The country uses the uppercase English alphabet from A through Z.) For example, the name `GOOGLE` has four different alphabet letters: E, G, L, and O. The name `APAC CODE JAM` has eight different letters. If the country only consists of these 2 persons, `APAC CODE JAM` would be the leader.

If there is a tie, the person whose name comes earliest in alphabetical order is the leader.

Given a list of names of the citizens of the country, can you determine who the leader is?

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line with an interger N, the number of people in the country. Then N lines follow. The i-th line represents the name of the i-th person. Each name contains at most 20 characters and contains at least one alphabet letter.

### Output

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 name of the leader.

### Limits

1 ≤ T ≤ 100.
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ N ≤ 100.

#### Small dataset (Test set 1 - Visible)

Each name consists of at most 20 characters and only consists of the uppercase English letters `A` through `Z`.

#### Large dataset (Test set 2 - Hidden)

Each name consists of at most 20 characters and only consists of the uppercase English letters `A` through `Z` and ' '(space).
All names start and end with alphabet letters.

### Sample

Sample Input
```2
3
BOB
JOHNSON
2
A AB C
DEF
```
Sample Output
```Case #1: JOHNSON
Case #2: A AB C

```
In sample case #1, `JOHNSON` contains 5 different alphabet letters('H', 'J', 'N', 'O', 'S'), so he is the leader.

Sample case #2 would only appear in Large data set. The name `DEF` contains 3 different alphabet letters, the name `A AB C` also contains 3 different alphabet letters. `A AB C` comes alphabetically earlier so he is the leader.

## B. Rain

### Problem

There's an island in the sea. The island can be described as a matrix with R rows and C columns, with H[i][j] indicating the height of each unit cell. Following is an example of a 3*3 island:

```3 5 5
5 4 5
5 5 5
```
Sometimes, a heavy rain falls evenly on every cell of this island. You can assume that an arbitrarily large amount of water falls. After such a heavy rain, some areas of the island (formed of one or more unit cells joined along edges) might collect water. This can only happen if, wherever a cell in that area shares an edge (not just a corner) with a cell outside of that area, the cell outside of that area has a larger height. (The surrounding sea counts as an infinite grid of cells with height 0.) Otherwise, water will always flow away into one or more of the neighboring areas (for our purposes, it doesn't matter which) and eventually out to sea. You may assume that the height of the sea never changes. We will use W[i][j] to denote the heights of the island's cells after a heavy rain. Here are the heights of the example island after a heavy rain. The cell with initial height 4 only borders cells with higher initial heights, so water will collect in it, raising its height to 5. After that, there are no more areas surrounded by higher cells, so no more water will collect. Again, note that water cannot flow directly between cells that intersect only at their corners; water must flow along shared edges.
Following is the height of the example island after rain:
```3 5 5
5 5 5
5 5 5
```
Given the matrix of the island, can you calculate the total increased height sum(W[i][j]-H[i][j]) after a heavy rain?

### Input

The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains two numbers R and C indicating the number of rows and columns of cells on the island. Then, there are R lines of C positive integers each. The j-th value on the i-th of these lines gives H[i][j]: the height of the cell in the i-th row and the j-th column.

### Output

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 total increased height.

### Limits

1 ≤ T ≤ 100.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ H[i][j] ≤ 1000.

1 ≤ R ≤ 10.
1 ≤ C ≤ 10.

1 ≤ R ≤ 50.
1 ≤ C ≤ 50.

### Sample

Sample Input
```3
3 3
3 5 5
5 4 5
5 5 5
4 4
5 5 5 1
5 1 1 5
5 1 5 5
5 2 5 8
4 3
2 2 2
2 1 2
2 1 2
2 1 2
```
Sample Output
```Case #1: 1
Case #2: 3
Case #3: 0
```

Case 1 is explained in the statement.

In case 2, the island looks like this after the rain:

```5 5 5 1
5 2 2 5
5 2 5 5
5 2 5 8
```

Case 3 remains unchanged after the rain.

## C. Jane's Flower Shop

### Problem

Jane plans to open a flower shop in the local flower market. The initial cost includes the booth license, furnishings and decorations, a truck to transport flowers from the greenhouse to the shop, and so on. Jane will have to recoup these costs by earning income. She has estimated how much net income she will earn in each of the following M months.

Jane wants to predict how successful her flower shop will be by calculating the IRR (Internal Rate of Return) for the M-month period. Given a series of (time, cash flow) pairs (i, Ci), the IRR is the compound interest rate that would make total cash exactly 0 at the end of the last month. The higher the IRR is, the more successful the business is. If the IRR is lower than the inflation rate, it would be wise not to start the business in the first place.

For example, suppose the initial cost is \$10,000 and the shop runs for 3 months, with net incomes of \$3,000, \$4,000, and \$5,000, respectively. Then the IRR r is given by:

In this case, there is only one rate (~=8.8963%) that satisfies the equation.

Help Jane to calculate the IRR for her business. It is guaranteed that -1 < r < 1, and there is exactly one solution in each test case.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a positive integer M: the number of months that the flower shop will be open. The next line contains M + 1 non-negative integers Ci (0 ≤ i ≤ M). Note that C0 represents the initial cost, all the remaining Cis are profits, the shop will always either make a positive net profit or zero net profit in each month, and will never have negative profits.

### Output

For each test case, output one line containing `Case #x: y`, where `x` is the test case number (starting from 1) and `y` is a floating-point number: the IRR of Jane's business. `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.

### Limits

1 ≤ T ≤ 100.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
C0 > 0.
0 ≤ Ci ≤ 1,000,000,000.

1 ≤ M ≤ 2.

1 ≤ M ≤ 100.

### Sample

Sample Input
```3
2
200 100 100
3
10000 3000 4000 5000
5
3000 100 100 100 100 100
```
Sample Output
```Case #1: 0.000000000000
Case #2: 0.088963394693
Case #3: -0.401790748826
```
In sample case #1, the IRR is 0, Jane just paid back all the money and no interest.

Sample case #2 and #3 will only appear in large dataset.

## D. Clash Royale

### Problem

Clash Royale is a real time strategy card game. Each card has an attack power and a level. Each player picks 8 cards to form a battle deck; the total attack power of a deck is the sum of the attack power of each of its cards. Players fight with each other by placing cards from their battle decks into the battle arena. The winner of a battle is rewarded with coins, which can be used to upgrade cards. Upgrading a card increases its attack power.

After days of arena fighting, Little Shawn has accumulated a total of M coins. He has decided to upgrade some of his cards. Little Shawn has N cards. The i-th card can have any level from 1 through Ki; the attack power for the j-th level is Ai,j. Cards must be upgraded one level at a time; the price to upgrade the i-th card from level j to level j+1 costs Ci,j coins. The i-th card is currently at level Li before Little Shawn has upgraded any cards.

Little Shawn wants to use some or all of his coins to upgrade cards, and then form a deck of exactly 8 cards, so that the deck's total attack power is as large as possible. Can you help him do this? He can upgrade the same card more than once as long as he can afford it, and he does not have to upgrade every card.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with 2 integers M and N, the number of coins and the number of cards that Little Shawn possesses. Then N blocks follow. The i-th block consists of 3 lines describing the i-th card. The first line contains two integers Ki and Li, the maximum possible level and current level of the card. The second line contains Ki integers Ai,1, Ai,2, ..., Ai,Ki, the attack power of each level. The third line contains Ki-1 integers Ci,1, Ci,2, ..., Ci,Ki-1, the number of coins required to upgrade a card that is currently at level 1, 2, ..., Ki-1.

### Output

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 maximal possible total attack power of a deck that Little Shawn can form, using the coins that he has.

### Limits

Time limit: 60 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ Ki ≤ 10.
1 ≤ LiKi.
Ai,j < Ai,j+1.

#### Small dataset (Test set 1 - Visible)

1 ≤ M ≤ 1,000.
N = 8.
1 ≤ Ai,j ≤ 1,000.
1 ≤ Ci,j ≤ 1,000.

#### Large dataset (Test set 2 - Hidden)

1 ≤ M ≤ 1,000,000,000.
8 ≤ N ≤ 12.
1 ≤ Ai,j ≤ 1,000,000,000.
1 ≤ Ci,j ≤ 1,000,000,000.

### Sample

Sample Input
```2
20 8
3 1
1 10 100
1 2
3 1
1 10 100
1 3
3 1
1 10 100
1 4
3 1
1 10 100
1 5
3 1
1 10 100
1 6
3 1
1 10 100
1 7
3 1
1 10 100
1 8
3 1
1 10 100
1 9
30 10
4 1
1 10 100 200
1 2 3
3 1
1 10 100
2 4
3 1
1 10 100
3 6
4 2
1 10 100 200
4 8 16
3 1
1 10 100
5 10
3 1
1 10 100
6 12
3 1
1 10 100
7 14
3 1
1 10 100
8 16
3 1
1 10 100
9 18
3 1
1 10 100
10 20
```
Sample Output
```Case #1: 422
Case #2: 504
```
In sample case #1, you can upgrade the first 4 cards to level 3, upgrade the 5th and 6th card to level 2, keep the last 2 cards level 1. This will cost you (1+2)+(1+3)+(1+4)+(1+5)+1+1=20 coins and the total attack power is 100+100+100+100+10+10+1+1=422 which is the maximal possible we can get.

Sample case #2 will only appear in large dataset.

## Analysis — A. Country Leader

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

## Analysis — B. Rain

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

## Analysis — C. Jane's Flower Shop

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

## Analysis — D. Clash Royale

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

## Statistics — A. Country Leader

### Test set 1: 2262 correct solutions (98.3% solve rate)

First
doodhwala 4:41
youfu 4:51
anurag21raghav 5:25
nfssdq 5:31
ZhouYuChen 5:55

First
doodhwala 4:41
youfu 4:51
nfssdq 5:31
ZhouYuChen 5:55
Raynger 6:06

## Statistics — B. Rain

### Test set 1: 558 correct solutions (24.3% solve rate)

First
deathstar 15:54
dhrumil140396 18:38
Ronnoc 21:41
mrvedsachdeva 22:24
jcvb 22:32

### Test set 2: 502 correct solutions (21.8% solve rate)

First
deathstar 15:54
dhrumil140396 18:38
Ronnoc 21:41
mrvedsachdeva 22:24
jcvb 22:32

## Statistics — C. Jane's Flower Shop

### Test set 1: 1003 correct solutions (43.6% solve rate)

First
amangoelvsec 25:52
himanshujaju 26:29
ZhouYuChen 31:27
vivek.n.2 32:23
Huge.Chauhan 33:34

### Test set 2: 319 correct solutions (13.9% solve rate)

First
himanshujaju 26:29
ZhouYuChen 31:27
Huge.Chauhan 33:34
wwwwodddd 34:51
Fierce grey fox 36:32

## Statistics — D. Clash Royale

### Test set 1: 200 correct solutions (8.7% solve rate)

First
huanyingtianhe 45:39
james0zan 45:52
nfssdq 64:49
jcvb 66:22
himanshujaju 69:15

First
nfssdq 64:49
jcvb 66:22
ZhouYuChen 81:05
wwwwodddd 86:06
Jason911 88:20