Statistics

Problem Statement for "Collision"

Problem Statement

You are working on the backend of a particular system in which you want to assign a unique ID to each client. However, the system is distributed, and there are a number of components, each of which must be able to assign IDs to clients. In other words, you want to have each of the components assign the IDs with as little communication between the components as possible. You have decided that it is more important to keep the system distributed than it is to ensure that all of the clients have unique IDs. Thus, you are considering having each of the components independently assign IDs randomly from a large pool of possible IDs, and synchronizing the assigned IDs at the end of each day. In other words, each component will update its list of available IDs at the end of each day, based on the IDs assigned by all of the components.

Now, there are two ways that you can do this. The first is to have each of the components assign a random ID each time from the list of available IDs obtained at the beginning of each day. In other words, have components without any memory of which IDs they have assigned during the day, which may assign the same ID more than once during the day. The second way to assign the IDs is to have the components each remember which IDs they have assigned, so that no component assigns the same ID more than once. This way, two different components may assign the same ID, but no one component will assign an ID more than once. Now, it turns out that the first system is slightly cheaper to implement, but it will clearly result in more collisions (a collision occurs when the same ID is assigned to multiple clients). So, to help decide which system to implement, you want to run a simulation.

Your task is to simulate both systems and figure out the probability that some ID is assigned to more than one client in both of the systems, and then return the difference in the two probabilities. You will be given an int, ids, which represents the number of IDs in the pool of possible IDs that each component may assign at the beginning of some day (all components draw IDs from the same pool). You will also be given a int[], assignments, each of whose elements represents the number of IDs that some component assigns during the day. You are to return a double representing the difference in the probabilities between the two systems.

Definition

Class:
Collision
Method:
probability
Parameters:
int[], int
Returns:
double
Method signature:
double probability(int[] assignments, int ids)
(be sure your method is public)

Notes

  • Your result need not be precisely the same as the result shown in the examples. As long as your result is within 1e-9 of the result in the example, your submission will be evaluated as correct.
  • If more IDs are assigned than there are total IDs, return 0, since there must be a collision in this case.

Constraints

  • ids will be between 1000 and 2147483647, inclusive.
  • assignments will contain between 2 and 50 elements, inclusive.
  • Each element of assignments will be between 0 and 10,000, inclusive.

Examples

  1. {20,20}

    1000

    Returns: 0.2113618990410422

    The probability that there will be no collision if the components have memory is about 0.6649899283281026. The probability that there will be no collision if the components do not have memory is about 0.45362802928706036.

  2. {123,456}

    123456

    Returns: 0.3769052883184334

  3. {10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000}

    2147483647

    Returns: 0.0069090268185510555

  4. {1005,1005}

    1000

    Returns: 0.0

  5. {6159,4927,6323,2339,7797,9793,6654,5711,5326,3700,945,3340,738,5359,9794,5659,7476,8771,483,6621,2119,6778,7009,3695,7841,8748,9044,2376,5703,1783,4337,9436,9444,9440,57,5176,9658,1417,5417,3909,9897,7066,6760}

    2001034851

    Returns: 1.6742947149701077E-7

  6. {6764,5605,9981,4914,4178,2166,912,8102,5494,926,1552,949,3981,4245,8396,8824,3966,3639,3711,3231,88,1066,2450,3738,4262,2092,3019,1168,7292,4754,3344,795,2733,8359}

    648336135

    Returns: 4.5319887938925983E-7

  7. {4705,2595,9038,1057,7607,3653}

    93207251

    Returns: 0.02036272439195439

  8. {4178,3432,9946,5782,9952,936,6373,5366,8409}

    712190492

    Returns: 0.040864223266969896

  9. {6043,1635,3514,4539,2272,8789,1237,6489,6766,7007,7661,5122,8803,1132,897,6942,5311,5406,1674,2633,9271,9826,7702,4326,8044,2663,7139,4309,595,1216,7553,5929,6752,4217,6811,8280,8971,4482,1262,1441,5804}

    26492068

    Returns: 1.0E-323

  10. {5251,7545,1155,362,9600,5280,184,2520,9142,1859,5457,146,8297,7220,7012,6654,1476,8232,6899,4175,9404,4678,7090,5530,9643,901,9413,5136,2853,5392,4013,6522,6788,5164,1245,7458,8758,9494,7120,776,4243,2098,7273}

    1478022888

    Returns: 1.3172076603021851E-8

  11. {4190,4124,7733,6784,4686,7293,1907,5803,2713,3894}

    546259475

    Returns: 0.03146855424566798

  12. {1486,9189,9190,5483,182,6081,4454,9177,2913,4567,6755,1831,3628,5809,9406,8446,1398,3343,7789,3286,3692,4581,9196,53,7287,7670,9960,1429,2741,9552,5807,4681,9330,2358,8296,2021,1701,3891,3141,8599,6445,7769}

    263222947

    Returns: 4.355798682508344E-41

  13. {1604,6387,4078,4456,5303,5541,4112,1226,7750,3557,3381,8076,2186,6920,9716,9864,174,1200,371,6316,4753,6556,775,9873,3042,3949,8318,52,2061,9214,1332,3667,8938,2667,7714,5979,1604,6499,1450,8655,3491,8210,8427}

    661346148

    Returns: 7.48702282050674E-15

  14. {4763,7251,3664,7171,1216,9181,7850,3793,4246,4473,8821,575,4352,3523,2582,4430,5295,6786,1840,8753,9203,1273,6267,4219,2332,8523,82,7360,6680,3830,2639,4201,1022,3436,7848,9780,8447,3627,2280,280,3042}

    100509008

    Returns: 7.446304268220031E-82

  15. {1728,4743,8320,5063,2372,7912,8720,9545,5440,1636,6621,2461,235,6352,8884,7352,4000,5313}

    1042131609

    Returns: 0.004161651048922545

  16. {8886,4672,4156,9893}

    619616732

    Returns: 0.10289661515891646

  17. {5620,4026,2148,8061,7215,4013,5455,6041,1982,2188,3958,3545,1307}

    1536252695

    Returns: 0.03629740668400133

  18. {7152,8378,7527,8110,5015,863,4397,3694,8284,7101,7141,4124,4648}

    1077793641

    Returns: 0.01780355422016508

  19. {3353,1962,3177,454,4746,2376,9314,9416}

    1462371693

    Returns: 0.05381918611811942

  20. {5259,3177,759,7812,6469,9433,9563,3907,9715,7977,2850,9192,371,3016,9872,45,623,2881,5299,2592,6375,4138,2791,5444}

    1239106987

    Returns: 0.0012482103352535199

  21. {6214,7865,5404,9912,3124,1399,8686,1462,325,8390,734,6272,3504,1637,7136,9192,6671,5791,6983,1925,9777,8023,3500,7789,1657,894,7045,3750,4541,811,4588,9844,7720,9027,6080,1921,8394,2623,2494,4161,2136,4491,1237}

    1103941371

    Returns: 7.352275429399718E-10

  22. {1242,5176,6533,657,5498,7208,1151,5200,7847,5248,6526,9369,9132,8753,1841,276,7822,9484}

    992974713

    Returns: 0.0031318879046331894

  23. {5056,1442,497,1131,7226,7382,5759,6380,9024,6883,6713,9683,5841,582,5119,7874,1944,1049,2946,692,194,5493,8123,7593,7175,1127,1415,207,2742,2825,8213,5826,2141,8167}

    1320413318

    Returns: 5.5565468798867416E-5

  24. {1000,0}

    1000

    Returns: 1.0

  25. {0,1000,0}

    1000

    Returns: 1.0

  26. {76,2365,619,7952,5927,5576,1518,3695,5695,3018,6347,7131,9158,8307,9411,2963,9846,7919,4934,3925,922,5202,2592,805,6004,5352,4649,9895,2113,7000,228,9120,8735,4301,9483,3524,3091,8033,2324,8560,7755,7357,8494,8605,367,7024,2716,477,5623}

    1800590576

    Returns: 7.2315474224492E-9

  27. {5327,5379,5677}

    2142347951

    Returns: 0.01983142691110551

  28. {2805,3781,4189,3104,6815,3357,4177,7478,5734,7931,1117,6243,7048,2469,6843,8853,7810,3372,3299,6565,6450,9320,8701,2026,9457,7743,4315,5866,6821,9276,500,8138,3052,855,2855,4005,9741,884,7057}

    131074508

    Returns: 1.6026710430488814E-71

  29. {978,3193,7108,8196,9031,1464,3308,103,5072,7675,8039,5001,460,2112,8871,8520}

    882200381

    Returns: 0.010598777106219266

  30. {6697,3965,696,5790,1058,3278,4083,1597,9308,6593,9281,5806,3933,662,3452,4489,1178,1670,1429,6181,3715,6710,1658,402,4922,9204,9438,7945,4813,2166,1564,7188,2652,8241,2709,5549,541}

    1473489999

    Returns: 6.3073598601672E-5

  31. {4694,40}

    1673664295

    Returns: 0.0065591770691942886

  32. {4876,7509,1992,3570,9511,7072,2376,6060,1297,7702,9804,2004,8,677,5791,3745,2756,7085,3145,9922,6103,3805,999,9335,2951,7131,3893,9491,1979,6747,5561,1559,4990,2281,3039,8535,4266,7484,5939,451,1752,1761,1854,3231,7787}

    490102786

    Returns: 9.105903246144105E-20

  33. {8209,4881,4076,1036,3599,7236,1549,5745,8316,8993,430,7361,6184,2366,1966,167,6373,2922,4870,7385,776,3049,2240,815,3628,2444,3894,4662,7339,3975,482,5856,4998,9142,2227,6390,2909,2499,8458,6584,6758,3397,4545,3664,7340,3443,7435,9777}

    1703734335

    Returns: 2.4297451455613994E-7

  34. {2622,831,4732,9890,1574,3084,3626,87,7080}

    599526190

    Returns: 0.07225244133164788

  35. {6934,3423,959,9848,2116,4378,9244,1932,4549,7762,7675,7140,7126,8844,9737,3505,6697,7482,9469,8143,8188,284,4883,2613,8572,2718,1024,4779,8231,5004,568,8717,865,1545,6648,7285,3485,2956,9419}

    26371654

    Returns: 1.5E-323

  36. {4747,6455,9725,8511,2314,470,1479,5263,9312,4318,3564,2851,6022,9533,9345,7327,3493,4826,3239,8811,10000,1279,1272,3302,9087,9713,5327,6063,6498,3641,8456,8110,997,4628,8873,7765,7862,4333,1994,9762,9484,9026,1381}

    1482063249

    Returns: 5.569583738729275E-10

  37. {9513,9730,5610,7052,3933,6565,5776,1367,3208,7568,5736,4188,4262,9171,9753}

    99406833

    Returns: 2.431978647199953E-18

  38. {3672,9858,8401,2926,70,2665,4220,6137,6693,9899,6183}

    2129919893

    Returns: 0.04505850518454285

  39. {6726,8292,6626,8598}

    390982122

    Returns: 0.10713601673246642

  40. {4613,6167,654,8570,3551,968,2655,1507,6839,6798}

    551055680

    Returns: 0.04990331281020635

  41. {6615,4659,5494,328,7948,5173,734,2695,4963,4291}

    1666758571

    Returns: 0.0423290951956492

  42. {3374,6168,1865,1623,143}

    1339141032

    Returns: 0.019642002678472603

  43. {8490,7906,294,9402,8624,1307,8431,4800,8287,241,8981,889,9548,3766,3101,6017,9328,4143,4340,3401,5848,4929,934,98,4591,9314,7240,581,3938,2989,9413,479,3871,4272,6916,5494,9437}

    1666850060

    Returns: 8.29106748783453E-6

  44. {5709,189,8341,9818,3217,8357,8422,8187,894,3064,6504,3449,4493,7475,7578,8655,8182,2222,5964,5220,9676,3351,8439,6196}

    45520082

    Returns: 3.0157541307402146E-94

  45. {9692,9024,5107,3824,9282,8752,9765,7065,8817,6579,5941,2741,3598,3965,4095,5714,5167,7414,990,6979,9564,9894,3220,4983,1060,2364,1345,7636,5846,1372,3299,5442,9552,5229,3428,5154,6139,7996,9207,7406,1989,3310,4470}

    1970839819

    Returns: 1.4088734157041954E-7

  46. {932,4683,832,717,46,4313,6117,1664,2575,1216,3034,260,287,5855,7392,3649,1068,7537,195,1819,110,8445,7981,7390,9434,2924,1647,3545,6697,3897,4073,6123,9533,9466,7510,7091,4158,8750,6609,6618,1240,632,3043,369,1059,6939,2643,2472}

    1576181551

    Returns: 2.8756517242764293E-6

  47. {7401,6922,1439,9113,1678,4219,4273,9340,7694,4440,1656,5641,7256,8670,4368,4811}

    1314784005

    Returns: 0.012609353402262748

  48. {9565,2293,418,1815,890,4691,1291,2678,5488,8005,5402,5231,924,8199,86,163,1764,7759,6627,997,9088,4872,8232,4404,7038,5569,488,2030,6003,4545,4981,8265,5352,8146,8439,8077,1499,1896,7477,3875,9300,2453,6734,2215,6849,3603}

    1831553524

    Returns: 1.4123450659142064E-6

  49. {8243,6860,4456,9630,4069,2683,2713,3996,8317,3248,5544,7581,7790,7598,5612,5964,8187,4312,8621,2499,7100,5709,5514,9228,4635,9901,2529,7502,4752,1449,4359,5805,5457,1137,68,1670,6596,4056,4655,7808,8515,4837}

    9915357

    Returns: 0.0

  50. {8141,4671,4500,30,3798,7891,8193,9831,4752,6467}

    1894853033

    Returns: 0.047015506709428

  51. {8868,1399,753,7894,3941,8081,945,2902,9720,4035,3902,4047,7030,6522,9800,4349,7494,4655,1332,3982,3498,5745,238,9753,7464,2344,2571,4098,5929,8435,4008,6142,1474,1366,6892,7793,2755,7890,8581,4896}

    2039186151

    Returns: 1.5137612495283822E-5

  52. {4096,3343,3355,7873,6633,3561,7816,9595,1539,2446,4301,3652,8033,5646,5790}

    565277785

    Returns: 0.002550237935048062

  53. {2294,2889,4493,7973,4336,3619,5266,9807,5519,8746,9878,7303,4051,4048,2772,6743,7210,9135,2878,8844,1799,2502,1938,5144,7437,9503,5750,8714,7674,8574,3713,8294,765,194,8116,7723,5587,7951,9681,8440}

    1851179508

    Returns: 1.4585517653303326E-7

  54. {105,3588}

    61087485

    Returns: 0.09945038753563973

  55. {1546,7920,3265,297,2079,8783,6098,730,5300,9401,8999,7601,7639,5833,7239,600,7908,3852,2283,2017,823,9272,6016,8955,1383,876,9075,6456,2560,1010,4417,1298,9994,7321,4038,9562,6822,3144,2379,4050,9752,4487,1481,5931,2535}

    175010096

    Returns: 1.449336079370823E-60

  56. {9489,2189,6536,6900,3509,1250,354,3995,6752,6345,443,9638,3523,534,6673,910,7372,3155,431,4793,2143,4192,1802,500}

    1697061239

    Returns: 0.013841645461371607

  57. {5757,5524,1085,9447,6870,5672,9653,3536,8666,1331,9325,4578,4374,3691,8226,4791,5236,2537,5329,4254,9733,1110,3055,2503,5553,7404,2329,8202,5351,7851,8465,2272,1184,6577,6506,7003,3740,1385,9376,2778,3489}

    548348240

    Returns: 9.781897757519474E-19

  58. {5155,2438,5464,7265,514,1743,2536,9184,8723,3821,2444,8856,1408,2597,8478,4573,7351,1478,1146,1246,5810,7467,3338,5524,3648,5980,3319,8308,1181,3102,3102,9634,6542,5004,1413,3138,2715,7003,4517}

    1306584137

    Returns: 3.0902245521707565E-6

  59. {5877,7612,8985,2548,9176,3234,2225,8727,2493,2969,2878,137,5927,3511,7259,8371,3145,7862,4546,5123,2263}

    2011081423

    Returns: 0.011822509607281317

  60. {2589,9141,2390,1503,2381,7300,3268,9153,1486,1040,2694,6027,3069,8177,397,2938,7108,4637,5712,9252,8319,308,6244,1195,757,3357,3791,5967,2524,8770,6174,8887,7800,1098,6623,1387,898,1085,3656,2947,7904,4238,5490,923,9530,765,9612}

    740538118

    Returns: 1.5420067388032892E-13

  61. {3143,1342,6552,8620,2218,9728,4625,8338,2458,5263,9472,3832,3751}

    621924753

    Returns: 0.009655489219899022

  62. {5780,6655,3339,1289,5667,8141,8880,1313,6788,9698,2850,3486,2755,1660}

    531247220

    Returns: 0.006360025917363418

  63. {4065,4777,5048,2179,3838,1689,6556,2293,7857,6961,4567,4774,2606,5571,4828,9471,4534,6751,5552,4759}

    1446901450

    Returns: 0.00737466897296387

  64. {3416,3365,5520,2848,7177,8218,5709,5521,9861,9192,1335,3670,2835,8360,1961,4316,720,8615,3562,9051}

    1386811712

    Returns: 0.005377516849784079

  65. {654,7964,9168,6678,7675,6614,1372,8353,8710,2847,2178,2113,521,7987,9754,378,1571,3446,4082,5031,7279,9242,9194,8300,6730,9204,499,9942,1848,9989,3621,5252,1694,5026,611,3853,3574,5541,2324,9060,3100,7879,8407,5258,5962,6166}

    914765701

    Returns: 5.8248812641808254E-15

  66. {6694,4908,5035,7053,9728,8492,9286,9339,3067,7791,8373,8611,770,2045,7942,1844,1721,7195,7165,6694,7182,9105,3133}

    282736609

    Returns: 1.0008144397685054E-15

  67. {5484,201,5270,526}

    1651265755

    Returns: 0.0170694914269377

  68. {4959,4057,4396,1187,5605,4889,1466,630,3250,8879,6729,6540,2143,6701,6667,835,8099,1139,1920,1113,5444,8414,8782,4500,8842,1352,9056,3639,1082,6114,5778,2818,1544}

    356631501

    Returns: 9.500548959676105E-14

  69. {7936,7672,8990,4321,4208,7866,930,1928,50,6681,9378,1182,756,1594,2810,734,4029,3499,9197,7228,4882,3607,506,1551,5320,9569}

    1672988280

    Returns: 0.00454005817341737

  70. {4395,4180,610,4140,3696,3684,2601,3577,7446,9558,4486,7631,9581,9092,1048,9413,7768,4615,2083,8933,3152,9883,716,5612,1672,4233,5395,294,9419,3246,9559,8819,546,8980,5164,7214,5955,2976}

    734636525

    Returns: 1.6734781411596556E-12

  71. {5830,1687,8917,3206,6145,8224,8350,9966,5737,9546,9779,5391,2117,7117,6094,1532,7926,2483,3103,274,5573,2030,3094,1768,285,4901,2426,4020,3694,3314,7630,5059,860,2555,2395,7421,998,1215,7572,8105,1232,96,7054}

    618321460

    Returns: 4.5872453090308675E-14

  72. {7600,6853,6795,4483,9132,4044,1671,5843,8168,6614,3611,8671,363,7926,4328,1451,5904,832,1699,5271,8898,9680,1893,3118,3570,7599,2755,7471,7746,246,3303,6571,3987,4177,432,6796,2627,3383,3311,521}

    934777533

    Returns: 4.221972375571384E-9

  73. {6480,3208,7603,2907,4353}

    1158728772

    Returns: 0.047115405628814444

  74. {3430,8999,580,2063,7380,5059,9275,6610,1150,7035,3900,5265,4868,6678,6050,8285,9515,1062,2523,5269,875,6577,6146,510,6081,9944,3356,2863,3802,6557,6990,441,7135,1610,1109,7755,924,592,5345,765,3100,1216,3565,1396,511,9132}

    1126648188

    Returns: 8.430440993226299E-9

  75. {6075,1871,3306,7619,4953,6484,3629,3236,6189,1865,9916,7894,7029,2895,3740,7876,7777,6216,3351,2935,6985,4067,26,503,1961,5495,7315,4256,7531,4963,4417,9628,9020,3235,6454}

    372048259

    Returns: 3.206023415786296E-19

  76. {2538,6625,6183,944,1200,1440,149,2489,769,7585,4403,5681,6172,4918,2809,5224,153,5225,2383,4981,6021,6569,476,7489,2374,6741,1192,4493}

    885417547

    Returns: 5.779780593337001E-4

  77. {7037,9351,4127,7799,4453,2837,4222,3491,1056,4045,1046,1150,8678,1824,6848,3447,658,3337,6975,8073,8282,7767,8584,4291,128,6157,310,3791}

    856063004

    Returns: 3.3322196557609616E-5

  78. {8792,7561,5712,377,7060,6428,411,4366,3776,585,5434,8406,1249,9644,461,2067,9360,4008,6653,1711,3449,1480,1467,3998,961,205,43,6258,3369,335,5153,8402,5628,543,5425,6115,8958,2827,875,5494,5998,3445}

    2083351236

    Returns: 2.0031215826711308E-4

  79. {6487,1548,3834,989,2830,775,2774,5402,3499,8762,9198,5065,9676,6092,8102,3848,8168,1445,6184,171,370,7250,495,5730,7952,9484,9137,5313,9541,3247,9174}

    1924320963

    Returns: 3.6695288857780837E-4

  80. {7221,9238,5661,1806,7213,5626,6015,7854,7879}

    1978615937

    Returns: 0.04670637265629396

  81. {1889,9921,5330,617,2101,6822,7199,9904,6873,6102,7854,2885,229,2568,4616,6711,3065,7654}

    1028192544

    Returns: 0.005639669198999227

  82. {4424,4963,8833,1186,9763,4044,3197,7384,1638,9761,4077,3358,7685,5760,9271,8251,2479,6295,563,10,3157,6214,8595,8358,8733,4448,9808,4662,5245,6289,8016,8075,8627,4717,6090,2149,205,4368,1681,1442,6032,1628,9626,6128}

    255528059

    Returns: 3.509276248153178E-47

  83. {5150,7347,1288,1547,2154,5872,7626,1622,1625,580,6383,1195,1616,3209,1949,9074,1011,4591,2538,4125,4372,933,3856,2243,9466,5440,8155,5767,4575,8317}

    476478329

    Returns: 1.2288835852422687E-7

  84. {4787,9180,2782,8218,9371,8812,3685,2991,1516,2900,3415,6491,4008,6364,5932,4013,8043,4046,8929,836}

    94332340

    Returns: 3.806382132950033E-25

  85. {6908,7190,8708,5320,261,3854,8143,373,4754,4250}

    1298754805

    Returns: 0.05146732161538253

  86. {9276,9500,3680,7377}

    1205102984

    Returns: 0.07371629272213931

  87. {4827,6422,5236,9402,1064,2176,4397,9924,8269,4685,8524,6099,4438,6917,548,4125,4759,9658,1877,3712,1704,7553,4265,8534,3536,2347,7337,4000,835,5643,6429,1769,2782,7024,6935,6640,6554}

    1523905869

    Returns: 3.1694829295278804E-6

  88. {187,58,44,8119,3098,3486,2439,6897,172,8885,7927,1910,4615,5822,1799,8159,8930,4711,2471,2042,9097,4379,3093,9971,5566,1162,4673,7250,6256,3954,8362,2431,4333,8756,643,1035,3661,4628,1473,8599,2048,7164,6079}

    1582284471

    Returns: 2.5208397166100443E-6

  89. {4426,9495,1043,7427,6347,7501,7284,2760,6415,258,366,1012,5504,8167,2157,1349,606,9469,2562,560,4580,9120,9596,2058,7013,67,2767,8093,2275,9136,6841,83,120,4165,449,5904,523,7147,6235,1250,7446,1821,7194,9853,971,2048,7418,374,9434}

    528550719

    Returns: 7.223438557980127E-20

  90. {980,9492,7148,2443,2842,8156,3969,6642,5853,8732,8247,3527,4409,5172}

    820927566

    Returns: 0.009496365648532852

  91. {2816,6311,2941,9066,8183,7618,9564,7982,9850,9642,8326,8871,233,6888,7638,6390,8966,5648,7943,4462,5325,9351,8210,6097,9127,3131,6767,2632}

    1527425665

    Returns: 4.54857107625638E-6

  92. {639,2032,6872,9199,9704,8145,5982,9101,1229,8441,8808,5714,8275,2478,361,3737,2670,5973,7773,7013,2852,8164,3854,9954,2787,3917,4620,4162,5317,5225,1172,9154}

    1223998057

    Returns: 2.299183746985235E-6

  93. {3254,9047,2933,6528,6049,5634,3006,8328,19,2315,9074,3694,903,8555,7037,2274,1887,9958,7091,9915,8934,5571,1644,923,6683,8702,6169,1389,2806,6079,214}

    1980319467

    Returns: 6.481984982542395E-4

  94. {1803,2282,6082,5120,3224,5777,2288,7367,6724,5922,906,5418,2968,5639,3063,3959,9965,9563,3312,388,7567,4802,400,4900,4436,915,7080,9881,5167,9747,9046}

    552066262

    Returns: 4.464841215538802E-10

  95. {4191,6743,5740,6138,4986,1719,5082,6407,5753,2796,4432,6371,8162,2307,7688,4368,8294,7120,8646,6175,4573,1839,4655,9645,6395,1837,3353,8277,7735,1283,3002,2585,9807,2167,1557,3457,736,5930,8533,3768,5348,9787,1069,9958,9355,811,3067}

    1637238071

    Returns: 8.506596908965146E-9

  96. {6026,2383,1704,4931,7982,7813,5987,9295,3495,4248,7376,175,62,9957,2190,4230,9475,2708,6916,9651,3528,5062,2199,1044,7238,1066,6188,5062,1243,7870,7842,470,5173,1331,6108}

    423690775

    Returns: 9.176437939810718E-15

  97. {7743,5504,9295,1886,6617,6051,5752,29,4412,8770,3994,9190,5732,1450,8825,9590,8004,8978,402,2443,2404,2676,2804,5243,5224,9300,5246,8020,8688,5881,164,2102,2299,2489}

    1600119438

    Returns: 2.5551916210655406E-5

  98. {9526,2958,1990,2111,6004,378,9681,7908,3575,3506,5066,4121,7532,6240,3593,3676,9629,6122,8897,596,5855,1694,5735,7174,1924,5324,5413,4156,8709,5263,9074,5483,7407,8730,2252,7497,7436,1422,3241,1169}

    721613572

    Returns: 1.495323246802401E-13

  99. {4075,4149,3586,6342,1065,854,2096,8794,2557,8347,8576,2417,3765,8849,4286,6819,342,5232,5605,649,9330,9299,6200,5111,2050,8490,7158,1555,1543,4732,8459,5600,2461,4955,7801,2057,1718,3382,5532,9870}

    1514512239

    Returns: 1.6888258800697977E-6

  100. {545,6001,7731}

    769996632

    Returns: 0.05638657078075893

  101. { 2, 3, 4, 5, 6 }

    200003

    Returns: 1.7484781342147482E-4

  102. { 44, 5, 34, 22 }

    334456

    Returns: 0.005155411696098566

  103. { 1, 5, 10, 20, 30 }

    1000

    Returns: 0.10988899792940177

  104. { 1, 5, 10, 25, 30 }

    1000

    Returns: 0.09559303910556256

  105. { 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    2147483647

    Returns: 1.1173770699525203E-24

  106. { 999, 1 }

    1000

    Returns: 0.0010

  107. { 0, 1000 }

    1000

    Returns: 1.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)2024, TopCoder, Inc. All rights reserved.
This problem was used for: