TopCoder problem "Distance" used in ()



Problem Statement

    The execution of your program in this problem will take place in two stages. In the first stage, you will be given a large undirected graph, and will have 30 seconds to perform any processing you desire. In the second stage, you will be queried about pairs of points in the graph, and must determine the distance between them. In the second stage, you will only be allowed 2 seconds of processing time, for 10000 pairs of points.



Scoring will be based on how how much time you use in the second stage, combined with the accuracy the distances you return. The accuracy will be computed using the root mean squared error (RMSE) of your returned distances. In other words, for each distance, we will compute the error from the correct distance, and square it. We then take the average of these squared errors, and finally take the square root of this average. We will then add time to this error, where time is your stage 2 execution time, measured in seconds. Your final score will be 10*tests minus the sum of your individual scores, where tests is the number of test cases. If you score over 10 on any test case, or you fail any test case (exceed time, crash, or provide an invalid return), it will be treated as if you scored 10.



Each graph except the examples will have one million nodes. The nodes will be numbered from 0 to 999,999. A value D will then be chosen between 5 and 20, along with a real value a between 0 and 1. For each node, D edges will be created. When creating an edge from node i, it will go to node j (where j does not equal i) with probability proportional to ((di,j)-a-(di,j+1)-a), where di,j is the minimum of |i-j| and N-|i-j|. This may generate duplicate edges, so there may end up being fewer than N*D edges in the graph given to you. Finally, the nodes will be randomly permuted so that the numbering used to generate the graph is lost.



You should write a method process that takes a String[], representing the graph. Element i of the input is a space delimited list of nodes that i is connected to. For conciseness, if j appears on i's list, i will not neccesarily appear on j's list (though it may), though the edges are undirected. The method query will take two int[]s, and should return a double[] of the same length. Element i of the returned double[] should contain the distance between u[i] and v[i].
 

Definition

    
Class:Distance
Method:process
Parameters:String[]
Returns:int
Method signature:int process(String[] g)
 
Method:query
Parameters:int[], int[]
Returns:double[]
Method signature:double[] query(int[] u, int[] v)
(be sure your methods are public)
    
 

Notes

-There will be a path in the graph between all queried pairs of nodes.
-While some of the examples are smaller graphs with fewer queries, all of the test cases will be on one million nodes, with 10,000 queries.
-While the actual path lengths are clearly integers, you may find it useful to predict fractional values. For example, if you are not sure whether the path length between two nodes is 8 or 9, you might predict 8.5.
-The memory limit is 1024M and the thread limit is 32 (including the primary thread).
-java.util.Random is used for all random number generation.
-There are 20 non-example test cases.
 

Examples

0)
    
"11 !\"\"\"#\"#\"\"\""
Returns: 
"This test case has 10 nodes.  D = 5 and a = 0.6294993817708533.  There are 10 queries."
Download

Each of the first N lines represents a single node. Each line starts with an integer K, and is followed by K other integers representing K edges. For example if line 0 were "2 83 76", it would indicate that there were edges from node 0 to nodes 83 and 76. Following these N lines, are a number of lines containing two integers -- the queries. All test case files are formatted the same way.



Note that the file format is slightly different from the input format. The graph in the file for this test cases is represented by 
2 8 6
4 5 0 4 2
3 0 6 9
3 7 8 0
3 5 1 7
3 9 4 1
4 4 0 7 9
4 4 1 5 8
4 3 7 1 2
3 2 5 1
On the other hand, the String[] input is: 
{"8 6",
 "5 0 4 2",
 "0 6 9",
 "7 8 0",
 "5 1 7",
 "9 4 1",
 "4 0 7 9",
 "4 1 5 8",
 "3 7 1 2",
 "2 5 1"}
1)
    
"12 ##\"################\"###\"#\"#\"\"#\"###$##########\"#$###\"#####\"##\"#######\"\"#$#\"\"#######$\"\"#\"##\"##$###\"\"#$"
Returns: 
"This test case has 100 nodes.  D = 20 and a = 0.4809864913712196.  There are 100 queries."
Download
2)
    
"13 $#$$$##$$##$$$$#$#$#$##$$##$$$$#$$####$$#$$#$###$$$#$###$$#$##$$#$#$$$$$#$$##$#$$#$#$$$#$###\"$\"#$##$#$$#\"$#####$###$#$$$$\"#$$$$$$$#$#\"#$#$##$#$$####$#$#$$$###$$$#\"##$##$$######$##$$#$$$$#####$#\"$#$#$$#$$$$$#$#\"$$#$#$$##$#$$$$#$$#$$#$#$#$#####$#$#$#####\"\"#$$$$\"#$!$$$$$$$###$$$#$$$$#$###$\"$#$$$##$#$$$$$$$##$###$$$##$#$##$$$####$$$\"\"#$$$##$#$##$$$$#$$$$$$$$##$$$$###$#$$#$#$##$$$#$###$#$$##$#$#\"#$$$#$#$#$#$$#$$$$\"#$$##$$##\"#$\"##$\"\"#$$##$####$$$#$#$$$##$###$#$##$$#$$$$$#$$#$#$$$##$$$###$##$$#$$$$#$##$\"$##$$$###$###$$$$$$$#$$#$$$$#$$#\"$$##$$$#$$##$$####$$###%##$#####$#$$###$##$###$$$$$$$$$$$$##$##$#\"$$#$####$$$#$#$##$$$#$#$#$$$#$$##$#$$$\"#$#$#$#$#####$$#$$#$$#$$##$#$##$##\"##$##$##$#$$$#$$##$$$#$####$$$$#$$$#$###$$#$#$##$#$##$$#$##$$$##$$##$$$$$$###$#$#$$#$$###$##$$#$#\"###$$##$$#$$$\"##$$$##$$$$$$$$#$$$$$#$$###$#\"$$$###$$$$$$$$#$\"###$$$###$$$$$$\"##$#$##$$$$$$#$$##$$#$$$$$#$\"#$#$$$$###$#$#$$$$$$$$$$$$$\"$$$#$###$##$$#$####$#$##$$$$$$$$#$#$$#$$#$$$#$$#$\"$#$$#$$#$$##$#$#$##$$$##$$$$$#$#$##$$$$$###"
Returns: 
"This test case has 1000 nodes.  D = 16 and a = 0.05128392223198952.  There are 1000 queries."
Download
3)
    
"14 &%&%&&&&%%%&$&%&%&%&%%&&&&%&&%%&%%&%%$&%%&$%%&&&&&%%%%&&&$%%%&%&%&&&&%%%$%%%&%%%&&%$%$&&&%%'&&$&%%&&&%&&%&&%%$$%%&%%%%%%&%&%%%%&&$&&&%$&$$&%&&%%%&%%&&%&%$'&%$%%%$&&$$%&&&&&%&%&%&$&&%&%&&&%&&&&&&&&$$%%%$%&%&%%&&%%&%&&&%&%'&%%&$&&&&%%%\"%&%&#%%%%&&%%%%&%'$&%&%&&%'%&%%%&%%%&&$&%&%%%&%%#%%#&$&&%%&&&%&%%&%&%%%&&%%&&$&%&%&%&&'&%&$&%%$&#$$&%$%&&&$%&&%%$&%%&&&$%&&%%%%&$$%&%&&&%%&%%$%&&&&%%&%%$%%%&$&%%&&%%%&%%&%&%$&&&$#$&%&%&%%%&&%%%$%%&&%&%$&%&$'&%&&&%%&%&&%&&'%&&%&&&&%%%&&&%%#&%%&#%$&&&%%%%&%$%&&&&%'%&%&%%&%%%$%&&&&&%$%%&&%%&&&%&%&&%&&%%%&%%%%%%&%$&%%%%&$$%%%&%%&&&&$&%%'%$&&%$&&%%&&&&%&&$%&%&$&&&%&$&&&&&%&&&%#%%&&&&%%$%&%%%$%#%$%%%&&%%$%&%$&%&&&&%$&&%%&&'%&&&&%&%&&%%&%%$%&%%&&%%#&%&%&&&%%%'$$&%&%%%%&$%%%%&%&%&&$&%%&#%$&%&&#&$%&%%%&&&%&&%&&&&%&&&%%&&&&$&&%%&&&&%%&&&%&%&%&%%%%%&%&%%&&&&%%%$&&%&%%%&%$%&&%%&&%&&%%&%%%&#%&&'%%&&%&&#%&%%%%%&$%&&%$%%&$&%%&&%&%%%$&%%%%%%%&$&&&%&$'$$%%%%%&%&%$&%&&'%%&&&&&%&&%&%&&&#%&%%%&%&%%&&'%&$&&&&%$%$$&%&%$%$%\"$%&%&%&%&%%%%$%%&%%&%&%%%&$%&$&&%&%&$%&&&%%&&&&&&&%$&%%&&&&&&%&&%%#%%%&%%&%%'$&&&&$%%%\"&%%&#$%&'$%%&&%%&%%$%%%%%%&$&&&%&%%&%%%&&&%$&%&#&#%%%$&%&&%&&%&%$$%$&&%&&#&&%&&$&&&%&&&%&%%%&&&%%&&%&$&&#&&$%&%%%%%%%$%%$'$%%&%$&%%%%&&%$&&&&&$%&%'%$%&&&%&'%&&&&&%%&$&%&%&%%&&%&%&%%%%&%%&&%$&%%$%&#&&%&%%&%%&&%%%%%&&&&%%%$%&&&%&%%%%$%%%%$%%&%%&&%%%&&&%%%%$%&%$%$%&&&%%%%&%%%%&%%&$%$%%&&&%&&&$%&&%&&&%'$&&%%&%&&%&%&%&%$&$&&%&&%%&%&%$%$$%&&%%&&%&$%%%%%%%&&&%&&&%%%%%&%%&&$$%&&&&%&$%%&&#&&&%%&%&&&$%%%%%$%&%&%&$$#&&&%&%%&%$%%&%%%&$$$$\"%&&&&$%&%'&$%&$%%%%&%%&%%#&&&$&&&%%%%&&&%&$%&%%&%'%&$&&&&%&&&&%&&'%&%$%&%%%$&&$%%&%%$&&%%%%$&%$&$%%&'%%&$&&&%&&$%%&&&%&$%&&'\"&%&&&%%%%&%%%%%&%&%&%$&&%%&&%%$&$$%%&$&&%&%%$&&&%%&%%%&%&&%$%%%&&%%&&'%&%&$$%%%%&$&%&%#%&$&%%%%%$&&%%&%%#%&%&&&%%%%&%%'%$%&$%%%&&&%$&$&%&%%$%%&&&%&&%&$&&%#%%%%$%%$#%%%%&&%%&&&&&%$&&%%%$&%&%%&%&%&#%#%%&&&&$&&%$&%$%%&%&%&$&%&%%%&%%&%%&&&%%%%%&&&$$%&$%&$&$&%#%#%&$%&%&$%%%&&&%%&$%&%%$&&&%%&&&%&&&&&$$&$&%%%&&%%&&$%%&%%%%%&%&&&$$&%&%%$&%&&%%'&&&%'%%$&$%%&%%%&%%$%%&%%%&%$&%%%%%%%&%'&&&%%&%%%%$&\"%%%%%&%%%&&%%&%%&%&%&%&%%&&%%$%%$%$&&$%'%&&%%&%%%%%%%%%&%&%%&&$&$&$$$&%$&&&$&&&$&&%%&%$%%%$%%%%&%&%&%%%&$&%'%&'%&%$%&&%%&%%%%$%$%%%%%%&&$$%&$%%&%$&%%&%$&&%&'&&$%%&&&&&$&%&&&&$$%&&&%%%&%%%&%&%&%&&&&%%$%#%$&&$&$%&%&&%&&%%&%%&$$%&%&%%&'%%&%&&&&$%%%%&&&$%&%&&%&&%%%%&&&%'%&%%&%%&$%$%&%&%&%$%%&&&%%%&%%%%%$%&%&%&'%'$%&%&&$%&&&%&%&&&&%&$&&%&%$&%'&&%%$&%&%%&%&&%&$%&&&&&%%&%&&%&&$&%&%'&&%%&&$%&%%$&%%$%%%&%%%&%&&&%$&$&&%%&&&&&&\"&&%%%&&%%%&&%&%%&&%%&%$&%&&&%%%%%%%&&&&&#%&%%&%&&&&$%&%&&&'%%&%%&$$%&&&%%&%%%%&%%$&%%&&$'$$&%&%%&&&&&%$'&%%%%%%%#&%%&%'&%&&%%%%&%%%&%&$%%$&&&#%&&%&%%%&%%%&&%&$%&&&&&#&&%&'%%$$&%%$%&&&&%%%&&&&&&%&&%%&&#%&&%&%$&&&#&%%$&$%%%%%$&&&%&%&&&$%$%&'&%%&%&&%&&'%&%&%&%%$&%%&&&%%%&%%&&&&&%%%&&%%%#&&$&&&%%&$&&&&&%&%&%&%&&&%%&%$%&&&$$%&&%$&&%%$&%%%$$&&%&&#&&&&$$%%%%#%%%&&%&&'&&%%%$&$%%%&&%%&%&&&$&%&%%&%%%&$$%$&%&$&%&%&%%&&&$%&'&%%&%%%%&%&&&&&&%&%&%&%&&&&%%%&&&&&&&&%&&&%$%&$%&%%%%&'%%$%&&&%%%&&&&%&%%$&%&&%&%$%%%%$$%&&$%$%$%%$&%%%&%%&&&%$&%$%#%&%&&%&$&%%%%%#%$&%%%#%%%&&&%%$%&&%&%&&&&&%&%%%%%%&&&%&&%&&&%$&#%&&%%&&&%&$&%&&%&'%$%%&&&%'&%&$%%%%&&$%$%$&&&&%$$\"&&%$&&&$%%$$%%%%%%&%&&&%%&%%$$&$$&%%%%%&$%%&&'$%%&%$%&$%&%&&$%&%%&%%#%&&#&$$$&&%$$%&$%%%$&&%%&%&&&&&#%$%%%&%%%%$%%&&&%%&%%%&&&&&%%&&&&&%%%%$$%$%%&&&$&%&#%&$&$#&\"&%&%%&%&&&&&%&%&%%&&#&&%&$&&&&&%%&%&%&'%&&&&$#&$%&&%%&%#&&&&&%&%%&%%$&%&%&&%&%&$&&%%&%%%&%&%%&&&&%%&&%%%%&%&$&&$&&%&$%%&&&&&%&&&&%&$&&%&&\"#&&%#&%%$%&&&%%%%$%&%%&&%%&&$%&&&%&%&&&$%&%%%%&&%&%&%$%$%&$%%&%%%&&%%%&%&%$&&&$$%&&&&%%&%%&&&%%&$%%&&%&&$%%%&%&$&%&%$$$%%%&$%$&%%&$%&&%&&%%&&&%&&&&&&%%%&&&%&&&&%%%&&%%&%%&'%%&%$&&%%%&'%&%%&&$$$&%%%&&&%&&%%&%&%&&&$%%&&&%%%$&%$%&%&%&%%&&&%&%$'%&&&%&#%'%%&%%%&&%%&%%&%&%$$&%$&&%&%&%%&&&%$%&%%$&$&%%$&%$%&%%%'%&&%%&%&&&&'%%&$$%%%&&%&%%&&%%&%%%&%&$&&%&&%%&%%%%&&&$%&%%&&%&&$%%&&%&%%&&&&%&&%$&%&$$#&%%&%&&%&%%%&%%%&%$%%&%%&&%%%%%&%%&%%%&%&%%&%%%%%&&&$%%%%&%&%&%%&&&&%%%%%'&%%%&&$%&%%%%&%%&&&&&$%&&&&&%&%&%&&$&&&&$&&&$%&&#%%%&%&&&&%%$%%&%%%$&'%&&%%%%&%#%'%&&%&&%&&&#%&&$&%$&&&$&&%#$'&&%&%%%%&&%$%&&&%&&&%$&%$&&%&&&&%%%&&&%&$&%%&%$%&&$%%%&%$%%%%&&%%&&#%&&&%&#%&&%%&&&%&%%&&$%%%&%&&&%&%%%$&&$%%%%&%&%%%%&$%&&&&$%&%&#%%%&%#&&&%&&&&$%$%%%&&&%&&$%$%%%%%&&%&%$%$%&$%%%$&%%%%%%#&&%%%%&&$%&%$&$%&#$%%%%%&&&&%%%$%&&%%%%%$$&&&&&#&&&&%&$&$&%%$%&%&&%&%%%%&%&%$$%$%&&&$%%%&%&&%%&%%$&%$&%$#$&%%&&%$%&%&%$#%%%%&%%%&%&%%%%&&&%$&%&%%&&'%%&$$&&&%$&%&%&&&&%%$%$&$&%$&%%%%%$&&&&&%%%%%&&%%&$&$%$%&%&%$&&&$%&%$%&$&&&&&%%%$&&#%'%%%$%%%&&&%%&&%&$&&&%%&%%%%&%&%%%&&&&%&&%%%%%%&%%&&&$%%&%$%%$%%&&&&&%&&%&$&$%$%&&&%&%&%&%&&&$$%%&&$%&&&$&%$&%%$%%&%%&%%&%&$%&%%%&&%&$%&&%%%%%%&&$&&&&%%%%&&&&&&&&$%%&&&%&&%%&%%%%%$&&&$&&&%$\"&'%&%&%%$%&&%&%$%$%&%%&%%%%%%$&%&&&%%%%&&&&$%&&%%%%&$%&&&%%&%%%$%%&&&%%%'%$%$&%%%&&&&%%&%&%&%%$&%%%$%&&$&&&&%$&%%$%%&&$%&&%%%%%&%&%%%%&&%&$%&%'%%&&&&%&$&&&%&&#&&%&%&'%&&$&$&&&%&%%%&$&%&&%#&%%%&&%&%%&#&&&&&%%&&#%&%%&'%&&&%&%%%&&&'%%&%%&&%&$%&%$%&&%&&$&%&&%&&&%%%%%%&%&%&%&$$%&&$%%&&%%&#&&%$%&&&%&&%%%%%%&&%%&&%&&&&%%%%&&&%&%&%%&%%%&&&&&%'&%&%$&&%&&%%&%&%%%#%%&&&%&%%&$'%%&%%$&&$&&&%&$&%&&%$%%&&&&&$%%%&#&&%$%&%%%%%%%%$&&&%&%&&%$%&%$%&%&%%%$&%%&$$%%%&%&%%&&%&&%$&%%%%%'$&&%$&&%&&%%$#$&%$&$%%%&%&&'&%&%&%%&$%&%%&%$%$&&%&%%%&%$'&&%%%%%&&%%%&&&&%%%&&%&%'$$&&&%%&%%%&&&%%%$$&&&&%%$&&%%&&%&%%&$%$'%$&&%&&%%%&'&&%%&&&%&%%&%%&%&&%$%%%&%%&$$&%%&$&&&%&%&%&%%%%%&&%&%$&%&$&&&&$&&&%\"%%&&%$%%%$&&%'%\"&$%%&$%&&%&&%&&&$&%%&%&&%%%&&$%&%&&&%$%%&&$%&&&%%$$&&#%&$%$&&&&&%%%&%%$&&%&%&%&&%&%&&&%%%%&%%&&&&&&&%&&$%&%&%&&&&%%&%%&%%%$%%%$&&&$$&$%$%$&%&$%%%%$$$%%&&%%&&$%&%&&'%$&&&&&%&&'%%&%&&&&&&&%%&%&&%%&$%&%&&&&&&%%%%%&%&&%&%%%&%&%%&%%%&%%%%$&&'$\"%%%&&&$%'%%%'%%&&%%%%&&&%%%&&&%&#&%&%%%%&&'$%%%&&'%&%%&&%&&%$%%%%%%%&%%%%$$&&%%%%&%\"%%%$&%&&%$$&$%%&&&%%%&&%%%%&%$&%$&%%&%&%&&&%&%&&&%$&&%%&&&&%%%$%&%%%$%%%&%&&&&&&&$$%$%&%&&%&&%%%$#%%%&%%&&%%%%%%&&&&%&%%%&%&%&%%&$&%&$%%$$$&&%$&&%&%&%%&$$%%%&%%&&%%%&%%&&'%%&%&%&%&&&&%&&&%&&$$&&$&%%&%#&$$%%&&&%%%%$$$%&&%&&%'&%%&&&&%&&#&%%%&%%&%&#$&&%&%&$%&%$&&%$%%&&%%%%&&&&$%%&&&&%&%&%%%%&%'%%&#&%%&&&&%&&%%%%%%%%%%%&%&&&%&%%%&%&%&&%%%$&%%&%%&&%&&%%&%&%$$&&%&$&&&&$%&%&%%$%&&&&%&%&&&%%%#$#&&%&&%%&&$&&&$$&&$%&%%&&%&%&&%&$$&%&$&%&%&&&%&%%%%&%#%%%%%%$%&&&%&&%&&%$&&%&&%&%%&%%%&%%&$&%%%&%&%%%%%%%&&%%%%&%&&&$%&&%$$%&&$&$&&%&&%&$%&%$&%&&%&%%%%%&&%$&&%%$&%'%&%%&%$&$&&%&&&$&%%&&&&&%%&%%%$%$&&&%%%&%&&&$&%%$&%$$&&&!&%&&&%%&&%%&%&%%&#&%&%%%%%%%%$&%&&%%%$&'%&%&%&%%&&&&%%&%&&&%&&%%%%#%&$&&%$%$%&&%%%%&%$%$%&$%\"&%$$&&'%&$%&&$&&$%&%%%$%%''%%&%&%&%&&%%%$&%&%%%&&&%%&%&%&%%&&&&%%&&%&%&$$$&%&%&%&%&&%&$%&&&%&%&$%&%#%%%$&%&%&%$%&&&$%%#&&&&&$$%$%&&&&%&%'&&%%&%%%&%&%&%&&&&&&%%%&%&%%&$&&&&&&%%$&%#'&&%&&&%%&&%%%%%%&$%%%&&%%%%%&&&%%%&&&%%&%%%&%%%%&&%&&%$%%'%&&&#$#%$%&$%$%&$$%%&$&&%&&$&%$%%&%&$&%%&&%&$%%%&%&%$%&%%&%$&&%&&%%%'&&&'&%%%%%&'%%%&&%&$%&&&$&%%%&$%%&&%%%%&%&$&&&%%&%$%&&$%&&&%%%$&%%%%#&&#&%$&&'&%$$$%%%&%&&$&%&&&&%$&&&%&&&$%&$%&&&&%%%$&$%&%%&&%%%$%%&&$#%%&%%%%%%&&&&%%%$&&%%%%%$%&&&&%%%&%$%&&$%$%%%&&%&&&%%&%&$$&%%%&'&$%$&%&&%%&%&&&%%&%%%&&$%&&&$%&$%%%%&%$%%%&%%%%&&%%&%$%&'%&%%&%&%&%%&%%&%&%%&&%%&&%&&&%%&&&%$%%&%%%%%&%&&&&&$%%$%%&$$$&$&$%%&%#&&&&$%%%&%%&$%&&&&&&&%#&%&&&$$$$%&$%&&$%&&%%%%%&%&%%%%&&%&$%#%'%#%&&%%&$%%&%%'%%&&&\"&%%%&&%&&$$&%%%&&&%&$%&%#&&%&%&%&%$&$%&&&&%$%%%&$%'$%%%%%&$%&&&&&$%%&&&%#&&%%%&&%%&&%'%%&&$%&&&%&&&&$%%%%%&&$&$&%$%&&%&%&&%$%%%\"&&&&%%&$$'&&&&%%'%&%%%&&$$&%&&&&%%&%\"\"$%&&&&%&%&%$%%%&&%%%%%%%&$$'&%%%&$$&&&%%&%&%%&&&&&%%%%$$$&&%%&&%&&&%&%&'&%%&&%%%%&$$&%%&%%%%%&%%&&&&&%&&&%&&&&$&%$%&&&%%%%%%%%#%&%&&&&&%%&&&&$%%&%&$%&&&%%&%%%%%%&%&$%&%&%$%$%&$%&&%&&$&&$&%&%#%%%&$&%%&&%%%$&%%&%&&&&%$%%&&%&&&%%%&%&&&\"&%&#&%'&&&%&%&&%&&&%&&$%%&%%%%%&&&&&&&%$%%&%&%%%$&$&&&$&$%&&&%&%$#%&&%%%$%%%&%&%$&%%&&%&&&&&%&&%%%%'%%&&%&%&&&&%%$&%$&%%&#&%&&&%&&%%%%&&%%&&&%%%%&&&&%&%&%%'#$%%$%%&$%%%&%%%%'%%%&%%%$%&&%&%&%%$%&&%&&&&%&%%%&&%&%%$%&%%&%&&$%%%%&%#%&$&&&&$&&#&$&%&&&&&&&&&%&%%&&$&%&&%&%$%&&%&%&%&&&&&%&&$%&&$%&$%&$%&$&%%&&&%&&%%&&%%%%&&&&&%&&$%$%&%&&%&#%%&%%&%&&%$%%%$&&&&%%%$%$&%%%&$&%&&%&$%&$&&&&%$%&$%%%%%&%%%%$%&%&%&&&&%&%%$%%%#%%&&%%%%&$%%%&&$&&&%$%&%%%%$&&%%&'%%&&&&%&&&%&%%$&%&%%$%'&$%%&&&'&$$&&&%$&%$%&%&&$%%&%&&%&$&%%$%%'&&%&&&&&#&&&%&&%&&%$&%%%%%&%&%&&$&&%%%%&&%%&%&&&%&%&&%%%&&%&&&&$&&&&%%&%&&$%&$%&%%'%&&$&%%&%&%%%$%%&&%'%&&%&&%&&%&&&%&&%%&%%%%&%%$&&&$%%&%&&%%&&%&&&%%%%%&%&&#%&&%%%$&&%%&&&#%%%&%%%%&$$&&$%&&$&&&$%&%%%%$&$&&&%'%%'$&$&%$&&%%%$&&%#%%&%&%$&$%&%'%%&&&%%&%#&$%&&&&%&%%%$%%&%&%&$&&%%%&&%$%%%&&&&%&&&%&&%&&%%&%%&%%%&&&$&&%%$&&&&&%%%%&&%%$&&%&%%&%&&%%%%%$%%%&&%&&&%%%$$$&%&&$&%%%%&&&$$%'&&%$&%%%&&&%&%%&&$%&&'&$%#&&&$'&%&%&$&&&&$&&%%&%%&&%&&$%$&%%&&&%%%&$&$%&&%$&%%&%%%%&%$&%%$%&&&$%$%&&%$%%%&%&%%&%$%&%%%&&&%&&&%&&$#&%#&&%$%%%%'%%%&%%%&&&&%&&%%&%%&&&%&&&$$$$&$&$%$%%&&&%&%&&&%&%&%&%&&%&$&%$%$&%&%&%$%&%$%%%&&&&%%$%&$%%&%&#$%%#%%%%&#&%&%%&$%&&%&%&%$$%%&%$&%&&%%%%%&$%%%&#%%&%&%%%'$%%$%&%&%$&&&%%&%&&%&%#&$%%%&&&&%#&$%&%%$%%%%#%%&$%&%&&%&%$%%&&$%&&%%%&%&&&&#&$$&%&%%%&%$%%%&&%&%%$&&&&%$&&%%#$&&%&&&$&&&&%&%%%&%&$%%%%&%$%$%%$&%&&&%&&$&&'&&&&&$&&%#%&&&$&%&&%&%#%&%&$&&%%%%&%%&%$%%$$%&$&#%&%$%&%&&%$%&''$&'&%&$%&%&%%%%%%&%&&%&&&%&&%%&%&%$%%%%%&&%&%&&&&#%$%&%%%%%%%&&%#%&&&$&%%%&%&%%%&&%&&$%%&$%&&&$&%&%%%%%$%%$&%%%$&&%&$%&%&&%%$&&%%$&&$&&&&&'&%&%%&%%%$%$&&%&%%&%&%&%&$%&%&%%%%%$%&%&&&&&%%%%%%%%%&%%%&&$&%&&$%&%&%&&&&%%&&%&&&&&%&&$&&&&&%&&%%#&&%%&%&&%%$$'&%%%&&&&&%&%&%%%%&&'%%%%&&&'&%&&&&&'&&%&%&&&&%&%%$$$&&#%&&&%&$&%%$%%&%%$%%'$&&&%&%$&&&%%%%&%&&%%&%%%&%%&&$%&&%$&%&%'%&%&&%&&%&&&%&&%%%%&%&&&%&&&%&%#%&&%&%%&%%%&%%&&%%%%$%&%$&&&&$%$&&&#%%%%&#&%%%%#&%%%%%&%%$%%&%%%&%%&%&%#&&&%&%%$&&&%%&%%&%&&%%#&&&&&%$%%&$&%&&%$%&%&$%$$%&&&%&$%%&&%&&%$%&&&$%&%%&&%%&%'$%&%%&%&%&$%%%%$%&%%$$&&%%&%%$%$&%%%%$%%&$&&%%&$%&$%%&%&%'$&&%%%%$&&%&%&#$&%&&&&$&$&%%%%&$%%&&%&&%%%&&%%%&&%%%&&%%&%&%&$%&$&&&%%!#%&$&%%%%%&#%%&&%&&%%%&&%&&%&#$%&&%&%&%%%&%&%&$&%&%%&&%&&%%&%$%#%&%%%%&%&&%$$%%%'%&%&&%$$&%&%#&%%%&&%&%#&%%&&&&&%%&&&&%&%&$&&%%&%%&&&&%'&%&$&&&&%&#%%$&%$%$&%&%%$$&&%%&%%%$%%%&$&&%&%&&#%&&%%&&$%%&%&&&&&&&$&&%$%$%&&&%&&&%&&%&&%&&&&&%%%&&$#&%$&&&&%%$%&&%&&%$$%%&&&&%%#&$%%%$%&&%&%%%&%$$&%&%&&&%&&&%$&$$%&&&%%%$%%%%%&&&%$%%&%%&%&%%%%%%%&%&%&&&&&&&%%$&%%%&&&&%%%%$%&&$&%&&%&%%%&%%&&&%%$&&%%%%$%%&%%&&%%%&%%&%%%%%$&%&&&%&$$%%&&&&&&&&%%&%%&$%&%&%'$$%%%&$$%&%$&&%%&&%%&%$&%&%&&%%%&%&%%%&'%&$&&&%$&&%&%&&&&$&%&$%&%$&&&%%%'%$&&%%%%&%%&&$%%&%&&&%&&&&%&&%&%&%&%&&&&$&&&&"
Returns: 
"This test case has 10000 nodes.  D = 10 and a = 0.3403916445508408.  There are 10000 queries."
Download
4)
    
"15 6035,63/5+-25211*371/153.0506-654,4-71/0.2'1-2/1/734011./-*125335-01*424520+2-36503.1/1-6-00/4/3.6.(4+241457044+-+7/1.-01/2266/.0056234.(1.7.33.///0--0+2.2627/4.26+/0/*)1,-5027/203.+11/5..114251,*2-/6545'+63-74,1/34205.,0/02045//7-/*33613+.0&12-5+.--2.43)6+25034311.2.0.&.5-/2,862)/2344-3030233/065/363114656143/-/.23+52-53/4-3+02,10.2615.304-/3.6042613205424752145/84.+5*/4,/333'502(1+12230-7(.,64,.33..222/213)4-343(+8146340.0413/62/31,6/5(41)31/.201-3/66.-1+40,/,70533024844342.2/-3-132.+1&005533-53//3540.5560)/151.51/5-/+0*253.454/\"3/11430437137/041303/3/**06*+42,/0,3131*2.06+143*50/0/3.56211505&7/2*32)4/-0+-7620(-,)40/465*.500064641.5,4545064/4/.-/6-/4//6/62''8.053,51,52./2&,02+330/1/11.1106251,/23(-,0075.22(46+3344/710/6)2,3))+4.41+./4,3,/0240.,0)444591/003*0047,346..5-24027224/,020203.03-+0043216.,4213444.263551*0*-/&.23.3030/-13353-2346414054210112/01+0+1155-+1.85-1,0*131.421234*56012.014635152031.1*650.-3/433/54-320035.223-5.3032615104121.3101/236.01/-035524706/624,0/14024001713/022,/3/2.40/5.005//.115,/33.4/13,.533142-3.-0/+/3253'+5141/,,14234001.,0/67110202-+*4/.4+5-21/4,630036.470551354+0//-1,.5103004/2**6.11/6/341+4.07-,103512,8611./5-64363)2/26363-1*,531..3/0402//0/*6*-12511111'4/01152552.604,5.45..3457744/3336152,5.14535*213631+0'031210+25-344.81,1-4143222,543.2./44/07../07-12+.13/-,0.02)603+0/0.36/3104633//)-3,2/35/0224453270031003/0*+0,2/9*401/1/160/425635),4./2.12*7531,1604).24+1+46*3402+-31-05/1/521020/5.,-004115-4242.-/-0-3/13/33*14201)3..223,67.-)053314+32/023,-33*+.45433,7+*+.4122,&3431151/3-23125+24/(2+12*0213/7*'69/.5353562140,2//12-*+2203-5--./5262/40.65260-214454+/3(3141.2.5,3,.32/,00232+0023/401/136734,-0862244*(94/.)677)600*13133,32.2327.43002&-/'051421.4-224/0003/432*4125+/.02133.5/51--720612664334//-/1.81)44443301,3-2-3+3/5*0-4413751-+5:0371/8172+11,345,4.0104/0003/.+,)-/356))1(07502/.32,6(062,421..4-52,0+0-.522/4/721.3*336,*,346334*74921523,500124303-4573++,22070'76.1+,-/352456230134,313445663444)532.,3//+163+4433,00.6602/230140/5355.,.*.//3755,/371+-&6-6206/3/3,5.4)3,0103/05731114517+51*/17/33-01226,131141).(21-5).1130))1*16--+4.4320)2045+/./20,.1.1).,64022320,401/-3173*.446741+15-1030224.1'/0442446432-3+*10/644613/6-11/07/05/40340(4-/47.0/444/138062-3136/6+3..(0+34303302/0--2252663*.102+15402/*0)83-7.+043,'-432//*3,52,16%.22,,0+35/5.+4.1201.-'5602110)31,23+.0'*1*+2,)6490551+560/2675/25510.2,07.872234-637:.-.0/)0.-10/00602.-0-54581,4*41415-+52.0+)034//22060-41,0,546.1,075-3--.2/-0,/052,//.*/3-1303540463,1/+.563)3,50/2123516021)4.133*20+50,5391/07604625*01.13-+.0,5022.,5454,4//0,73/11634120..13,/2/75.0424.3,31220,2401*.,/57.663)02/2,*023/6105-01232///125+3/.22,2310,,5,85/*38744420(+*31/1255-1$(4+03-*0+3132295)14121)3-11-52.1144*4743,4).)4/5512667141/-(.,32/.01-00/21-200216(/562/.3/).05/555,.200/,/.6/2.20532.-3.061647/,+26.,,4./184*.1100/00517'124.3,044414,02-00,6.2360-3'/6-5-/22+)4.3410200771*.322343(32,1,25--94$.2/*02..105341+602-9.23)101/40/14-+3/5322(+02*21+/--,4.4.20314.4,2,5016/21,0*3750-2311-5+0,3+00-)3441/22/-2201.-+405.*0743421114-3/*45/1-,7/0231556,688/3016,-3252%-/500*06.4314/636512.0332(-)53-/21123-3/2.47544/312524../638/332.50535),40%0.(1/+.52/74/513,,312.-4140.2/01,252-(230453.2.3*+250/0.3-1)166-1323*31,10041',253.58(/3)12,.33.1'*7)1+215.61501140512.5.3/03.5/0421/4.6.1,*4*4/04/0724-5-)43/02/640-1+2,1/0+4//0/31.21252.+.00012//+12.1/31511.1.-123531///(1/13-630-07202-414443.65//*+76427+-.77/2441156,06735670/6'0242)24713-5(.110140(+/51+0+,4/6,//-./42037125-83/335**413.0-111442131051401452/244,62)0*2*.4+33+1+.40154/.3253/4143/.,..20.51/.25+-2-.2,/2/54.43/05//43,6-38061.214501*074143.352./0330)161/3)8,0612515-0,0153-41/)//212446.+.0,21.33/-10(1/3/14433+51462,-1/40.07/60/2/4)2)..06444.2.305/,262#2+1-026205/134..443*6.21133+1,3512*5+443/2,-.331)-0020,+4*-36)34116001741/0/3621&)/4'.&10/03,'003.,3+,-/-3002,32,/+5/1)/5-6/50-86441.1-714(/7-2321373332.4,0101-132003303/).2.521*351-),#--7,,,64,44+-14'3-.0.5,/5*1.211,+-16/)14330626.86/5.0,1'.365.53050+411./(1./63343,,9413-.029//61332021202&002,2034.(*)2405+)2,012237.2)-5*04%1%537-4302204+2222-0067008061423,0,/41./2751.-23330121433/1215/,.3-4-/1/2540&1/5)341+3/314)(5'40,00.0(020,831,-2241341.4060,262.4/(.0220.111.5+021**07,2,73.406-35+)1.114+/27*/2531&420//45.4.++/.222-,1205.*3401071272411/41+44*,+4-.72-053362434/162(231501.0)415255,2166222401/3.+00421.3/-33-/2333,/3-23/3121+.25/3*-5.3.+143772424)/3510350512-5014+2.1607383,314+(.,363.3-1,312-16-4.20).1.-20)/340060&121232,51*40.,(*153-,/72/250,1104262242//4.32/514../3/,234/.7-/4170416010903-1422/544.62,/8&12.5//-15+0-,323103/3,//223362/.,10.22130726417)142/2343--0423-054/304/1601/0+22301-1/+2162.-)32.1105/3411,4314252201)726/2..0-05*2534'136,3010.,-/63*6.52.32127-123655-13,1430('3100+'.1*5/30)'2'+/35211/,3024/,,11(0-25235353,'0244122,7.1//132544514.463430/.,2.48+3--301-46-,/51/*05400/...-/23,+147,52.,160+21-)(,+331.0/41)/33251703//35.24,*3.4-'25716(+.60.(323201,/0233,//0+55.(26/04.+10.2+3+13252.3.4+66/3043,2,212.4+576./1&/5+044261,(2/41-1/13+./3400304/.63426022354,//3.-)-63/*2.412025*15116-6224-56141./3(.53530)165)1173+.4&3261824344013.1,17.14531011/1,52010./*2/00//-.4164361)6401234.41.016312233*5144162,72/56622/40//37.3/..+/)141-110(2)130/+512.011262,,44314*21183241+3035,+5/*9*31.*0/152311223-62330)3,31/134237110.*13+106/5320*/1432-24225-*0./363.3.2./+12336/323122/.7+).1,/5//0510,//1602.4-/20+-30//0,(3-61-15470,03.206.1'/22*337*5/4,3*200/417362.2/24521,405421%/050,%1.66/,3462353-37341,/4421420,3120-1$--0/0*/3352.206)50702160+6-211083335/42)02,4421324-32.313*22//3+1/.02-2*10(/210)3650.302.0/00/.1131/.6+21-,-2803+0055212%/611444+/)-3,3/4443405//-20,35.363-720333562/1-.46154103/./+52,5/(41*40(2/3./3,$3512*5./+,21/1105100.500/6064+.*/3/41/.52332242.4-000.581314,325316//.2426*243-931414363074+8*225&*.01670-721(.00002,2041.,315.46)23131)045360/-33+41+(,5-81/0/2/22,.65.535102,50+4//6,1142)1,23438.321513/065305.+3160622311435/50(355/0(1.5-331020,/1*051/2.5330'.3+1+153..6084152*.54863420/33//2/2413000613*14,05425526/4/5745+3431203)504,5,2131/4545-52/2*06-*343-4+66+033583(2,+75+,6',2+143(/+012'211)3.-003126436+423/,/144+2*1)3-71-4/-742034-.2+5-5/22607-3-23122/2(//23.4)71.6-)056+/0'546/0/.3622.+.42400/353.21,2511(.02,0+/+01.001/-2342/.-.,31,(13$-03432513422-2-'4060023015*3*3*5.0443-3--2)11,5.+32052720350081/(2.60.2$245-16103(/02*151253-+2+315//0406-722*+*.4..3441032.244-252-4-.116/4.,2/66523-2-4104635-..,7454.*,2405.1-+072261/30+/5+21-*0600//234.4.*,)1050/13+2//2.423/41*/,/4231/4/3)4314/-25+553(.,-34-7442604)31652.08)23*--184..-.33)(/-5*+*.3-3711236003/42614023132022(5.,1*402441645/508354..('23-.1//2.4*,14/$+50.1.61'044/0,5243/03.,2-2,0424..8-03166,/3-/,5,.5-2/63//-.53&3-/034.421--*.5.440+17&022524/0565145.15/3(**10/052,3246705215--,61)446(/5,03+13002/805242/./(33,537**--014/&/1-113-/23215)/.21423-0-30.2432,3,5+4,,,546-3630'8)1740(-026240-)3.7.1...10/733053,).1.1+1-+/362+333+50*/4*/4224/450/324/632044020/7223/+2/04//.2,-30-/40,2313.24*3/3332-+2.,1-26.63313.1313&4347)3/34063-//20./3-1/7-5.0143/624265137-6'2-263/3432,03//5335103+03.462,27.064-,72520)$02326314.1*2(3+.8..21/136410415,/30312-+03)1/12244,06)110-262,-/0/,+0664/.51.41213150220441.4(+5231*2/14(72.53466.146*/442424/2-+836102453+/42.+4(1,3453.13/0545(4/4-21,1,--1)/2111.61/4625)3653+,//.-06/3310063413130110/*,47-3-.5435113-052-.1/1*3617/37-'2,*,3454.-3--133623041-,34--+.4420..$5-1+355,.244.412,2544+121,2/423+,5.+,5/1630-12242.351-52,-.,13-///-436420--/15/.650546/5/3/31425.146.13,762*,,413+1/*/,,5,1/643-3150241/)1150927.12-43.//./-23..6*04/.0114-6225.613-1///41221252)'26-504350+,5//1713/.61137323359234461,2240.51-1/.05+22108(24512'26.673543-2.022.7'5*5610-.44/110'0/)2/350045-553.04/5-4+3131-0.2/6,0211-/,63015-0/43454420/5/--63*55,232)-31324,03*.31').-30.0,3+1*-6432063324122804/1-4.2424/47613/.-*461041284/4.11(20424543.5-7(54-3/+03.1,.10123454/*0162.,51-2.,6,-3.,/074703056442.3607..43104622*851.0/1+82-6521371143-//31-14/02644/63/0/3./7+1)6-2(,/5/2.*31301/0111+31/1140/1-+2323.1.67422+*220//.0/1+,605/-7.55204-/4233,34227,4.6-38--4.642%4-51,&830+/.304*618*2/13)12550241260126---3-22-41410-6*/2434.0,1/4101.01'525,33300--/245+33.*24431/2.5-12'326373/*14,2*0502..2216317/..16,5.1411/2424)3512+'.54.,3-60/30614/2.41-1/-1/2+1-1,22/.../7/2/1311226450445-424153432213421/325466,+0*132+5/4./6058-(-.535-(0.44330*2456124/&435055503425.-*0-1.#.00/'/742/2333-26)55.3-50600/01-+07/.13//051/,35.,.17,5(4,20/3,53/51214533.36225741-/1+.73/50*4'.4'+35/-+1)00302521*12,/43-60367552)4/,51+'130//-273,.40//07017/,36250010.430/2-413)36.123603075124/70-6510.52.3.0/.-/62120.4+3414100.'260141-,2.1736/0/021/2-1205-/.,)1.623..224*)131(/4863/0-30(01.4+3656*/356,+187.*1.4,542/2/133*.+112.134262-33(42348/./0434,6/50621.0231-*/54452533414/-)/41,31(562032.4/1+*1,56-/10,33140.,10-4*2442313134001*6351./.2/01.6-1/7-443/351,1(,10/(*21222,9/.3)10-105/6172425005/1.+80/1*.34/01*5624-/,16102--.6,353)12-,101,3.4+8.350/2/020063)-02163113301/44433603143+22/-/1+303/4.66.524/31.001-0-+/*351,9-./00-2242/*321,324377..*-80.3/1/41&6-.6221350321+-1+'.45./4//262503541--0+610/46*-/20/.030.*345514250'6/2/122/00)8*1,010/24'10*1445-./673.475-11/13/6+01-240,80610*4'-403401201003634-)0-421220+5/3-(/06181*3)22405533.25457414-5*0,56254523/06/534001)8/+//,56232-011./0012082540.,0/3521-//.-7,5360343/2605710005417*)200371+5//+425134.0*232-0-./11..4114,3531//1+40202,0./)21+.*-.014/116.4610(5750109233+/.20.4*0//3460/2136/+-2.6*161550//002-3/5183,34643003+203.00)342/.14+.40).3125.445351.-5,0.2/,6,,1-5230.00350222/34-1124-13.+.2-25532540,0+42.004-14314371.44-6/4-(5051/02/6201-0426003/(--55,1//(5225-.022/.0852404(32632'447/3/50.1.561/3/5550.23,45+.65$632-60/1/-8205*743,4+'*6/2-11.25.5-04-4.'43/-52/73.32107141321+.4412/310/6361.5,4)/5713-,0.3460410212-*05-.10)3255146(2/.00/2(21-2,0.6/30*50,/823522-0.0'-4)13.16.5/-/+33435005.*54,.33022612*4-310500.233543015/.5/0240*18)21*3/.(211/0/311'13221*10,14431//1+.1-/15.,01-.-0565023-3.,4%0+0.+53613+-/,2+4144/13-*32./&2336/5/)3015.+3/2*(83-,4234-,/3+.1(*14/51-3/.62620344/.-+21/6,2/4/201-/1,610-4623//2/,024-502(/154*65*&.4'204*30.-31//4144317(-24231-63./*1222232./4.2+535322201/3102333"
Returns: 
"This test case has 100000 nodes.  D = 7 and a = 0.9106890605104496.  There are 10000 queries."
Download
5)
    
"16 ,-.,*)+,,-,-,+*&.+,,0.,-+/.+.,,-,---.,,-+,//+.-,&*..+-...-*,-,-,-+..+.-,.+*.*-*+,+,,-.+.')+,..,-,*+*+,-,+.))./.,.,-..*/*,.'.+*++,,,+,+).,-.+-+*.,-/*+.+.,**----+0,/,--..+--.(*.*).-+*,++0,,+&++--/).++,*.),..)+,*.'+/-/+,,+,,--+.++---,...-+..+.,--/-*,.-*.+.-+.-,.-*.-**-/+*-.*/+.*-,/*+)-,.-(((-*-.---+-.,-+,*--.,..,--+)-/.-,.*,**,./-,.-/-/,.,*,,-+.+..-,--,,.-,...++++.+),..-(--,-+,*-),*,++-.,(-,-*--+-,.+-+,,./)*.-(.+(*-,+,**/,),-,*/),*,,/--,+,-.)-.,-,.(+*-*,/,-..,/.,,***/+,*+,-.*-,./.-/-,,,)+,+/+/-,..,/---,,+++-,,.*-+-,,--,,-+,+,-,+,+,+-,-.---+*-..**,.---.-(,+-,+-.,,...+,+,---.-+--./.).-,,-,.-+.+*/-,....+.+.,-/--,-,,,)-,,--,-**,*+.+.,,,.--..,,/+.)(,,(,--.,*,-,+-(.-+-+,,.-,.--)..+..,),*.-,.-,*/*-),,/++-,----,,-.--+---,*,+/.,+---++-,,,.,.--(-,..-,+-+..*,,-.,+,+*--.)-&-,,--,,-.,.,.-,--+(*+-,,.,-.-*,..,*,..-.+/+-*/*--,-.+,,+,,---,)*.,.-/./....).-./-.-.*-.+'.,--,.--+...+.+,,,-,,*,*,--,,/,,,*++.-.-,++-.--.-.+///+*.,/-*),-.,*,,-..-.,+---*.-.,+/-,.'+-+,---...+,,----*.-/,+/-/,).*+----+-/--.+/--/-*,+..,+-,,/*+--/-,-++-.,++../).,---+++-,/-,-+-,*)+.+,--/,-(-+/.,,*--++.---.+.-,-.,,/-/-.+-..-,--*-..+,+.-,.,,0,,-+--+-++.+,-,-../-,/,+*+,,--/,--+--,,,,/&,/-.,.-,.*),+/-,--*.*-+..+,,.+,..-,,,+--+..*--).-,,--.+-./,--+,,+--/,--.-,*.*.++-+,+*0)(--,,-*--.-,*-.,+.--+..,,),,-+.-/--*.,)--*..*)--..,+.+.*.**.+,--*.-,-+,-+*+-(*..(,'*-+,.,.-+,/+)---,,.(+,,**-.,,/.+.+'---,,/-*-.//-+*-.*-+*,,+*..-,,/+-*+-.,---+,,',.++,+--..-.*)-+.-/(+----/,,,-++*-.-,/+,+---*+-&.-.(.*/-+--,.-++,+.-.*----,,++,,),.-*,,-(+++.*,).+.--,+--+-.,.,+.-+-*--+-.(..--.),(--...-+-+.,,----.----,-,.,,.--+++-,.+,,.,),,.,,,/+--+-.-,-+---*./+-/-.,+--,----*,./+*/-.,*-*-/,-,..,..),.+*-.,-.*-+*----.-+-,-,0,.+++-,,,+,.,..+,.+.,--.-+-,-,+,/*...+.-,,,/*,-,-,.,-,--.+-.,---).,-,+,./)-,,.,*,*/),)*././--+-+--),-.++/-,*-,+-.+.-.).,.,.+,,),--.+/&+..+,-++0-.-,(,,.,-.,,---*-.,*.+-,+-*--+.,,.,/-,,++---.+,-/,,)./-,---/.++--..-+.*-+*-/.---*)--*,,-*,--/-)/+..*.,,--,,,-,-+(.,/*,--.--(.*.+..+,,+-,-*.,.-,.-.+,-,--.+-*---*,-+*.,+-,+..--.+,-+-.,.-.,*,-+---,,-,**.,+.-&+'+*(,,*-,-,/*.*+++,.+*-(..*/-++--*.,,.,)-*,,--,.*-)*..-.+-.,-/-,)*-,./-.-.-.--*.-/+-..)+,-+.+*,.,-(.,--.*--.),*,*.--,--,-,..---,,,-,.-..+*/-+/+./)+.-,,.././)-*--,/-,--+,-.++,,,-/,,),.(*....+.-.,.(---(,-.'-'./.,/-,+-+,-*,---.,,/-...,.-,,/.,---..-+,)*,+./.+--.,..-.,,..-.,*++-**+*.-/-,..+/..--)./+.--./-.+,(-,+.,-.....*+).*--..,+*-*+.),*-,--,)-**..+-+-++-*.-.-,,-+-*+-+-*,..,/.*-+-+.-,+.-,,/,+--..+.*/./,+--,-,+.,/-),+*)----+--(*.,-,.-,/./,.(-,+.,,-/-..,*,+.*,.,+,*,--+,..,+.-,/+/-++),.-,)-,-,,+-+-+-,.*,.,..,-,,,',*,-++-.,/(..+.-,)*,--*/+--,+.-,,-+-/-,,/-),--.-,--',++.).,/-.+-.,'+--,.-.-.),,.--.+)+*+-,,,+---+-..-,+&0-----,--,-./+-,-/.-.,,+.,*,+.--.,/-,-,)+.-*--)*-.+,,-.*-++-,*.-+++-+,,,,+,,+-,,-(/+--/-,-..-+-,-,-,*--+.(.,.+-,-+)+(-,*-.-,/-+/+,,--,)'--,.*,-..,+(-)--,,-,.-+.+--..,,-/.'-././*()/,*,.,-*,+.'/.,//,-,+,.,-,,,.,)'+,.,+-/..-+,,.,.-(.-..,,-*,*-(*--+-.)-,./,---,/()-,.,--*).+-+*-+,...,/,-+.*+,.+.))-,*-,-**,+./.+,,,/,,.--*),*,--,--/,-,-.+-.*,/.+,,-+.///-(,),.+.-,/-.-+--*,..*/.+++)*)-*,./-,.)-(.0--.,+,--,-,---+-/..,+-,-.,.-.++),-,.,+,---,+.),.+../.,,-,/,-*+.-.-/--/-*,+.,*..---)--+,.-.**,-/-*--*,)..--/.,/..-,,**(-,-.+*-+.--.,.---.-*)-.+,*-,.,*-++-,-.--/..-.,-)/+.+.)-*+**++-,-.++./,+.,.-+,,.-*/.-,**.,*---,,..//.-,+,.+-//--.,-/,-)-.,.+,,,+-..)+,/+.)+*.-*-+,,,-*-.,.,,/,+++-.+*-,--.-,--,-...,/.-)*'(-/.&-,*/-,*,-,,.+.,-.+,,+../-+-*+,)-*..('/%.,--,/,,,)-...--,,,+.,/..,-,-,,.,,.--+.+/',*,+-,)/,*./+*-0*+-+.--..-,-*-,.-.-+,*/-+-,-/*..-.-))0+-,----+,(--.*)-.-+-,-(-+,(.+*,.-+/,,*,....*,&++)+--'-,,+,.+',-,-/-..,++-)+-.++*-,-..,0+*/+,-+,,,.++,--..--.,/-../+-*--.(,./,-.,+-+.,---/.-./.)-+--.*-&+.--.-,..-(*+---'+++,+,----(-.*,..+--,-,/-++,.*,-,,+.,+--,-.+-,*.---/,.++-+++)-.+++-,.-.-/-.-.+,/.*--,.--,./--,+*)+,.-++)-*,)-,,,,/.,+...-.-.-+,0-+,,-.+..-+-,,/-'--*.-+-,.-).+..-+)*,--*,,))-,++/.-**,*--,,-,+*++,-.-,,(+0--,+-/+*--.,+-)-+,*)++)-++%-.)&.+-.(*,--)+,+...)-//,-.),.-),,*,+--)---,,+.-,,-,,-+,.(,,/.,-/,,--/,-,,,.),.-*-/+-.*.-,-+,,-.,-,++,--*-)+..,---+,*+.//--,.,-,+/,-/--+.*.)(,.,.*../),,+.-,+-*--*,,-(-+,+-.,-*-..+-+-/-.*.--./.*+*,+-*,,+-,+.+,,-.-.)-,)/*.-+,,,,-+-,--+,(.+-,/.,/,+,-,+-,--.--*,*+-,-)+,.,-++,-,.---/+--+-/,,,**,,-,,*,-+,--,.-,,..--,,),*,.,/--,,*.,),--+.-+/-)+-**-.+++--,+-)..,,)+,--/.-++.,*,-),+,/..,-,-,----,--,.,,)-/*,0..,++-.-+-.*,(-,---,+,/.-+-.+-.--.+.*+,*(+-,-)+-.*+,++++,*-.**,--,.--,-)*---*+--,-.&--++,+.--.+-.+.,-+,--)+++-(--.*,,,/./--+---.,-.----+.+,,,,'--*,*-.-,*)*,'+-,./*-*++-+++..+./--+,--/.+,.-*,-.,,--.,*/.*-.(+,*--,-,--.(-.(,,*,,+)/+.-,,-/,,-,,/-+.-,-),-),,/-+.,-----,,.-'-,,,*.-'/,,-.,--,-..,...-,(+-.++,,,*+.,.-,++,.,-+-.--',*-*.++,/,-.**)-,-)-./)++)..++)..-/-*,-(*-,+,.,/,-+'--+-,)---.,++/.,,.,--,*+--*.-+,+/--.--,-*+)-.+*,-,..,-.-).-..+.+.,*)++.,,....*.,-)+.,..*.,)++.-,+..-,*.)*+.(,+//*/,,..,/.,-/*----..-+-+,++.+)-.*&.+++.),.).---,,--,-+.-*++,,...*/.*/---.,,,,-,-)-.,.,*-,/'+-+.-/-.,+,.,-.-+-+,.*--.+--+,.+*.,,,+,,..+,,--...--..,.'+....-*-/+/+,.----..-------,-+,++,+.,),)/--,.-.--+,,+-)&+/+.+--/--,+,/+.-,++++,--,-/)-+)+-(-++***,,*+,+).,.)--.-'-*--,+-.//,-+-.,-*,/.-)/,----*--/,,---...+,-+.),-&-..--,+..----+,,.-.+/--+----*/,,+*---*-/.+.--*.+--,,*.*/+,-,*,,(,-*,-...+-*/,.-),)-.--++,.-,,+.-/+.+,.+,,-./,,-,..,,-,+,.-+*-,--+-.+.,.--*..,)--,.*.),-,)./-*-+-+--,,.-,./--,--,.,-,,*..+-,.+.-.&0++--,,*,++-++..,,+++)-,.,.*-.0+.,,./++-,../-/-&/,-.+--),-.,*.-.-,..,-)/+-.,)/),--,.*,,.,)--*-+,)--+,*.+----)-.//+-.---')+,+./+-)-/)*-/++.-.,.&+,,+-)-,+-+0*,,.,,+),++-+(,+).,+,,/-,,.+/(-.+-*)/,/*-)/,*,+-,,--+,,.-*.,-.-,.,..---)-.--.*,-,./-+,-)+..,,,+,-..-.,+-.,/,.*/)-+-*-..*,,--,-.---+--(/--.-.-.()'+.'*+,.,.-,-+,+-&/,.+-.++--.--+,/+,-.+..-.,.(-+,++-.,..+,,*+++.,--+.).,+.-..+.+,-.-.+,+,.+....0+*---./+*,,.**-++*.--/..+-..+(+,--/'--,..--,+-*-.*,+..-.--,+.+,-+,+.,*-/*.*,--,-*+/,,-..,.+-,---/*,*,.-*+,+/,+,+,.)-),.--,.+-*,.+.-,+-,-),-+-+/*,+*+*)--.-.-/-)+,,--&..(---..-,),--/.,--+-,,.+*--0.-+,--,.++-,.,-+*-0+,.,.--,--,-++.*.),+,/.+-,+/---,/++.+..-,.--,--.,.+./,,.---*(+./*.-,,,.+--/--.,+,.)//-+.---).,-.-.-+&/-+--,,+*./,+.-+/.,-(+.-...+,++/--+,+*,,.,-+.,,-..,,,.+)*,-----.,++,-,-/*,-/,,,+,-.-.*,--)*,/(-/..-+.,,,,+.-+-.-+.-+-,+-+)-,-/../-,-/,--,,*.*,++-.-++-.,.-..*----.--,,*+(+.)*--.,.-.)..,.-/.(-.-,,,.*++-.+-/.-++..**.+*..--//,,,*+--,-,+,+-++.,-...,-,-..--..,,,-+.--.-.,*,-,-(,)..,,---***),.--------/+.,-,'+--.-,,-.,+,-,-*)/-**----+.'.-.,'--++-,-+----,,,),.,++,,,+/,,/-(*)+**,,/+..+)).-----*-,,*-.(,.,,,+-,--*+*--.-+,.++,.,+,---*,-),,-,,-..)/-,,*,++.*)/.)+-+-*,./-.--+--/,.)-++-*//.-.-.-.-+-,--.*+-/*++,,-,,('.+-.',-+---,---..-,.*++-.--,//,-)+-/.,-.,,/-,.*,,(-)-++-.+,-++*.),-+-,+-+-.-*,-*).-,,*-***+,,-,----,-,++.),,....--.-,-.-,,./.++.-.-/-,..-.+,,--,-+,.-.,.,+--,+.)/--*,//+-+-+---./-(.,++++..+-,,-*+,,..-,.-,-*.+-+)-/-/+,-...,./*,+..--.-,-.+-*--..)*(---/,*-(./.*,,-//.+-/.++,.--.-.-,,*-,+,*-,--,-+-.)--.-..+.,+-,-.-.,.,--,..-,+-.+++,,,,,,,,*+.-..-,,-.+.-+-,.,--,+./-.-./...---/,,,/----+--+-.,-0+,.,,).,,-*-,,-++.-()-+,+*,*,,+-,+..,..,-*-,..--./,+.*.,.,.)().-.----..,./*))+...$*+,+,----/,,.-..(++,.*-*.-+--.*/+.*-.,-**,.,-.+.+'-,)-,',*,-+.-./,,/*+,*-',,/-.-,,+.----*+++*/&)+,.,--.+..,,-(,),,-.*---,-+-+-,'-...+.,--/...,*-.-,.,-/--.++...,..****-+--*--,-)++,)-..-..,,.*--/-+..,-,.*,..//,+,++-)+++,-,---)--/,.*-+,,.,++(.-.,--/..-,-*,/++-+.*,-.,,,./-,+...,(,--,,*.-,,,,.-.-+++..-+,.,-.,.,/*,-&,-*+-,,,-+/----'--**,)),-.+/---(,-..-,---.,*+--(..&-*--,**,.../,+).-,)---*-,--)----,,-+-/..-,--,+,../---+.+..,+.-.),-,)*,,-),)--+,.,+-.*-.-,*-.*,./,*+---,*,&,,0+*--.+,,+,.,,,),'-,++/,-.-+,-*,.+-..,+(*,...+--*.-.,---+-.,,.+---,+,*.+++,+/,,-,+-,.---,,-*+.(--.,*,---.------+.+.+)-..--**+--.*.*(*.)..+.-).-..-,--/.*--*.+-,/.+--../.---*+.-,-,-,..-*,,--+,)--/---.-,,.,,+,..*--.-./-,-+.,-./+..+*.),.++-.--+-./+-.-.-.---,/),....+,++).',,,--+-/,-+,.,,*&.,/+-.*,),...-)-,*+,-+/,+--.,+,+,).,)).-,+,,-,-,--.+,,/,/---/+,.-0*-/.,-----.---(-,-+-,,-,*,+-.,.-..+-+.-,,-,-+,--..-*--+---,,**.+,-,*..+,+---,-,,/,.-.,+---..,,*-----.,-++,,-,---,--,&+,,+-././,--.,/--,--,),....,)).+/-).+--+-,+.+*-)---.,-,-+-+-*-,,,+/.-+.-,+/,-*+-,,,.--,/..++-,,.-*---,*,+,.,-.',-/,+*-,*-++--.,*-*-----+--.,.,*---+,-*,-,-'--.,/,.--,*.,------,--,''//+--.).-,*,-,+--,/-).().+.+,*+..----/-+---/-(.,-.*-.+-*,/*-,--,+,*,---+,-+.+,)--.*(./,,--,,-../--(+*,,.-+.(.+-+(-+-*,-)++.,-,+,(+)-.-,*--,,*.-+-.-,.+.+-+-,++..(*&,)-,,---,/-(,.+-.,+-+-((**--)+.-.,+)+./-++-.).,..+-.*-*-,+*,-*,-.,-/+,+.+)---)...,./*,*.,-,.--./..,-,)-),,-.-.,/*++-.*-.+/,+/+-,--/+-++.-,+./-+.,+--,,-,.-,)*,-..--.-.-.,'++,..,,*.-,+*.-/.-+.,,),--,,),-..-,,-.,+-+,,.).*-,*.*-,/+/*.++).---)++,..-)-+-+.----+./.+)-,,,--...,--.,-/+..&+.,--,--./..-,.-+.,+,.-0,+-,+*+---+-,..-+,)/--).,.,-.+),/,.+-----.-,'.+.(,,((--,-+,-,.+)/,/++./*,+)..,-.$,.,.,...)/&--,).-+-0/,,,-,**.)++(-)-..-+.*.-..-/++..,-,*,,/,*+,+-*..+,**-,,+-.+(*-(-.--(-+,--.**-.,+--.,,/-.),/,-,-+..-,.,,-...,-+-++(,-,-.+,...(,*.,/.0..'-+,.-+-+,/-*,,.,-.--,-,-,,.-.-./.--,,+,.*,+(&+-.,/,--.+,-.,,,,+*,,--+*-'+.*-/+(-,..,-,-..+,+,.,,..*,-/.,,-,,-,.,+.-,+-/*/+++/*.,..--.++-+..+.*,-,0-.-++.+,-0.,,..++*/0**,-.+.)*--//***,,-/.,-,....-+--,/+(+-,.-.+.--.--,-/-..-,+.-+,,,.--.,*/*-.-+*-.,,,-.-*-.,.,.,-)-,,-----+.-,,+/*,+--*-)*..-,../+-,)-.+-.,,,*..,--+---+,),-.,+-.-+,,./+..,+,.,,.,.-...-.(-.0--+.-.'+,..*-..,,)+-(.*)+++*..*,*-,--//+-.,-,,*--,,/,+//,--,+-+,**-,.++,.,)*+,,,)*.+,+-..---,/-+.-,+.-.,+.-*-+,-.-,-,++/+)-/-.),,.*'-..-../.,,+.-*/.,-..,,-,,,+*+,.,-,..,..,--,--(,.+./-.*.,.++,+.'.--/-,--,-,0--.**-,----+(+,+*-..--,.,)-+/,-(-.,+,,,,-+--,-,-,,--.-*-+.-,--,.+)*+,,-,+.,,,++'/.-.+.+.-++,-)+,,---,-*.+---,-.--,,.,-'-,-,..,),/..+-*-,,-,+-.,/-+-),.--,-,/+.*-,.+,-.()-*--*.++,,*/*-)----,/.-,-.----,..-,,*.+(/*,*+---./+,++-+*,,,*.0-+-,-.*)'+-..-.++-,,-,+,+.++-,--+-/.,..,,/,-/)+,.-)-.-,-/-,.+,--,),,)/+(*-,,+,,.--++.-/.+,,.,-*',-,.,,-)./-..--)-,.*/+(-*/--.)++)-*+*,-,.+.,++-,-+..)*.,..(,.)-+.0.,,+)-,--,.,,-)-,*-.-*(,,(-.-+).-,---)--+.-+,,--.,--+*--**,,)++++--.-,+-,*-'*,+(,*-,-+.-----,*--,.+(//,,+,..-,-.,-*+*-,,-/,.+*..-/,+.*-/,,++,-,.-/,,+-,)-)+-..,-.,*+,+-.*..,.-.-.)-/-*.-,.++--.--&-+.)+*+/-+.,,,-,),--+)/,).-,,,,/-,-./.,'---.+.,..*-./-.,..*.,%-,,*-,/--,-,/,,,-,./-.,.-,...-/,+-)/+--,-."
Returns: 
"This test case has 1000000 nodes.  D = 5 and a = 0.5126586954905619.  There are 10000 queries."
Download
6)
    
"17 &&&%&&&&%%&&%&&&&&%&&$&%%%&&%&&&&%&&%&&&&&&&%$&%&%%&%&&%&&&%&%%&&%&%%&&&%&&&%&&&&&&&&%&&&&%&&&&&&%&&%&%&&&&%&%&%&&%&&&&%&&&&&&&&&&&&$&%%&&&%&%&%&%&&%&&%&&%%&&%%&%&%&&&&%%&%%&&&%&&&%%%&&&&&&&&%&&&&'&&&%&&&%&&&&&%&&&&%&&%&&%&&%%%&&&%%&&&%&&%%%&&&&&&&&&%&&%%&%&&&&%&&&&%%&&$&&&$%&%'&%%%&&%&&&&&&&%%&%%&$&&&&&&%&&&&&%&&&&&&%&%%&&&&%&%$%&&&&&%%&&&%&&&%&&%%&%%&&%%%&&&&&&%%%&&%%&%%&%&%%&%$&&%&&&%%&&%&%&&&%&%%%&&&%%&%%&%&%%$&&%%&$&&&%&&&&%&%&%$&%&&&&%&&%&%&&&&%&&&%&%%&&&&$%&&&%%%&&%%&&&&%&&%&&%%&%%%&&%%&%&&&&%&&&&&%&%%&&&&&&%&%&%%%&&&&&%%%&&&%&%&%&&&&&&&&&&&&%&'%&&&%&&%&%&&&&&&%&%&&&&&%&&%&&&%&&&%&%%&&&&&&%&&&%%%'%&&%&%%&&%%&&&&&&&&&%&&&&&&%&&&&&&%&%%%&&&&&%&$&%&&%&&&&$%&&%&&&&&%%&&%&&&&&&&%%&&&%&&&%&%%&%%&&&&&%%&&%&&%&&&&&&&%&%%%&&%&&&&%&&&&&&%&&&&&&&%&&%&%&&&%&%&%&%%%&%&&&&&&&%&&&&&&%%&%&&&&&&%%%&%&%&%&&%%&&&%&%&%%%&%&&&&&%&%&&&&%&&%&&&&&%%&&&%&%%&&&&%&%&&&&&%$&&&&%&%&&%$%%&&%%&%&%&&%&%%%%&&&&&&%&&&&%&%&&&%%%&%%&&&&&&%%%&%&&%&&&%&&%&&%%$&%&%%%%%&&&&&&%&&&&&&&&&$&%&&%%%&%&&&$&&&&%%%&&%&&&%&&&&&&&%&%&&&&&$%&%&&&%&&&%&%%%&&&&&%%&&&%&&&&&&&&%&&%%&%%%%&&%%&%&&&%&&%&&&&&&&%&%&%&&$%&&&&&%&&&&%&&&&%&&%&%%&&&&&'&$&$%&&&&&&%%&&&&%&&&&&&&&&&%&&%&%&%%%&&&%&&%&%&&%&&%%%&%%&&%%&%%&%&&%&&&&&&%&%&&%&&&%&%&'&&&&%&&&%&%&%&&%&&&&%$&&&&&&&%&&%&%%&&$&%&%&&&&&&%&&&%&&%%&%&%&&&%%&%%&&&%&&&&&&&&&&&&&&&&%&&&&&&&%%&&&%&%&&%&%$%$&&%&&%%&&&%%&%&&%%&%%&&&&&%%&&%%&%&&%%%&%%&&%&&&&%%&%&%&%&%&&&%%&&&&%&&%&&&&&&%&&%&&&%&&&&&&%&&&&&&&%&&$&&%&&&%$%&%&&&&%&&&&&&%&%%&&&&&&&%&%%&%&%&&%&%%&%&&&&%&&&%%&%&%&&&%%%%&&&&&&&%%%%%&&%&&%&&&&%&%&&%&%&&&&&&&&&%%&%&%&&%&&%&&&&%&&&&&%&&&%%%%&&%%%&&%&%&&&&&%&&%&&&&&%&&&&&&&&&%%&&&&$%&&&&&&&%%&&%&&&%&&&%%&&&&&&%&%%%%&&%%&&&&&%&&&&&$&&%%&&&&&&&%%%%%&&&&%&%&%&&%&&%%&%&&&&&&&&&%&%&%&&%&&&%%&&&&%&%&&&%&&%&&&$&&&%&%%&&%&%%%&%%&&&&&%&%&%%&&&&&%&%%&&&%&&%&%%&&&%%%&&&&&&%%&&&&&%&&&&&%&&%&&%$&
Problem url:
 http://www.topcoder.com/stat?c=problem_statement&pm=7297


Problem stats url:
 http://www.topcoder.com/tc?module=ProblemDetail&rd=10681&pm=7297


Writer:
  

Testers:
  

Problem categories: