Google Kick Start Archive — Round A 2015 problems

Problem

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string:

• switch: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011".
• reverse: The string is reversed. For example, "100" becomes "001".

Consider this infinite sequence of 0/1 strings:

S₀ = ""

S₁ = "0"

S₂ = "001"

S₃ = "0010011"

S₄ = "001001100011011"

...

S_N = S_N-1 + "0" + switch(reverse(S_N-1)).

You need to figure out the Kth character of S_googol, where googol = 10¹⁰⁰.

Input

The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.

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 Kth character of S_googol.

Limits

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

Small dataset (Test Set 1 - Visible)

1 ≤ K ≤ 10⁵.

Large dataset (Test Set 2 - Hidden)

1 ≤ K ≤ 10¹⁸.

Sample

4
1
2
3
10

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0

Problem

Googlers are very interested in cubes, but they are bored with normal three-dimensional cubes and also want to think about other kinds of cubes! A "D-dimensional cube" has D dimensions, all of equal length. (D may be any positive integer; for example, a 1-dimensional cube is a line segment, and a 2-dimensional cube is a square, and a 4-dimensional cube is a hypercube.) A "D-dimensional cuboid" has D dimensions, but they might not all have the same lengths.

Suppose we have an N-dimensional cuboid. The N dimensions are numbered in order (0, 1, 2, ..., N - 1), and each dimension has a certain length. We want to solve many subproblems of this type:

1. Take all consecutive dimensions between the L_i-th dimension and R_i-th dimension, inclusive.

2. Use those dimensions to form a D-dimensional cuboid, where D = R_i - L_i + 1. (For example, if L_i = 3 and R_i = 6, we would form a 4-dimensional cuboid using the 3rd, 4th, 5th, and 6th dimensions of our N-dimensional cuboid.)

3. Reshape it into a D-dimensional cube that has exactly the same volume as that D-dimensional cuboid, and find the edge length of that cube.

Each test case will have M subproblems like this, all of which use the same original N-dimensional cuboid.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with two integers N and M; N is the number of dimensions and M is the number of queries. Then there is one line with N positive integers a_i, which are the lengths of the dimensions, in order. Then, M lines follow. In the ith line, there are two integers L_i and R_i, which give the range of dimensions to use for the ith subproblem.

Output

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). After that, output M lines, where the ith line has the edge length for the ith subproblem. An edge length will be considered correct if it is within an absolute 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

Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ a_i ≤ 10⁹.
0 ≤ L_i ≤ R_i < N.

Small dataset (Test Set 1 - Visible)

1 ≤ N ≤ 10.
1 ≤ M ≤ 10.

Large dataset (Test Set 2 - Hidden)

1 ≤ N ≤ 1000.
1 ≤ M ≤ 100.

Sample

2
2 2
1 4
0 0
0 1
3 2
1 2 3
0 1
1 2

Case #1:
1.000000000
2.000000000
Case #2:
1.414213562
2.449489743

Problem

Company G has a main campus with N offices (numbered from 0 to N - 1) and M bidirectional roads (numbered from 0 to M - 1). The ith road connects a pair of offices (U_i, V_i), and it takes C_i minutes to travel on it (in either direction).

A path between two offices X and Y is a series of one or more roads that starts at X and ends at Y. The time taken to travel a path is the sum of the times needed to travel each of the roads that make up the path. (It's guaranteed that there is at least one path connecting any two offices.)

Company G specializes in efficient transport solutions, but the CEO has just realized that, embarrassingly enough, its own road network may be suboptimal! She wants to know which roads in the campus are inefficient. A road is inefficient if and only if it is not included in any shortest paths between any offices.

Given the graph of offices and roads, can you help the CEO find all of the inefficient roads?

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each case begins with one line with two integers N and M, indicating the number of offices and roads. This is followed by M lines containing three integers each: U_i, V_i and C_i, indicating the ith road is between office U_i and office V_i, and it takes C_i minutes to travel on it.

Output

For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output the road numbers of all of the inefficient roads, in increasing order, each on its own line. (Note that road 0 refers to the first road listed in a test case, road 1 refers to the second road, etc.)

Limits

Time limit: 30 seconds per test set.
Memory limit: 1GB.
0 < C_i ≤ 1000000.

Small dataset (Test Set 1 - Visible)

1 ≤ T ≤ 10.
1 ≤ N = M ≤ 100.

Large dataset (Test Set 2 - Hidden)

1 ≤ T ≤ 3.
1 ≤ N ≤ 100.
1 ≤ M ≤ 10000.

Sample

2
3 3
0 1 10
1 2 3
2 0 3
3 3
0 1 10
1 2 3
2 1 3

Case #1:
0
Case #2:

Problem

Alex is a huge fan of the Snake game.

Note: This Google Doodle does not exactly match the rules of the Snake game we will describe below. It is only intended to give you a general idea of what the game looks like.

Alex just learned how to program and wants to develop his own version of Snake, with the following rules:

• The game board has R rows and C columns. The top left cell of the board has coordinates (1, 1), and the bottom right cell has coordinates (R, C).
• At the start of the game, in every cell with coordinates (r, c) such that r + c is odd, there is one piece of food. No other cells have food.
• The snake's body is always an ordered, connected sequence of one or more cells on the board. The first cell of the sequence is called the "head" of the snake. The second cell (if any) shares an edge (not just a corner) with the first cell, and so on. The last cell in the sequence is called the "tail" of the snake.
• The snake's head is always facing in one of four directions: left, up, right, or down.
• At the start of the game, the snake is at cell (1, 1) and has a length of one (that is, the snake consists of only a head), and the head faces right.
• At each integer time (1 second, 2 seconds, etc.), the head of the snake will move into the adjacent cell that its head is facing toward. The board is cyclic, i.e., trying to move off an edge will cause the head to appear on the opposite edge of the board. For example, if the snake is at (1, C) and its head is facing right, the head will next move to (1, 1). If the snake is at (1, C) and its head is facing up, the head will next move to (R, C).
• When the snake's head moves into a cell with no food, the snake does not grow. The snake's second cell (if any) moves to the place where the snake's head was, the snake's third cell (if any) moves to the place where the second cell was, and so on.
• When the snake's head moves into a cell with a piece of food, it eats the food (meaning that cell no longer has food), and grows its body. A new head is created in the cell where the food was. The cell that was the snake's head becomes the snake's second cell, the cell that was the snake's second cell (if any) becomes the snake's third cell, and so on.
• If, after a move is complete, the snake's head is in the same place as one of another of its cells, the snake dies and the game ends immediately. (Note that if the snake's head moves toward a cell where its tail was, the game will not end, because the tail will move out of the way before the move is complete.)
• In the game, the player can let the snake perform some turn actions. Each action A_i will happen between the T_ith and T_i+1 th seconds. There are two possible actions: "L" and "R". An "L" action will turn the head 90 degrees to the left, so, for example, if the snake had been facing down before, it would face right after. An "R" action will turn the head 90 degrees to the right, so, for example, if the snake had been facing down before, it would face left after.
• The game has a time limit: it will end after the move on the 10⁹th second is complete (if the game has even gone on that long!)

To test the game, Alex has written a series of TURN actions. Your task is to simulate that series of actions, and tell Alex the final length of the snake when the game is over. Remember that the game can end either because the snake's head and another cell of its body are in the same place after a move is complete, or because time runs out. In the former case, you should count both the head and the overlapping cell of its body as two separate cells, for the purpose of determining length.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test cases starts with three integers S, R, and C, where S gives the number of turn actions and R and C represent the number of rows and columns of the board. S lines follow; the ith of these lines has an integer X_i, then a character A_i that is either L or R. Each of these lines corresponds to performing an action between X_ith and X_i+1 th seconds. It's guaranteed that the actions are given in time order and there will never be more than one action between the same two seconds. However, you should note that the game may end before the snake gets to execute all of these actions.

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 length of the snake when the game is over.

Limits

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

Small dataset (Test Set 1 - Visible)

Time limit: 30 seconds.
1 ≤ R, C ≤ 100;
1 ≤ S ≤ 100;
1 ≤ X_i ≤ 2000.

Large dataset (Test Set 2 - Visible)

Time limit: 60 seconds.
1 ≤ R, C ≤ 100000;
1 ≤ S ≤ 100000;
1 ≤ X_i ≤ 1000000.

Sample

2
3 3 3
1 R
2 L
3 R
5 3 3
2 R
4 R
6 R
7 R
8 R

Case #1: 3
Case #2: 5