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:
0
becomes 1
and every 1
becomes 0
. For example, "100" becomes "011".
Consider this infinite sequence of 0/1 strings:
S_{0} = ""
S_{1} = "0"
S_{2} = "001"
S_{3} = "0010011"
S_{4} = "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^{100}.
The first line of the input gives the number of test cases, T. Each of the next T lines contains a number K.
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}.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ K ≤ 10^{5}.
1 ≤ K ≤ 10^{18}.
4 1 2 3 10
Case #1: 0 Case #2: 0 Case #3: 1 Case #4: 0
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.
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.
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.
Time limit: 30 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
1 ≤ a_{i} ≤ 10^{9}.
0 ≤ L_{i} ≤ R_{i} < N.
1 ≤ N ≤ 10.
1 ≤ M ≤ 10.
1 ≤ N ≤ 1000.
1 ≤ M ≤ 100.
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
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?
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.
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.)
Time limit: 30 seconds per test set.
Memory limit: 1GB.
0 < C_{i} ≤ 1000000.
1 ≤ T ≤ 10.
1 ≤ N = M ≤ 100.
1 ≤ T ≤ 3.
1 ≤ N ≤ 100.
1 ≤ M ≤ 10000.
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:
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:
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.
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_{i}th 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.
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.
Memory limit: 1GB.
1 ≤ T ≤ 10.
Time limit: 30 seconds.
1 ≤ R, C ≤ 100;
1 ≤ S ≤ 100;
1 ≤ X_{i} ≤ 2000.
Time limit: 60 seconds.
1 ≤ R, C ≤ 100000;
1 ≤ S ≤ 100000;
1 ≤ X_{i} ≤ 1000000.
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