Jolly Jumpers..~

Problem Statement
     
You may remember an old computer game called "The Incredible Machine". It was a game where you could simulate simple processes like balls falling, lasers shooting, or cats pursuing mice. Moreover, you were able to perform these observations with different values for gravitational acceleration.  We are observing a system with some unknown acceleration of gravity. There is a slope which has the form of a polyline with N vertices. Each vertex of the polyline is positioned lower and to the right of the previous one. At time 0, a ball is placed at the first vertex. The ball is small enough to be considered a single point. Assume that there's no friction between the slope and the ball, the ball is absolutely nonelastic, and the direction of its velocity changes instantly at the polyline's vertices. Under these conditions, the ball will follow the polyline without ever losing contact with it. The ball reaches the final vertex at time T.  You are given vector <int>s x and y, where (x[i], y[i]) are the coordinates of the i-th vertex. Return the gravitational acceleration in this system. A body rolling down an inclined plane of angle alpha (measured between the plane and horizontal direction) under gravitational acceleration g has a constant acceleration of a = g * sin(alpha). The distance d travelled by an object during time t moving with initial velocity v0 and with constant acceleration a is equal to d = v0 * t + 0.5 * a * t^2. The velocity v1 of the object after time t has passed is equal to v1 = v0 + a * t.
Definition
   
Class:
IncredibleMachine
Method:
gravitationalAcceleration
Parameters:
vector <int>, vector <int>, int
Returns:
double
Method signature:
double gravitationalAcceleration(vector <int> x, vector <int> y, int T)
(be sure your method is public)
   
 
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
x will contain between 2 and 50 elements, inclusive.
-
Elements of x will be strictly ascending.
-
Elements of x will be between 0 and 100, inclusive.
-
x and y will contain the same number of elements.
-
Elements of y will be strictly descending.
-
Elements of y will be between 0 and 100, inclusive.
-
T will be between 1 and 100, inclusive.
Examples
0)
 
   
{0,6}
{100,22}
4
Returns: 9.807692307692307
That's an acceleration of gravity that might be somewhere on Earth's surface.
1)
 
   
{0,26,100}
{50,26,24}
4
Returns: 26.743031720603582
And this is likely on Jupiter.
2)
 
   
{0,7,8}
{10,6,0}
7
Returns: 1.1076837407708007
Note that in spite of the angle at vertex (7,6), the body won't fly off the slope and will follow the segment (7,6)-(8,0).
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
According to research conducted recently, listening to classical music increases one's mental abilities, while listening to metal decreases them. Now, yet another experiment is being conducted to try to prove or disprove this statement.  In this new experiment, a mouse is placed in a rectangular maze consisting of NxM squares. Each square either contains a wall or is empty. The maze is structured in such a way that for any two empty squares, there exists exactly one path between them. A path is a sequence of pairwise distinct empty squares such that every two consecutive squares are neighboring. Two squares are considered neighboring if they share a common edge.  One of the empty squares in the maze contains a piece of cheese, and the mouse's goal is to reach that square. The mouse can only move between neighboring empty squares. The mouse has been listening to metal for a week, so his mental abilities have become absolutely dull. Not only can he not smell the cheese, he can't even remember where he was heading a moment ago, so he is just wandering randomly. More precisely, from each square, the mouse will randomly choose one of the neighboring empty squares and move there. The probability of choosing each of the squares is equal. Each move takes one second.  You are given a vector <string> maze representing the maze. It contains N elements, each containing M characters. Empty squares are denoted by '.', walls are denoted by uppercase 'X', and the square containing the cheese is denoted by '*'. For each empty square, calculate the expected time required for the mouse to reach the cheese starting from that square. Return the arithmetical mean of all the expected times.
Definition
   
Class:
MazeWandering
Method:
expectedTime
Parameters:
vector <string>
Returns:
double
Method signature:
double expectedTime(vector <string> maze)
(be sure your method is public)
   
 
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
maze will contain between 1 and 50 elements, inclusive.
-
Each element of maze will contain between 1 and 50 characters, inclusive.
-
Elements of maze will be of the same length.
-
maze will contain only '.', 'X', or '*' characters.
-
There will be exactly one '*' character in maze.
-
For every pair of empty squares in the maze, there will exist exactly one path between them.
Examples
0)
 
   
{"*",
 "."}
Returns: 0.5
The mouse will need 0 seconds to find the cheese if it is put in the cheese-square and 1 second otherwise.
1)
 
   
{"*.."}
Returns: 2.3333333333333335
The expectations for each square are 0.0, 3.0 and 4.0.
2)
 
   
{"...",
 "X*X",
 "..."}
Returns: 4.857142857142857
 
3)
 
   
{".*.",
 ".XX",
 "..."}
Returns: 13.714285714285714
 
4)
 
   
{"*........",
 "XXX.XXXX.",
 ".XX.X....",
 ".....XX.X"}
Returns: 167.2608695652174
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Problem Statement
     
A square-free number is an integer that is not divisible by the square of any integer except 1. A set containing only square-free numbers is called a square-free set. The product of such a set is the product of all its elements. If the product of a square-free set is a square-free number itself, that set is called a perfect set.  You are given two ints N and K. Determine the number of perfect square-free sets that contain between 1 and K elements, inclusive, where each element is between 2 and N, inclusive. Return this number modulo 1,000,000,007.
Definition
   
Class:
SquareFreeSets
Method:
countPerfect
Parameters:
int, int
Returns:
int
Method signature:
int countPerfect(int N, int K)
(be sure your method is public)
   
 
Constraints
-
N will be between 2 and 500, inclusive.
-
K will be between 1 and 500, inclusive.
Examples
0)
 
   
5
1
Returns: 3
The possible sets are: {2}, {3}, {5}.
1)
 
   
5
2
Returns: 6
Here, {2,3}, {2,5} and {3,5} are also possible.
2)
 
   
5
3
Returns: 7
The set {2,3,5} is added to the previous ones.
3)
 
   
6
3
Returns: 9
Here, the sets are: {2}, {3}, {5}, {6}, {2,3}, {2,5}, {3,5}, {5,6}, {2,3,5}.
4)
 
   
28
41
Returns: 1599
 
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.