Jolly Jumpers..~

Problem Statement
   
You are sitting in front of a mirror and looking at the image of a clock located behind you. You want to know what time it is. The clock is a traditional clock with a 12-hour board (without numbers written on it), a minute and an hour hand (the hour hand is shorter, so that you can distuniguish them). You are given a string time denoting the time as it is seen in the mirror. The time will be formatted as "HH:MM" (quotes for clarity), where HH is the two digit hour and MM is the two digit minute. The hour will be between 00 and 11, inclusive, where 00 represents 12 o' clock. Return a string in the same format denoting the actual time. See examples for further clarification.
Definition
   
Class:
MirroredClock
Method:
whatTimeIsIt
Parameters:
string
Returns:
string
Method signature:
string whatTimeIsIt(string time)
(be sure your method is public)
   
 
Constraints
-
time will be formatted as "HH:MM" (quotes for clarity), where HH is a two digit integer between 00 and 11, inclusive, and MM is a two digit integer between 00 and 59, inclusive.
Examples
0)
 
   
"10:00"
Returns: "02:00"

 

1)
 
   
"01:15"
Returns: "10:45"
 


2)
 
   
"03:40"
Returns: "08:20"


 
3)
 
   
"00:00"
Returns: "00:00"
Although it doesn't happen often, sometimes we can see the actual time right in the mirror.
4)
 
   
"11:53"
Returns: "00:07"
 
 
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
     
Consider a meeting of n businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other. Given an int n, return the number of perfect shakes that exist for n businessmen. See examples for further clarification.
Definition
   
Class:
HandsShaking
Method:
countPerfect
Parameters:
int
Returns:
long long
Method signature:
long long countPerfect(int n)
(be sure your method is public)
   
 
Notes
-
Businessmen are distinguishable. Rotating a perfect shake can yield a different perfect shake (see example 1).
Constraints
-
n will be between 2 and 50, inclusive.
-
n will be even.
Examples
0)
 
   
2
Returns: 1
Two businessmen have only one possibility - just to shake each other's hand.
1)
 
   
4
Returns: 2
Two out of three possible shakes are perfect.

     
2)
 
   
8
Returns: 14
 
 
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
     
We are building an application using different types of components. Each time we want to install a new component, we choose one randomly (yes, it is crazy). Each of the n types of components has an equal probability 1/n of being chosen. There is an infinite number of each type.  Each time we choose a component instance, we first determine if it can be installed. Some components may require one or more other types of components to already be installed. If all the required components are not currently installed, we cannot install the chosen component.  If the chosen component can be installed, we then decide whether or not to actually install it. Each component has an associated income and expense. The expense is the amount of money we must spend to install the component, and the income is the amount of money the installed component is expected to give us. Our goal is to maximize the expected total profit (all our income minus all our expenses). If we decide to install a chosen component, we must install it immediately (i.e., we can't put it aside and use it later).  Multiple instances of the same component type can be installed in the application. Each instance costs the same amount of money and has the same expected income. Note that once all the requirements for a component have been met, we may install multiple instances of that component type. For example, consider the case where component type 5 requires component type 3, and a single instance of component type 3 is currently installed. Every time we choose component type 5 from now on, we are allowed to install an instance of it. We do not require an instance of component type 3 for each instance of component type 5.  You are given an int k, the number of times we randomly choose a new component. You are also given a String[] components, where the i-th element (0-indexed) contains the requirements for component type i. Each element is a single space separated list of the component's required component types. You are given int[]s income and expense, where the i-th elements are the income and expense, respectively, associated with component type i. We will use an optimal strategy and always try to maximize our expected total profit when deciding whether or not to install chosen components (so, if installing a component lowers our expected total profit, we don't install it). Return our expected total profit.
Definition
   
Class:
CrazyComponents
Method:
expectedProfit
Parameters:
int, String[], int[], int[]
Returns:
double
Method signature:
double expectedProfit(int k, String[] components, int[] income, int[] expense)
(be sure your method is public)
   
 
Notes
-
A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
-
k will be between 1 and 50, inclusive.
-
components will contain between 1 and 15 elements, inclusive.
-
components, income and expense will each contain the same number of elements.
-
Each element of components will be a single space separated list of integers, without leading or trailing spaces.
-
Each integer in each element of components will be between 0 and n-1, inclusive, with no extra leading zeroes, where n is the number of elements in components.
-
The list described by element i of components will not contain i.
-
In each element of components, integers will be distinct.
-
Each element of income will be between 0 and 1000000, inclusive.
-
Each element of expense will be between 0 and 1000000, inclusive.
Examples
0)
 
   
1
{ "", "" }
{ 1, 2 }
{ 0, 0 }
Returns: 1.5
Here, we choose a component only once. If we choose component type 0, our profit is 1 - 0 = 1. If we choose component type 1, our profit is 2 - 0 = 2. Since each type is equally likely to be chosen, the expected profit is 0.5 * 1 + 0.5 * 2.
1)
 
   
2
{ "1", "" }
{ 10, 0 }
{ 0, 2 }
Returns: 1.5
If we pick component 0 in the first turn (1/2 probability), we won't be able to install it. Whichever component we pick after that, it's better not to install it and settle for 0 profit. On the other hand, if we pick component 1 in the first turn (1/2 probability), we should install it even though the net is -2. If on the second try we pick component 1 again (1/4 total probability), we don't install it and end up losing the 2 we already spent. However, if we pick component 0 on the second try (1/4 total probability), we can install it and earn 10 for a total profit of 8. The expected profit is 1/4 * (-2) + 1/4 * 8 = 1.5.
2)
 
   
3
{ "1 2", "", "" }
{ 100, 0, 0 }
{ 0, 0, 0 }
Returns: 7.407407407407408
Component 0 (the only one that makes a profit) requires components 1 and 2 to be already installed, so if we draw it in the first or in the second turn, we won't be able to install it. It is only possible to install it in the 3rd turn, supposing that in the 1st and 2nd turns we drew components 1 and 2. The probability that we will have components 1 and 2 installed after the 2nd turn is 2/3 * 1/3 = 2/9. The probability of then picking component 0 is 1/3, so our expected profit equals 2/9 * 1/3 * 100 = 7.407... .
3)
 
   
5
{ "1", "2", "0", "" }
{ 4, 5, 6, 7 }
{ 0, 0, 0, 8 }
Returns: 0.0
 
4)
 
   
10
{ "", "", "", "", "", "", "", "", "", "" }
{ 142352, 2342, 34534, 2344, 12346, 7589, 79872, 973453, 96233, 34567 }
{ 12432, 2345, 3678, 456, 345, 457, 56758, 4564, 774, 34567 }
Returns: 1269258.9999999998
 
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.