Google Kick Start Archive — Round D 2014 problems

Problem

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 S² 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.

Small dataset (Test Set 1 - Visible)

1 ≤ S ≤ 10

Large dataset (Test Set 2 - Hidden)

1 ≤ S ≤ 10³.

Sample

2
2
3 4
1 2 


3
1 2 9 
5 3 8 
4 6 7 

Case #1: 1 2
Case #2: 6 4

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 A_i and B_i, 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 A₁ B₁ A₂ B₂ A₃ B₃ ... A_N B_N. That is, the first GBus serves the cities numbered from A₁ to B₁ (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 C_i 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 C_i.

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 ≤ A_i ≤ 500, for all i.
1 ≤ B_i ≤ 500, for all i.
1 ≤ C_i ≤ 500, for all i.
1 ≤ P ≤ 50.

Large dataset (Test Set 2 - Hidden)

1 ≤ N ≤ 500.
1 ≤ A_i ≤ 5000, for all i.
1 ≤ B_i ≤ 5000, for all i.
1 ≤ C_i ≤ 5000, for all i.
1 ≤ P ≤ 500.

Sample

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

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.

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.

Small dataset (Test Set 1 - Visible)

1 ≤ N ≤ 100.

Large dataset (Test Set 2 - Hidden)

1 ≤ N ≤ 10⁴.

Sample

2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

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

Large dataset (Test Set 2 - Hidden)

1 ≤ N ≤ 64.

Sample

2
2
A1-K
A8-Q

3
B2-K
A1-P
H8-Q

Case #1: 1
Case #2: 3