Problem Statement
N rabbits (numbered 0 through N - 1) aim to work at the new TopCoder office in Rabbitland.
You are to choose some of these applicants as employees.
Each pair of rabbits will make a certain profit when they work together. Given a group of rabbits, we can easily compute the total profit P as the sum of profits for each pair of rabbits in the group. However, hiring rabbits also brings some costs: they want to have a supply of fresh carrots. Surprisingly, the cost of supplying carrots to K rabbits is not linear in K. This cost is given by the formula C = (K * (200 - K)). The efficiency of a given group of rabbits is the real number (P / C), where P is their total profit and C is the cost of supplying carrots for them.
You are given a String[] profit, the j-th character of the i-th element of which represents the profit gained from rabbit i and rabbit j working together. The characters '0', '1', ..., '9' represent the values 0, 1, ..., 9, respectively. You may hire an arbitrary non-empty subset of the available rabbits. Return the maximum possible efficiency of the group of hired rabbits.
Each pair of rabbits will make a certain profit when they work together. Given a group of rabbits, we can easily compute the total profit P as the sum of profits for each pair of rabbits in the group. However, hiring rabbits also brings some costs: they want to have a supply of fresh carrots. Surprisingly, the cost of supplying carrots to K rabbits is not linear in K. This cost is given by the formula C = (K * (200 - K)). The efficiency of a given group of rabbits is the real number (P / C), where P is their total profit and C is the cost of supplying carrots for them.
You are given a String[] profit, the j-th character of the i-th element of which represents the profit gained from rabbit i and rabbit j working together. The characters '0', '1', ..., '9' represent the values 0, 1, ..., 9, respectively. You may hire an arbitrary non-empty subset of the available rabbits. Return the maximum possible efficiency of the group of hired rabbits.
Definition
- Class:
- RabbitWorking
- Method:
- getMaximum
- Parameters:
- String[]
- Returns:
- double
- Method signature:
- double getMaximum(String[] profit)
- (be sure your method is public)
Notes
- The returned value must have an absolute or relative error less than 1e-9.
Constraints
- profit will contain between 1 and 50 elements, inclusive.
- Each element of profit will contain exactly N characters, where N is the number of elements in profit.
- Each character in each element of profit will be a digit ('0' - '9').
- For each index i and j, the i-th character of the j-th element of profit will be equal to the j-th character of the i-th element of profit.
- For each index i, the i-th character of the i-th element of profit will be '0'.
Examples
{ "071", "702", "120" }Returns: 0.017676767676767676
If you choose only one rabbit, then P = 0, K = 1 and the efficiency is 0. If you choose rabbit 0 and rabbit 1, then P = 7, K = 2 and the efficiency is 7/396. If you choose rabbit 0 and rabbit 2, then P = 1, K = 2 and the efficiency is 1/396. If you choose rabbit 1 and rabbit 2, then P = 2, K = 2 and the efficiency is 2/396. If you choose all three rabbits, then P = 10, K = 3 and the efficiency is 10/591. You should choose rabbit 0 and rabbit 1 to maximize the efficiency.{ "061", "602", "120" }Returns: 0.015228426395939087
You should choose all three rabbits here.{ "0" }Returns: 0.0
{ "013040", "100010", "300060", "000008", "416000", "000800" }Returns: 0.021996615905245348
{ "06390061", "60960062", "39090270", "96900262", "00000212", "00222026", "66761201", "12022610" }Returns: 0.06871794871794872
Back to all problems