# Google Kick Start Archive — Round D 2014 problems

## A. Cube IV

### Problem

Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room). There is a big number written in the room. A person can only move from one room to another if the number in the next room is larger than the number in his current room by 1. Now, Vincenzo assigns unique numbers to all the rooms (1, 2, 3, .... S2) and then places S2 people in the maze, 1 in each room where S is the side length of the maze. The person who can move maximum number of times will win. Figure out who will emerge as the winner and the number of rooms he will be able to move.

### Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of S which is the side length of the square maze. Then S2 numbers follow like a maze to give the numbers that have been assigned to the rooms.

```1 2 9
5 3 8
4 6 7
```

### Output

For each test case, output one line containing "Case #x: r d", where x is the test case number (starting from 1), r is the room number of the person who will win and d is the number of rooms he could move. In case there are multiple such people, the person who is in the smallest room will win.

### Limits

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

1 ≤ S ≤ 10

1 ≤ S ≤ 103.

### Sample

Sample Input
```2
2
3 4
1 2

3
1 2 9
5 3 8
4 6 7 ```
Sample Output
```Case #1: 1 2
Case #2: 6 4```

## B. GBus count

### Problem

There exist some cities that are built along a straight road. The cities are numbered 1, 2, 3... from left to right.

There are N GBuses that operate along this road. For each GBus, we know the range of cities that it serves: the i-th gBus serves the cities with numbers between Ai and Bi, inclusive.

We are interested in a particular subset of P cities. For each of those cities, we need to find out how many GBuses serve that particular city.

### Input

The first line of the input gives the number of test cases, T. Then, T test cases follow; each case is separated from the next by one blank line. (Notice that this is unusual for Kickstart data sets.)

In each test case:

• The first line contains one integer N: the number of GBuses.
• The second line contains 2N integers representing the ranges of cities that the buses serve, in the form A1 B1 A2 B2 A3 B3 ... AN BN. That is, the first GBus serves the cities numbered from A1 to B1 (inclusive), and so on.
• The third line contains one integer P: the number of cities we are interested in, as described above. (Note that this is not necessarily the same as the total number of cities in the problem, which is not given.)
• Finally, there are P more lines; the i-th of these contains the number Ci of a city we are interested in.

### Output

For each test case, output one line containing `Case #x: y`, where `x` is the number of the test case (starting from 1), and `y` is a list of P integers, in which the i-th integer is the number of GBuses that serve city Ci.

### Limits

Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 10.

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

1 ≤ N ≤ 50
1 ≤ Ai ≤ 500, for all i.
1 ≤ Bi ≤ 500, for all i.
1 ≤ Ci ≤ 500, for all i.
1 ≤ P ≤ 50.

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

1 ≤ N ≤ 500.
1 ≤ Ai ≤ 5000, for all i.
1 ≤ Bi ≤ 5000, for all i.
1 ≤ Ci ≤ 5000, for all i.
1 ≤ P ≤ 500.

### Sample

Sample Input
```2
4
15 25 30 35 45 50 10 20
2
15
25

10
10 15 5 12 40 55 1 10 25 35 45 50 20 28 27 35 15 40 4 5
3
5
10
27
```
Sample Output
```Case #1: 2 1
Case #2: 3 3 4
```

In Sample Case #1, there are four GBuses. The first serves cities 15 through 25, the second serves cities 30 through 35, the third serves cities 45 through 50, and the fourth serves cities 10 through 20. City 15 is served by the first and fourth buses, so the first number in our answer list is 2. City 25 is served by only the first bus, so the second number in our answer list is 1.

## C. Sort a scrambled itinerary

### Problem

Once upon a day, Mary bought a one-way ticket from somewhere to somewhere with some flight transfers.

For example: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.

Obviously, transfer flights at a city twice or more doesn't make any sense. So Mary will not do that.

Unfortunately, after she received the tickets, she messed up the tickets and she forgot the order of the ticket.

Help Mary rearrange the tickets to make the tickets in correct order.

### Input

The first line contains the number of test cases T, after which T cases follow.
For each case, it starts with an integer N. There are N flight tickets follow.
Each of the next 2 lines contains the source and destination of a flight ticket.

### Output

For each test case, output one line containing "Case #x: itinerary", where x is the test case number (starting from 1) and itinerary is sorted list of flight tickets which represents the actual itinerary. Each flight segment in the itinerary should be outputted as pair of source-destination airport codes.

### Limits

Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
For each case, the input tickets are messed up from an entire itinerary bought by Mary. In other words, it's ensured can be recovered to a valid itinerary.

1 ≤ N ≤ 100.

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

1 ≤ N ≤ 104.

(The segment for second case in sample can be seen as below) MIA-ORD, DFW-JFK, SFO-DFW, JFK-MIA

### Sample

Sample Input
```2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA
```
Sample Output
```Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD
```

## D. Itz Chess

### Problem

Given an arranged chess board with pieces, figure out the total number of different ways in which any piece can be killed in one move. Note: in this problem, the pieces can be killed despite of the color.

For example, if there are 3 pieces King is at B2, Pawn at A1 and Queen at H8 then the total number of pieces that an be killed is 3. H8-Q can kill B2-K, A1-P can kill B2-K, B2-K can kill A1-P

A position on the chess board is represented as A1, A2... A8,B1.. H8

Pieces are represented as

• (K) King can move in 8 direction by one place.
• (Q) Queen can move in 8 direction by any number of places, but can't overtake another piece.
• (R) Rook can only move vertically or horitonzally, but can't overtake another piece.
• (B) Bishop can only move diagonally, but can't overtake another piece.
• (N) Knights can move to a square that is two squares horizontally and one square vertically OR one squares horizontally and two square vertically.
• (P) Pawn can only kill by moving diagonally upwards (towards higher number i.e. A -> B, B->C and so on).

### Input

The first line of the input gives the number of test cases, T. T Test cases follow. Each test case consists of the number of pieces , N. N lines follow, each line mentions where a piece is present followed by - with the piece type

### 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 different ways in which any piece can be killed.

### Limits

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

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

1 ≤ N ≤ 10.
Pieces can include K, P

1 ≤ N ≤ 64.

### Sample

Sample Input
```2
2
A1-K
A8-Q

3
B2-K
A1-P
H8-Q
```
Sample Output
```Case #1: 1
Case #2: 3
```

## Analysis — A. Cube IV

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

## Analysis — B. GBus count

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

## Analysis — C. Sort a scrambled itinerary

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

## Analysis — D. Itz Chess

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

## Statistics — A. Cube IV

### Test set 1: 1708 correct solutions (77.8% solve rate)

First
culaucon 7:55
Balajiganapathi 8:26
dreamoon_love_AA 8:31
Harta 8:37
Arios 9:25

### Test set 2: 1492 correct solutions (68.0% solve rate)

First
culaucon 7:55
Balajiganapathi 8:26
dreamoon_love_AA 8:31
Harta 8:37
Arios 9:25

## Statistics — B. GBus count

### Test set 1: 2048 correct solutions (93.3% solve rate)

First
csprajeeth 10:35
JeffWeng 11:53
guanshun 12:01
Bright lime crow 12:31
anmolarora123 12:46

### Test set 2: 1865 correct solutions (85.0% solve rate)

First
csprajeeth 10:35
JeffWeng 11:53
guanshun 12:01
Bright lime crow 12:31
anmolarora123 12:46

## Statistics — C. Sort a scrambled itinerary

### Test set 1: 1623 correct solutions (73.9% solve rate)

First
saurabhskj 18:18
dreamoon_love_AA 19:37
nbhagat 19:51
Balajiganapathi 22:10

### Test set 2: 1483 correct solutions (67.6% solve rate)

First
saurabhskj 18:18
dreamoon_love_AA 19:37
nbhagat 19:51
Balajiganapathi 22:10

## Statistics — D. Itz Chess

### Test set 1: 654 correct solutions (29.8% solve rate)

First
Chaithanya 20:51
dreamoon_love_AA 36:59
Balajiganapathi 43:50
Kriiii 46:57
zuoyou 47:09

### Test set 2: 393 correct solutions (17.9% solve rate)

First
dreamoon_love_AA 36:59
Balajiganapathi 43:50
Kriiii 46:57
zuoyou 47:09
uws933 52:05