# Google Kick Start Archive — Round C 2016 problems

## A. Monster Path

### Problem

Codejamon is a mobile game in which monster trainers walk around in the real world to catch monsters. You have an old smartphone with a short battery life, so you need to choose your path carefully to catch as many monsters as possible.

Suppose the Codejamon world is a rectangular grid with R rows and C columns. Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0. You start in the cell in the Rsth row and the Csth column. You will take a total of S unit steps; each step must be to a cell sharing an edge (not just a corner) with your current cell.

Whenever you take a step into a cell in which you have not already caught a monster, you will catch the monster in that cell with probability P if the cell has a monster attractor, or Q otherwise. If you do catch the monster in a cell, it goes away, and you cannot catch any more monsters in that cell, even on future visits. If you do not catch the monster in a cell, you may still try to catch the monster on a future visit to that cell. The starting cell is special: you have no chance of catching a monster there before taking your first step.

If you plan your path optimally before making any move, what is the maximum possible expected number of monsters that you will be able to catch?

The battery can only support limited steps, so hurry up!

### 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 of five integers: R, C, Rs, Cs and S. R and C are the numbers of rows and columns in the grid; Rs and Cs
are the numbers of the row and column of your starting position, and S is the number of steps you are allowed to take.

The next line contains two decimals P and Q, where P is the probability of meeting a monster in cells with a monster attractor, and Q is the probability of meeting a monster in cells without a monster attractor. P and Q are each given to exactly four decimal places.

Each of the next R lines contains contains C space-separated characters; the j-th character of the i-th line represents the cell at row i and column j. Each element is either `.` (meaning there is no attractor in that cell) or `A` (meaning there is an attractor in that cell).

### 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 largest possible expected number of monsters that the player can catch in the given amount of steps.

`y` will be considered correct if `y` 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.
0 ≤ Rs < R.
0 ≤ Cs < C.
0 ≤ Q < P ≤ 1.

1 ≤ R ≤ 10.
1 ≤ C ≤ 10.
0 ≤ S ≤ 5.

1 ≤ R ≤ 20.
1 ≤ C ≤ 20.
0 ≤ S ≤ 9.

### Sample

Sample Input
```2
4 4 0 0 5
0.8000 0.2000
. . . .
. . . .
. . A .
. A . A
10 10 9 1 4
0.6121 0.1000
. . A A . . . . . .
A . . . . . . . . .
. . A . . . . A . .
. . . A A . . . . .
. A A A . . . . . A
A . A A . . . . A .
. A . . . . . A . .
. . . . A A . . . .
. . A . . . A . . A
. . . . A . . A . .```
Sample Output
```Case #1: 1.6000000
Case #2: 1.0495336```

In Case #1, one of the best paths is (0,0)->(0,1)->(0,2)->(1,2)->(2,2)->(2,3). On this path, the expected number of monsters that you will catch is 0.2 + 0.2 + 0.2 + 0.8 + 0.2 = 1.6. Remember that there is no chance of catching a monster before taking your first step, which is why there are five probabilities in the calculation, not six.

In Case #2, one of the best paths is (9,1)->(9,2)->(8,2)->(8,3)->(8,2). On this path, the expected number of monsters that you will catch is 0.1 + 0.6121 + 0.1 + 0.23743359 = 1.04953359. Since we accept results within an absolute or relative error of 10-6 of the correct answer (1.04953359), 1.0495336 is accepted.

## B. Safe Squares

### Problem

Codejamon trainers are actively looking for monsters, but if you are not a trainer, these monsters could be really dangerous for you. You might want to find safe places that do not have any monsters!

Consider our world as a grid, and some of the cells have been occupied by monsters. We define a safe square as a grid-aligned D × D square of grid cells (with D ≥ 1) that does not contain any monsters. Your task is to find out how many safe squares (of any size) we have in the entire world.

### 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 three integers, R, C, and K. The grid has R rows and C columns, and contains K monsters. K more lines follow; each contains two integers Ri and Ci, indicating the row and column that the i-th monster is in. (Rows are numbered from top to bottom, starting from 0; columns are numbered from left to right, starting from 0.)

### 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 the total number of safe zones for this test case.

### Limits

Time limit: 60 seconds per test set.
Memory limit: 1GB.

1 ≤ T ≤ 20.

(Ri, Ci) ≠ (Rj, Cj) for i ≠ j. (No two monsters are in the same grid cell.)

0 ≤ Ri < R, i from 1 to K

0 ≤ Ci < C, i from 1 to K

1 ≤ R ≤ 10.

1 ≤ C ≤ 10.

0 ≤ K ≤ 10.

1 ≤ R ≤ 3000.

1 ≤ C ≤ 3000.

0 ≤ K ≤ 3000.

### Sample

Sample Input
```2
3 3 1
2 1
4 11 12
0 1
0 3
0 4
0 10
1 0
1 9
2 0
2 4
2 9
2 10
3 4
3 10```
Sample Output
```Case #1: 10
Case #2: 51```

The grid of sample case #1 is:

``` 0 0 0 0 0 0 0 1 0 ```

Here, 0 represents a cell with no monster, and 1 represents a cell with a monster. It has 10 safe squares: 8 1x1 and 2 2x2.

The grid of sample case #2 is:

``` 0 1 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 ```

Note that sample case #2 will only appear in the Large dataset. It has 51 safe squares: 32 1x1, 13 2x2, 5 3x3, and 1 4x4.

## C. Evaluation

### Problem

Given an unordered list of assignment statements, write a program to determine whether the assignment statements can be put in some order in which all variables can be evaluated.

For our problem, an assignment statement will consist of an assignment variable, an assignment operator, and an expression, in that order. Statements will be evaluated one at a time, in the order you choose for them. A variable can be evaluated if and only if it has been the assignment variable of a previous assignment statement.

To simplify the problem, all the expressions are single function calls. Functions can take an arbitrary number of arguments, including zero; a function with zero arguments is always valid, and a function with variable arguments is valid as long as all of the variables are evaluatable.

For example, for the following list of assignment statements:

```a=f(b,c)
b=g()
c=h()```

this is one order that makes every statement valid:

```b=g()
c=h()
a=f(b,c)```

This is because: (1) `b` and `c` can be evaluated because the expressions `g()` and `h()` don't depend on any variables; and (2)`a` can also be evaluated because expression `a` depends on `b` and `c`, which are evaluatable.

However, the order

```b=g()
a=f(b,c)
c=h()```

would not be valid, because `f(b, c)` has variable c as an argument, but variable c has not been an assignment variable yet.

Another example is: `a=f(a)`. This list of statements can't be evaluated because the expression `f(a)` depends on the variable `a` itself, which makes it impossible to evaluate the statement.

### 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 an integer N: the number of assignment statements. Then, N lines follow. Each contains one assignment statement.

Each assignment statement consists of three parts: the assignment variable, the assignment operator, and the expression, with no spaces in between. The assignment operator is always `=`. All expressions consist of a function name, then `(`, then zero or more comma-separated variable names, then `)`. All variables and function names consist of one or more lowercase English alphabet letters. No variable has the same name as a function. No variable will appear more than once as the assignment variable. However, variables may appear more than once in various functions (even within the same function), and functions may appear more than once.

### 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 `GOOD` if all variables are evaluatable or `BAD` otherwise.

### Limits

1 ≤ T ≤ 20.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
All functions take between 0 and 10 arguments, inclusive. All variable names consist of between 1 and 20 lowercase English alphabet letters.

1 ≤ N ≤ 100.

1 ≤ N ≤ 1000.

### Sample

Sample Input
```4
3
a=f(b,c)
b=g()
c=h()
2
a=f(b)
b=f(a)
2
aaa=foo(x,y)
bbb=bar(aaa,bbb)
2
x=f()
y=g(x,x)```
Sample Output
```Case #1: GOOD
Case #4: GOOD```

## D. Soldiers

### Soldiers

General Alice and General Bob are playing a war game. There are N soldiers in the game. Each soldier has two stats: attack and defense.

Before the game starts, General Alice and General Bob will take turns selecting soldiers, with General Alice going first. In each turn, a player can select one soldier, as long as that soldier either has an attack stat greater than each of the attack stats of all soldiers selected so far, or has a defense stat greater than each of the defense stats of all soldiers selected so far. To be precise: let Ai and Di be the attack and defense values for the i-th soldiers, for i from 1 to N, and let S be the set of soldiers that have been selected so far. Then a player can select soldier x if and only if at least one of the following is true:

• Ax > As for all s in S
• Dx > Ds for all s in S
If no selection can be made, then the selection process ends and the players start playing the game.

General Alice wants to select more soldiers than General Bob, and General Bob wants to avoid that. If both players play optimally to accomplish their goals, can General Alice succeed?

### Input

The first line of each case contains a positive integer N, the number of soldiers. N more lines follow; the i-th of these line contains two integers Ai and Di, indicating the attack and defense stats of the i-th soldier.

### 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 `YES` or `NO`, indicating whether General Alice can guarantee that she selects more soldiers than General Bob, even if General Bob plays optimally to prevent this.

### Limits

1 ≤ T ≤ 10;
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ Ak, Dk ≤ 10000.

1 ≤ N ≤ 200.

1 ≤ N ≤ 4000.

### Sample

Sample Input
```3
3
10 2
1 10
10 3
3
10 1
10 10
1 10
3
10 2
1 10
4 9
```
Sample Output
```Case #1: NO
Case #2: YES
Case #3: YES
```

## Analysis — A. Monster Path

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

## Analysis — B. Safe Squares

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

## Analysis — C. Evaluation

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

## Analysis — D. Soldiers

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

## Statistics — A. Monster Path

### Test set 1: 752 correct solutions (47.0% solve rate)

First
nfssdq 15:52
akulsareen 17:04
jonathanirvings 19:02
551100kk 22:11
mindhunter 22:23

### Test set 2: 655 correct solutions (40.9% solve rate)

First
nfssdq 15:52
akulsareen 17:04
jonathanirvings 19:02
551100kk 22:11
mindhunter 22:23

## Statistics — B. Safe Squares

First
Starry 11:42
rezwan4029 14:26
pandusonu 15:51
lvxuhong 16:17
ckcz123 17:07

### Test set 2: 621 correct solutions (38.8% solve rate)

First
mynkgarg 18:18
nik1234 19:56
prakharsingh95 20:59
hehaodele 21:05
nfssdq 23:17

First
garzon 28:34
sh3r 32:00
idea16 32:09
swordfeng 34:26

First
garzon 28:34
sh3r 32:00
idea16 32:09
swordfeng 34:26

## Statistics — D. Soldiers

First
Bir 44:18
teoy 62:42
tony810430 63:57
Nicoding 76:38
hehaodele 80:57

### Test set 2: 24 correct solutions (1.5% solve rate)

First
tony810430 63:57
Nicoding 76:38
nfssdq 85:14
jonathanirvings 86:24
Asdfdy 98:11