# Google Kick Start Archive — Round B 2015 problems

## A. Travel

### Problem

There are N cities in Chelsea's state (numbered starting from 1, which is Chelsea's city), and M bidirectional roads directly connect them. (A pair of cities may even be directly connected by more than one road.) Because of changes in traffic patterns, it may take different amounts of time to use a road at different times of day, depending on when the journey starts. (However, the direction traveled on the road does not matter -- traffic is always equally bad in both directions!) All trips on a road start (and end) exactly on the hour, and a trip on one road can be started instantaneously after finishing a trip on another road.

Chelsea loves to travel and is deciding where to go for her winter holiday trip. She wonders how quickly she can get from her city to various other destination cities, depending on what time she leaves her city. (Her route to her destination may include other intermediate cities on the way.) Can you answer all of her questions?

### 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 three integers: the number N of cities, the number M of roads, and the number K of Chelsea's questions.

2M lines -- M pairs of two lines -- follow. In each pair, the first line contains two different integers x and y that describe one bidirectional road between the x-th city and the y-th city. The second line contains 24 integers Cost[t] (0 ≤ t ≤ 23) that indicate the time cost, in hours, to use the road when departing at t o'clock on that road. It is guaranteed that Cost[t] ≤ Cost[t+1]+1 (0 ≤ t ≤ 22) and Cost[23] ≤ Cost[0]+1.

Then, an additional K lines follow. Each contains two integers D and S that comprise a question: what is the fewest number of hours it will take to get from city 1 to city D, if Chelsea departs city 1 at S o'clock?

### Output

For each test case, output one line containing "Case #x: ", where x is the case number (starting from 1), followed by K distinct space-separated integers that are the answers to the questions, in order. If Chelsea cannot reach the destination city for a question, no matter which roads she takes, then output -1 for that question.

### Limits

Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ x, y ≤ N.
1 ≤ all Cost values ≤ 50.
1 ≤ DN.
0 ≤ S ≤ 23.

1 ≤ T ≤ 100.
2 ≤ N ≤ 20.
1 ≤ M ≤ 100.
1 ≤ K ≤ 100.

1 ≤ T ≤ 5.
2 ≤ N ≤ 500.
1 ≤ M ≤ 2000.
1 ≤ K ≤ 5000.

### Sample

Sample Input
```3
3 3 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
2 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1
3 3
3 1 2
1 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 2
3 4
3 3 3
1 2
7 23 23 25 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
1 3
10 11 15 26 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11
2 3
7 29 28 27 26 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8
2 14
3 3
3 21```
Sample Output
```Case #1: 1 2
Case #2: 1 -1
Case #3: 17 26 13```

## B. gWheels

### Problem

A typical mountain bike has two groups of gears: one group connected to the pedals, and one group connected to the rear tire. A gear group consists of many gears, which usually have different numbers of teeth. A chain connects one of the gears in the pedal gear group to one of the gears in the tire gear group, and this determines the ratio between the cyclist's pedaling speed and the tire speed. For example, if the chain connects a gear with 5 teeth on the pedals to a gear with 10 teeth on the tires, the ratio will be 1/2, since the cyclist needs to make the pedal gear rotate twice to make the tire rotate once. The cyclist can change the chain to connect any one gear from the pedal group to any one gear from the tire group.

You have just bought a special new mountain bike with three groups of gears: one connected to the pedals, one connected to the tire, and one extra group in between. This mountain bike has two chains; the first chain must always connect one gear from the pedal gear group to one gear on the extra gear group, and the second chain must always connect one gear from the extra gear group to one gear on the tire gear group. Moreover, the two chains cannot both use the same gear from the extra gear group.

Given the numbers of teeth on the available gears on the pedals, extra, and tire groups, is it possible to make the ratio (between pedaling speed and tire speed) be exactly P/Q? For a given set of gears, you may need to answer multiple such questions.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with 3 integers Np, Ne, and Nt, representing the numbers of gears on the pedals, extra, and tire groups. Then, three more lines follow. These contain Np, Ne, and Nt integers, respectively, representing the numbers of teeth on the different gears on the pedals, extra, and tire gear groups, respectively. (It is guaranteed that the numbers of teeth on the gears within a group are all distinct.) The next line after that consists of one integer, M, the number of questions. Finally, there are M lines, each with 2 integers, P and Q, representing the target ratio. (It is not guaranteed that this ratio is a reduced fraction.)

### Output

For each test case, first output one line containing "Case #x:", where x is the test case number (starting from 1). Then output one line for each question within the test case, in the order that the questions were presented: `Yes` if it's possible to make the ratio P/Q, and `No` if it's impossible.

### Limits

Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ the number of teeth on each gear ≤ 10000.
1 ≤ all values of P, Q ≤ 109.
1 ≤ M ≤ 10.

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

Time limit: 30 seconds.
1 ≤ Np, Nt ≤ 10.
2 ≤ Ne ≤ 10.

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

Time limit: 180 seconds.
1 ≤ Np, Nt ≤ 2000.
2 ≤ Ne ≤ 2000.

### Sample

Sample Input
```1
1 2 3
5
4 6
3 5 7
2
1 1
5 2```
Sample Output
```Case #1:
No
Yes```
For the first question in the test case, it's impossible to get the ratio 1/1 since this would require both chains to be on the same gear in the extra gear group, which is not allowed.

For the second question in the test case, you can make the first chain connect the 5-tooth gear on the pedal gear group to the 4-tooth gear on the extra gear group, and make the second chain connect the 6-tooth gear on the extra gear group to the 3-tooth gear on the tire gear group. With this setup, the ratio is 5/2.

## C. gNumbers

### gNumbers

Googlers are crazy about numbers and games, especially number games! Two Googlers, Laurence and Seymour, have invented a new two-player game based on "gNumbers". A number is a gNumber if and only if the sum of the number's digits has no positive divisors other than 1 and itself. (In particular, note that 1 is a gNumber.)

The game works as follows: First, someone who is not playing the game chooses a starting number N. Then, the two players take turns. On a player's turn, the player checks whether the current number C is a gNumber. If it is, the player loses the game immediately. Otherwise, the player chooses a prime factor P of C, and keeps dividing C by P until P is no longer a factor of C. (For example, if the current number were 72, the player could either choose 2 and repeatedly divide by 2 until reaching 9, or choose 3 and repeatedly divide by 3 until reaching 8.) Then the result of the division becomes the new current number, and the other player's turn begins.

Laurence always gets to go first, and he hates to lose. Given a number N, he wants you to tell him which player is certain to win, assuming that both players play optimally.

### Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of a starting number N.

### 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 winner's name: either `Laurence` or `Seymour`.

### Limits

Memory limit: 1 GB.
1 ≤ T ≤ 100.

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

Time limit: 30 seconds.
1 < N ≤ 1000.

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

Time limit: 60 seconds.
1 < N ≤ 1015.

### Sample

Sample Input
```9
2
3
4
6
8
9
30
36300
1000000000000000
```
Sample Output
```Case #1: Seymour
Case #2: Seymour
Case #3: Laurence
Case #4: Laurence
Case #5: Laurence
Case #6: Laurence
Case #7: Seymour
Case #8: Laurence
Case #9: Seymour
```
In Case #1, 2 is already a gNumber, since the sum of its digits is 2, which has no positive divisors other than 1 and itself. So Laurence immediately loses, which means Seymour wins. The same is true for Case #2.

In Case #3, 4 is not a gNumber, since the sum of its digits is 4, which has a positive divisor other than 1 and itself (namely, 2). 4 has one prime factor (2), so Laurence must choose this factor and repeatedly divide 4 by it, which leaves him with 1. Then, Seymour begins his turn with 1, which is a gNumber. So he loses and Laurence wins.

## D. Albocede DNA

The DNA of the Albocede alien species is made up of 4 types of nucleotides: `a`, `b`, `c`, and `d`. Different Albocedes may have different sequences of these nucleotides, but any Albocede's DNA sequence obeys all of the following rules:

• It contains at least one copy of each of `a`, `b`, `c`, and `d`.
• All `a`s come before all `b`s, which come before all `c`s, which come before all `d`s.
• There are exactly as many `'a'`s as `'c'`s.
• There are exactly as many `'b'`s as `'d'`s.

For example, `abcd` and `aabbbccddd` are valid Albocede DNA sequences. `acbd`, `abc`, and `abbccd` are not.

The Albocede-n is an evolved species of Albocede. The DNA sequence of an Albocede-n consists of one or more valid Albocede DNA sequences, concatenated together end-to-end. For example, `abcd` and `aaabcccdaabbbccdddabcd` are valid Albocede-n DNA sequences. (Observe that a valid Albocede-n DNA sequence is not necessarily also a valid Albocede DNA sequence.)

From one of your alien expeditions, you retrieved an interesting sequence of DNA made up of only `a`s, `b`s, `c`s, and `d`s. You are interested in how many of the different subsequences of that sequence would be valid Albocede-n DNA sequences. (Even if multiple different selections of nucleotides from the sequence produce the same valid subsequence, they still all count as distinct subsequences.) Since the result may be very large, please find it modulo 1000000007 (109 + 7).

### Input

The first line of the input gives the number of test cases, T. Each of the next T lines contains a string S that consists only of the characters `a`, `b`, `c`, and `d`.

### 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 output of the xth test case.

### Limits

Memory limit: 1 GB.
1 ≤ T ≤ 20.

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

Time limit: 30 seconds.
1 ≤ length of S ≤ 50.

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

Time limit: 120 seconds.
1 ≤ length of S ≤ 500.

### Sample

Sample Input
```5
abcd
aaaabcd
aaaabbccd
abcdabcdaabccd
b```
Sample Output
```Case #1: 1
Case #2: 4
Case #3: 28
Case #4: 71
Case #5: 0```

## Analysis — A. Travel

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

## Analysis — B. gWheels

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

## Analysis — C. gNumbers

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

## Analysis — D. Albocede DNA

The problem can be solved using Dynamic programming approach.
Test Data
info We recommend that you practice debugging solutions without looking at the test data.

## Statistics — A. Travel

### Test set 1: 503 correct solutions (42.3% solve rate)

First
kcm1700 12:45
tapasjain 18:42
SampsonLee 18:50
JackyWijaya 19:22
Abhinav.Gupta 21:40

### Test set 2: 365 correct solutions (30.7% solve rate)

First
kcm1700 12:45
tapasjain 18:42
SampsonLee 18:50
JackyWijaya 19:22
Abhinav.Gupta 21:40

First
SDS 21:49
zjulyx 22:13
snake122 22:15
pakhandi 23:10
kcm1700 25:26

First
kcm1700 25:26
KKOrange 26:33
manavs19 38:10
xieofxie 41:44
nejistar 45:52

## Statistics — C. gNumbers

### Test set 1: 259 correct solutions (21.8% solve rate)

First
himanshujaju 22:24
mkrjn99 28:52
anuj95 35:44
kcm1700 36:22

### Test set 2: 78 correct solutions (6.6% solve rate)

First
himanshujaju 22:24
kcm1700 36:22
SampsonLee 59:23
jonathanirvings 65:32

## Statistics — D. Albocede DNA

### Test set 1: 31 correct solutions (2.6% solve rate)

First
Curious violet beaver 59:28
kcm1700 60:48