Google Kick Start Archive — Round D 2015 problems

Problem

We have a grid with R rows and C columns in which every entry is either 0 or 1. We are going to perform N operations on the grid, each of which is one of the following:

• Operation M: Change a number in one cell of the grid to 0 or 1
• Operation Q: Determine the number of different connected regions of 1s. A connected region of 1s is a subset of cells that are all 1, in which any cell in the region can be reached from any other cell in the region by traveling between cells along edges (not corners).

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line with two integers, R and C, which represent the number of rows and columns in the grid. Then, there are R lines of C characters each, in which every character is either 0 or 1. These lines represent the initial state of the grid.

Output

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then, for every operation Q in the test case, in order, output one line containing the number of connected regions of 1s.

Limits

Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 10.
1 ≤ R, C ≤ 100.
0 ≤ x < R.
0 ≤ y < C.
0 ≤ z ≤ 1.

Small dataset (Test Set 1 - Visible)

1 ≤ N ≤ 10.

Large dataset (Test Set 2 - Hidden)

1 ≤ N ≤ 1000.

Sample

1
4 4
0101
0010
0100
1111
7
Q
M 0 2 1
Q
M 2 2 0
Q
M 2 1 0
Q

Case #1:
4
2
2
2

Problem

The G tech company has deployed many balloons. Sometimes, they need to be collected for maintenance at the company's tower, which is located at horizontal position 0. Each balloon is currently at horizontal position P_i and height H_i.

G engineers can move a balloon up and down by sending radio signals to tell it to drop ballast or let out air. But they can't move the balloon horizontally; they have to rely on existing winds to do that.

There are M different heights where the balloons could be. The winds at different heights may blow in different directions and at different velocities. Specifically, at height j, the wind has velocity V_j, with positive velocities meaning that the wind blows left to right, and negative velocities meaning that the wind blows right to left. A balloon at position P at a height with wind velocity V will be at position P+V after one time unit, P+2V after two time units, etc. If a balloon touches the tower, it is immediately collected.

It costs | H_original - H_new | points of energy to move one balloon between two different heights. (This transfer takes no time.) You have Q points of energy to spend, although you do not need to spend all of it. What is the least amount of time it will take to collect all the balloons, if you spend energy optimally?

Input

The first line of the input gives the number of test cases, T. T test cases follows. The first line of each case has three integers N, M, and Q, representing the number of balloons, the number of height levels, and the amount of energy available.
The second line has M integers; the jth value on this line (counting starting from 0) is the wind velocity at height j.
Then, N more lines follow. The ith of these lines consists of two integers, P_i and H_i, representing the position and height of the ith balloon.

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 minimum number of time units needed to collect all of the balloons, returns IMPOSSIBLE if it's impossible to collect all the balloons using the energy given.

Limits

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

Small dataset (Test Set 1 - Visible)

1 ≤ T ≤ 100.
1 ≤ N ≤ 10.
1 ≤ M ≤ 10.
-10 ≤ V_j ≤ 10.
1 ≤ Q ≤ 10.
0 ≤ H_i <M.
-10 ≤ P_i ≤ 10.

Large dataset (Test Set 2 - Hidden)

1 ≤ T ≤ 25.
1 ≤ N ≤ 100.
1 ≤ M ≤ 1000.
-100 ≤ V_j ≤ 100.
1 ≤ Q ≤ 10000
0 ≤ H_i <M.
-10000 ≤ P_i ≤ 10000.

Sample

2
2 4 1
2 1 -2 -1
3 3
-2 1
1 3 1
1 -1 -2
-2 2

Case #1: 2
Case #2: IMPOSSIBLE

Here is an example:

In the sample case, there are two balloons in the sky, and you have 1 energy point to use. The best solution is to immediately spend 1 energy point to move the balloon at position 3, height 3 down to height 2. Once you've done that, it will take 2 time units for both balloons to reach the tower.

Problem

An IP (Internet Protocol) address is a number that is assigned to each device on the Internet. At the time being, most devices use version four of this protocol (IPv4). An IPv4 address is a 32-bit string. IPv4 addresses are normally represented in dot-decimal notation, which consists of four decimal numbers called octets, each ranging from 0 to 255 (inclusive), separated by dots, e.g., 172.16.254.1. Each octet represents a group of 8 bits (one byte) of the address. The first 8 bits of the string (when interpreted as an unsigned integer, with the most significant bit first) form the first octet, the next 8 bits form the second octet, and so on.

An IP subnet addresses is used to represent a group of devices that belong to the same network. IP subnet addresses are expressed in the format of an IP address, followed by a slash and then a prefix length ranging from 0 to 32. A subnet address stands for all IP addresses that have the same first P bits of the given address, where P is the prefix length. For example 10.8.0.0/9 represents 2²³ addresses that all have 000010100 (the first nine bits of 10.8.0.0) as their first 9 bits, that is, 10.0.0.0 through 10.127.255.255. Note that 10.8.0.0/9 and, for example, 10.0.0.0/9 (or any other address within the subnet) would be equivalent ways to refer to the same subnet, because those addresses start with the same nine bits.

A subnet is normalized if the bits of the address other than the prefix are all zeroes. For example, 10.8.1.0/24 and 10.8.1.2/24 represent the same subnet, but 10.8.1.0/24 is normalized. The normalization of 255.255.255.255/13 is 255.248.0.0/13.

You will be given a list of subnet addresses, and you must output the shortest ordered list of subnets such that all the addresses are normalized and an address belongs to some subnet in the input if and only if it belongs to some subnet in the output.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each begins with one line with an integer N, the number of subnets, and is followed by N more lines, each of which has a subnet addresses. Each subnet address is of the form A.B.C.D/P, where A, B, C, and D are integers from 0 to 255, inclusive, and P is an integer from 0 to 32, inclusive. No integer (apart from 0) has leading zeroes.

Output

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output a list of subnet addresses, one per line, meeting the conditions described above. These addresses must be normalized and must be ordered. An address X comes before another address Y if X's first integer is smaller than Y's first integer, or if X and Y have the same first integer but X's second integer is smaller than Y's second integer, and so on.

Note that the requirements of the problem guarantee that there is a single unique answer for each test case.

Limits

Small dataset (Test Set 1 - Visible)

Time limit: 30 seconds.
1 ≤ N ≤ 10.

Large dataset (Test Set 2 - Hidden)

Time limit: 60 seconds.
1 ≤ N ≤ 10000.

Sample

3
2
10.1.2.3/8
10.2.3.4/17
2
10.2.3.4/9
10.128.2.3/9
10
224.147.224.186/18
58.45.85.53/14
52.56.134.139/26
52.227.82.227/22
83.250.251.44/13
83.250.12.64/16
58.40.52.11/14
52.22.138.56/23
238.223.58.151/27
58.32.52.11/13

Case #1:
10.0.0.0/8
Case #2:
10.0.0.0/8
Case #3:
52.22.138.0/23
52.56.134.128/26
52.227.80.0/22
58.32.0.0/12
83.248.0.0/13
224.147.192.0/18
238.223.58.128/27

Problem

Alice just bought a virtual pet rabbit. The rabbit hops around on a screen and can be "fed" by pressing a button. Alice is fond of the rabbit, but she is also busy, and doesn't want to spend too much time taking care of it. However, if the rabbit goes without "food" for too long, it "dies" and Alice loses the game.

Every day, Alice gets up at time G, goes to work at time W, returns home at time H, and goes to bed at time B. Alice cannot feed the rabbit while she is at work or asleep -- that is, in the intervals [W, H) and [B, G). Note that times W and B themselves are not valid feeding times, whereas times H and G are. In any other second, Alice can either push a button to instantly feed the rabbit, or not push the button. Between every two seconds, the rabbit determines the number of consecutive seconds in which it has not been fed, and "dies" if that duration is equal to X.

It is currently 00:00:00 on Day 0, and the rabbit has just been delivered to Alice's house by the mail service. (The mail carrier pushes the button at 00:00:00, even if Alice is asleep, and then leaves.) Alice wants to make sure the rabbit is still "alive" at 00:00:00 on day D. What is the minimal number of times that she needs to feed the rabbit, if she can keep the rabbit "alive" at all?

Input

The first line of the input gives the number of test cases, T. T test cases follow; each consists of 6 lines. The first 5 lines represent the times G, W, H, B, and X in "hh:mm:ss" format. The last line consists of one integer 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 minimal number of times Alice needs to feed the rabbit. If it's impossible for the rabbit to be alive at 00:00:00 on day D, output -1.

Limits

Time limit: 30 seconds per test set.
Memory limit: 1 GB.
1 ≤ T ≤ 100.
It's guaranteed that Alice always goes to bed before midnight and gets up at or after midnight. G, W, H, and B are in strictly increasing order within the same day.
00:00:00 ≤ G < W < H < B ≤ 23:59:59.
00:00:00 < X ≤ 23:59:59.

Small dataset (Test Set 1 - Visible)

1 ≤ D ≤ 1000.

Large dataset (Test Set 2 - Hidden)

1 ≤ D ≤ 10¹⁴.

Sample

3
08:00:00
09:00:00
18:00:00
22:00:00
12:00:00
100
08:00:00
09:00:00
18:00:00
22:00:00
01:00:00
1
00:00:00
12:00:00
12:00:01
23:59:59
00:00:02
2

Case #1: 200
Case #2: -1
Case #3: 86401

In sample case #1, Alice could feed the rabbit at 08:00:00 and 20:00:00 every day.

In sample case #2, the poor rabbit will be "dead" before Alice even wakes up on Day 0.