back to the menu

 Flag Counter

TopCoder SRM 542 - 1000: RabbitWorking

Problem Statement

     题目简述：

有n只兔子，第i只和第j只同时工作会产生P[i][j]的利益，
现在你要挑选出k只兔子，使得利益总和除以( k*(200-k) )最大。

数据范围：

n<=50
0<=P[i][j]<10，且P[i][j]为整数


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 vector <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:vector <string>
Returns:double
Method signature:double getMaximum(vector <string> profit)
(be sure your method is public)

Limits

    
Time limit (s):2.000
Memory limit (MB):64

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

0)
    
{ "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.
1)
    
{ "061", 
  "602", 
  "120" }

Returns: 0.015228426395939087
You should choose all three rabbits here.
2)
    
{ "0" }

Returns: 0.0
3)
    
{ "013040", 
  "100010", 
  "300060", 
  "000008", 
  "416000", 
  "000800" }

Returns: 0.021996615905245348
4)
    
{ "06390061", 
  "60960062", 
  "39090270", 
  "96900262", 
  "00000212", 
  "00222026", 
  "66761201", 
  "12022610" }

Returns: 0.06871794871794872

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.