Statistics

Problem Statement for "TestProctoring"

Problem Statement

This problem has a non-standard time limit: 4 seconds.

Bob is a teacher proctoring a test for his students. All students are taking the test simultaneously.

Every second, student i has probability p[i]/q[i] of finishing the test and leaving the classroom. (The process is discrete, i.e., for each student the time spent taking the test is always an integer.)

Bob must stay in the room until all students have completed the test. Bob would like to know the expected amount of time he needs to stay.

Definition

Class:
TestProctoring
Method:
expectedTime
Parameters:
int[], int[]
Returns:
double
Method signature:
double expectedTime(int[] p, int[] q)
(be sure your method is public)

Notes

  • Your answer will be accepted if it has absolute or relative error at most 1e-6.

Constraints

  • p will contain between 1 and 20 elements, inclusive.
  • q will have the same length as p.
  • Each element of q will be between 1 and 10^9, inclusive.
  • The i-th element of p will be between 1 and q[i], inclusive.

Examples

  1. {2}

    {4}

    Returns: 2.0

    There is a single student. The student has probability 1/2 of finishing the test each second. The expected time Bob waits is 2.

  2. {1,2}

    {2,4}

    Returns: 2.6666666666666665

    There are two students, each with probability 1/2 of finishing. In this case, Bob must wait a bit longer - it is quite likely that at least one of the two students will take more than 2 seconds.

  3. {3,1,2,4,2,5}

    {3,1,2,4,2,5}

    Returns: 1.0

    Every student will finish the test in the first second.

  4. {1,1,1,1,1,1,1,1}

    {1,2,3,4,5,6,7,8}

    Returns: 13.604834665120991

  5. {2,3,5,7,11,13,17}

    {3,5,7,11,13,17,19}

    Returns: 2.6299445065924276

  6. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {1000000000,1000000000,1000000000,1000000000,1000000000, 1000000000,1000000000,1000000000,1000000000,1000000000, 1000000000,1000000000,1000000000,1000000000,1000000000, 1000000000,1000000000,1000000000,1000000000,1000000000}

    Returns: 3.597740924491638E9

  7. {12962238,16689192,16955465,17055163}

    {33970619,43671343,59726026,36056910}

    Returns: 5.163749559672052

  8. {7860008,29325852,9950828,1652013,54855512,17138443,651208,6370327,67751791,25486502,24332883,2540410,2975805,50234985}

    {23519728,45477787,29621074,10615569,56795047,42459653,63157553,45574873,97795477,43960788,48061048,20837073,20490952,58833708}

    Returns: 98.24187705360741

  9. {9379425,10482994,9196320,25072796,4915471,71987697,52457658,69572832,21030034,46356008,42908158}

    {33278886,34163800,27444260,83332181,5894750,80188592,57546406,70353235,41854911,93325935,81245177}

    Returns: 6.510538091727476

  10. {11858780,5233643,24018705,49414111,16319412,27898578,23466332}

    {14787765,36628514,28976812,51795294,47654749,36354296,85456558}

    Returns: 8.426407053663535

  11. {7427948,856913,12961903,3846224,74826416,50035324,6587434,29194242,841672,48763729,7263438,41955610,6359664,20211663,55064506,20710812}

    {88270926,5451450,19963537,33153283,80708108,73022550,20834369,77052005,15372367,55166033,72080336,92085862,10788779,62581644,58753808,38486040}

    Returns: 26.423881722956338

  12. {55542070,7310649,51052,18744233,6644482,19391843}

    {61764238,73953395,88117,24142843,41657994,71117030}

    Returns: 12.706114492734548

  13. {19628753,62248409,7648830,17565356,291676,55443498,51078353,58468375,38714380,32311994,7693500,57633,16587055,65975406,14500120,43384494,56553618}

    {43622230,89749206,8013872,18319894,84387096,72686013,51679150,84993232,66188515,38670253,51085595,45660990,39067974,77577979,70812180,91954382,82830995}

    Returns: 869.4686296815537

  14. {7730171,204280,11320748,2373846,32361855,51847,25872396,58847126,14440446,23739140,25420435,28131531,65528293,241229,42380872,86847974,51562313,27477166,53327695,41672224}

    {51785320,2726262,38190528,62508547,50619996,11164138,96746395,95319125,94435067,87904840,53540901,90437991,66674787,3286796,50532107,98337815,87676375,44591417,67597061,43952116}

    Returns: 218.89993078779776

  15. {11136082,4665654,69656943,35805436,41060450}

    {34971511,17438350,81695471,36457930,68986189}

    Returns: 5.026387146583733

  16. {18355262,31693555,5790671,60307638,843206,51739113,3449520,13781896,33330015,4197828,15562574,20818503,84539951,711191}

    {54039072,44094254,22049851,87998292,4091888,95413896,19979080,33568855,77567692,26514329,36264137,30841044,86414604,2358203}

    Returns: 11.016728929190249

  17. {6094937,9476464,69218582,82006958,5997804,6133981,64710223,30269068,56035561,13507833,87828829,45229648,791439,17357038}

    {9182940,20112242,70313984,90544712,81636185,87861939,73955930,70187127,75588538,40291280,96130999,52794503,2591278,78611889}

    Returns: 21.233820828880162

  18. {16618189,4989498,46275263,253572,20011386,24789306,22674444,34959240}

    {34343769,26325555,90635048,1646759,59400826,52747854,65872191,44121216}

    Returns: 9.398047397261546

  19. {58304529,952131,606832,3418251,29429367,64245372,49518800,28104909,21556442,41736849,486038,3827149,25633332,30700534,13869816,70302698,2559651,11036225,33202938}

    {81553073,64749673,8754495,4657413,68900968,84789066,77139078,41138216,77597926,67914661,7536154,6306385,27739272,42382757,98625933,98529285,7791313,24386137,96610238}

    Returns: 72.62247754150418

  20. {36979266,10744904,4299783,2965494,728078,23867425,27471287,68407240,1592928,26871227,79912919,14776211,66284043,78837679,4707465,966813,20918934}

    {40617668,17763327,28807717,17625645,1378505,63273827,81222918,91885902,5708672,83901231,97744773,81821659,91226220,86836030,18416110,1618258,98562675}

    Returns: 12.334370886647957

  21. {62682880,16425504,34661684}

    {70105676,21333315,45448764}

    Returns: 1.6257355326136658

  22. {48498467,2304957,66244828,31735734,2415805,5980381,39999996,19955689,6764962,26157575,3441193,14353651,7639960,31988496,62264291,2238311,8988672,57208174,4349011,12311231}

    {66850189,76844042,76434633,34460957,4307311,56864855,56706919,33607535,68386348,30900535,52750997,19664681,43107811,39839576,67008050,42008340,16467593,76006139,38274413,15419409}

    Returns: 44.6939738652194

  23. {14632784,72870033,10295886,51053009,21413308,12356912,40366208,14125301,13426388,2521070,5763946,35495321,381650,9640503,5985895,1579475,3775596,325674,10980519,22959426}

    {87381358,76579652,82539535,90813943,75259854,51059702,41332243,32858879,90334539,32358462,14566540,54642982,4516658,81241489,9587380,76248159,13137779,1140124,46858303,34645664}

    Returns: 53.536813128136345

  24. {20245432,3650499,12613913,1758058,1697395,4696641,544608,6739994,9752257,4880342,31327482,2963846,21068256,3203990,5659176,42190995,26604497,13032338,2251194,50784964}

    {56377532,3851200,26993690,84463609,96790722,5218994,12489727,95986579,32237940,9536510,76629242,7103830,86114024,16120917,16869275,70167797,48313157,15115550,7186504,79988852}

    Returns: 82.59782534365704

  25. {32082188,35275370,1127039,52079313,29701997,7420738,78299483,2263681,4628043,42197778,23346995,38721095,6487946,19702266,4941078,70707182,17702642,2700812,2956619,33978214}

    {48426402,82941566,22528874,61251721,43643024,55848338,81722305,34379489,20446285,43917690,60360641,96806590,24934327,27266933,10613683,75710691,45097652,26169215,56827953,56323335}

    Returns: 34.47431933111946

  26. {12001170,39885924,10555156,14394089,20225103,39744528,6617297,6697043,42071969,34832495,2683229,12323170,24832599,62568297,41995873,7371113,4080044,18871510,17841484,56342210}

    {20227704,73753951,17031324,39821315,21373301,40443317,10168151,8043369,83285674,45102247,5392795,15537441,79351041,81000273,58484743,8790626,91460803,22327384,20571634,99975971}

    Returns: 22.97425482643627

  27. {69,60,13,25,45,61,25,34,65,96,69,45,32,82,58,26,70,30,69,62}

    {93508364,67073802,69264366,99324263,33603103,77812383,4900440,38603205,92824695,75809741,74674436,29651260,13093224,40883988,53750820,23719056,22537351,60612114,88398960,89203542}

    Returns: 7741106.694528625

  28. {35,44,36,48,35,1,23,6,71,76,66,100,8,58,48}

    {76182551,87903098,74465666,4082208,23643681,74960533,72223586,84687618,51589615,63865646,39187783,85881256,47890396,80440612,65506023}

    Returns: 7.74643697798861E7

  29. {26,7,35,5,30}

    {20940343,41620805,79223711,9028325,738261}

    Returns: 6871080.656138144

  30. {77,78,87,13,98,49,35,73,62,35,70}

    {9268755,50858730,96461925,46461613,32011337,41002917,85818840,79921586,25643208,73145431,89349209}

    Returns: 5348446.642216014

  31. {2,73,7,7,32,28,88,98}

    {71097779,95713373,49644895,194176,21785289,75025083,90797819,88397040}

    Returns: 3.683037603832535E7

  32. {61,25,21,34,15,9,27,19,20,96,34,10,47,3,68}

    {32320843,17419380,2141817,63589302,6199451,264520,50339833,80030136,28023613,43812105,55467420,19125791,96266340,94068114,32519552}

    Returns: 3.2071791231756035E7

  33. {92,6,30,93,10}

    {82699489,44139414,32162899,30032677,6101101}

    Returns: 7582376.899664334

  34. {100,4,17,88,88,87,86,71,30,48}

    {84858716,76409183,95678496,61781040,13740422,89501505,13315732,59832871,63075595,22819682}

    Returns: 2.04989016991405E7

  35. {29,10,61,54,14,8,85,83,75,100,79,74,88,44,36,44,92,2,84,50}

    {9811702,94434974,8369661,36295625,4368934,97701253,4042086,24364307,71185381,45804584,44345172,33016629,69125426,35145363,28004760,79364823,20070784,83487055,28724111,61785099}

    Returns: 4.565708670261321E7

  36. {2,5,47,22,64,65}

    {52343208,30856263,61546214,71909079,31107266,42016392}

    Returns: 2.7563584421570197E7

  37. {10,84,42,31,42,21,65,17,50,15,62,22,7,19,1,82,67,47,88}

    {37898153,69273177,31734295,69497501,41253160,19890626,90276278,72314562,50280311,12975082,99212775,16374703,18498716,27100499,80499666,53983417,97143283,49935431,84524061}

    Returns: 8.091298646013911E7

  38. {48,2,8,12,65,75,56,60,58,82,76,80}

    {73630075,32930109,34913716,40278781,57371715,61013438,56429895,42483410,92972124,39171052,90580397,71388295}

    Returns: 1.7852531913333144E7

  39. {63,55,89,82}

    {95600075,23430755,99559312,46572808}

    Returns: 2102806.6003754605

  40. {17,74,25,8,50,63,51,54,47,61,45,93,69,41,25,23,77,29,40,71}

    {68966080,43362736,16710384,59620458,25281816,49560604,61746266,23716064,68466266,46832382,36156809,71835755,45076744,63623916,274265,93139457,6043411,84236015,34611686,38523418}

    Returns: 1.034577281640107E7

  41. {47,96,19,89,30,29,85,82,46,35,69}

    {31310906,79687659,30694519,97431935,11123637,98702365,88959822,29820775,70668428,28747202,71894209}

    Returns: 4605853.730896776

  42. {74,97,93,8,68,98,4,34,85,53,21,71,95,70,83,91,34,93,25,29}

    {21468414,85902182,19823628,97281621,28128376,76252753,70427568,96991129,69297932,49911775,30239592,53891909,67494230,41763781,80020860,7349742,55598631,54362400,40889265,80168557}

    Returns: 2.2851036106095653E7

  43. {61,52,77,64,37,93,5,62,42,57,99,79,86,92,51,27,60,57,85,33}

    {85285805,23237702,9657441,41922344,1781971,48013668,64245271,53550312,71889803,2300305,95304596,88056406,85243258,54094214,89616187,25370737,50972604,96623270,24282570,36735388}

    Returns: 1.3480988177258126E7

  44. {73,40,84,22,76,50,91,65,98,98,17,48,26,75,100,92,93,63,39,92}

    {12164070,78350955,15072974,47034931,91094107,90904460,88067420,83028157,2074417,98381505,92777105,79261945,39617381,96772258,86914623,2357199,90449949,35741692,83301442,18607100}

    Returns: 7321086.413050351

  45. {17,81,100,17,54,42,46,65,37,55,45,4,91,19,92,18,4,57,40,17}

    {47343272,71413711,35324666,32715342,1341992,77746975,20714339,79402589,50903997,86621072,29481377,27151779,97893783,73668229,3006423,27786135,12466070,80936670,29644820,31065197}

    Returns: 9654371.908453258

  46. {70,56,6,33,58,26,30,72,90,31,65,51,26,89,51,67,37,58,93,65}

    {70217028,34603455,69145624,18530376,84981458,39740282,78210772,49337479,65483893,54200576,35808903,71476328,4036733,19640135,61638310,80977279,69637624,88014857,14052912,44735061}

    Returns: 1.255359066321387E7

  47. {845830,99,8572,9984,726671,6767,1677}

    {43593622,25988740,76980280,74657182,52604661,49496246,64075997}

    Returns: 267559.8923058817

  48. {9143,7,64520,60898,72967,3570,10,225206,31,3687,8,113654,875,8,4872,66939,6,957042,96995}

    {90636295,73356372,37897893,81657065,83978610,79406301,10620207,17460658,35718215,53547037,44434365,72121962,65954400,81578943,36998360,63115087,97481518,94436248,69303186}

    Returns: 2.3523077397655E7

  49. {4,29,500,9552,1,709,577216,6402,92283,99648,54,87,200,961597,827403,386080,513634,1222,154,85390}

    {83592704,8670199,44378856,48806261,84490424,67835233,19651912,64041773,47766789,36978753,96652620,34189722,3952379,31722010,53592828,23488951,23800760,71465660,23362008,95891375}

    Returns: 8.864007176516147E7

  50. {408,895681,1,933150,46,897511,5,694,8,348,256593,3281}

    {72995450,3567746,56763252,15968654,20005205,99772966,14809536,39247665,88599936,56861990,91539319,51764054}

    Returns: 5.86258758561904E7

  51. {1099,95017,84538,675}

    {56419567,55914404,82650038,15289036}

    Returns: 58272.84436572762

  52. {5,889,58,40536,62710,10}

    {13565388,44660032,12427605,21394223,40729677,15302000}

    Returns: 3268426.9569463925

  53. {323,952,53,13,477,183020}

    {64435700,90316228,85536611,36545651,30019446,22084193}

    Returns: 3402755.782990201

  54. {554640,5,17845,5,279,63,23,77,37,511}

    {18005046,77698739,92752977,38650286,28175313,36195326,62444742,29300594,74460098,71624401}

    Returns: 1.8345182506491993E7

  55. {886,58,93512,54}

    {53599910,31612344,53663336,71233341}

    Returns: 1478986.5749014583

  56. {8,2,3,10,10}

    {4970898,46047124,69584218,39685451,81809703}

    Returns: 3.564729105621607E7

  57. {680015,4,22,2,42084,9,290,9575,715046,2,32,93,403770,41458}

    {11991972,65519727,57310229,45194890,62085700,81846899,83388783,32661435,20012565,13418177,187203,47516425,17138850,26441967}

    Returns: 3.1433997303526655E7

  58. {747604,375141,30,589484,173}

    {13706070,98906291,51127318,7907497,89496172}

    Returns: 1824707.98495889

  59. {62213,869,1,26,5459,5905,412455,2422,8942,2,3284,571,846582,887,5914,1,988,9259}

    {93856014,64765588,13308522,68905899,1299124,81368393,72133552,45034762,75175559,9667083,22402367,23824912,36896031,53219608,11602109,16153446,32054946,42520932}

    Returns: 2.27138625542181E7

  60. {64,6082,54026,26859,110,11,19025,21,40800,836383}

    {51492301,37439923,92473696,49907288,2287453,71086146,97477930,55554141,1152759,42296473}

    Returns: 7266078.904217567

  61. {3,15142,3020,4,1,7011,26295}

    {73095264,72692224,13037431,98862740,88422026,49697529,69887875}

    Returns: 9.758977103873704E7

  62. {7713,10,41119,6,556,43,294,598,55,8013,28929,581,817,51,744658,417,799110,79,67,86}

    {97591882,2467497,23830905,10460550,97347246,65957948,38252988,23620864,17239662,62164568,62724814,13357393,2730570,68443551,27212894,60737474,88152611,43398420,23048363,31995602}

    Returns: 2887276.143581312

  63. {643875,1,93255,3,685,4439,9,11862,47,16,527574,596,12,251,656626,51,3180,639,208,561}

    {39029733,73510328,26932228,26091596,97347273,54079749,91263262,13845626,15248699,93792905,8933307,35235073,3577909,87492410,94464182,98980049,88486246,98158107,65032396,91427028}

    Returns: 7.55673100002117E7

  64. {257440,73327,62705,46,670681,7509,622,187674,9,81,2,7159,81779,761652,78,35145,506056,834821,692287,1}

    {52626517,11926235,87757729,50011917,4877888,33965347,92260375,47368853,11905342,70721565,62445235,30193553,6012884,89941437,57333314,95030492,21612554,7729547,40404526,13096538}

    Returns: 3.510913030920912E7

  65. {6335,795,9,984,6,1187,88,515437,92281,1,33736,9305,65,10016,85,921727,380,22540,830,56}

    {73006422,48891905,32498703,12588567,62336343,903385,59465021,18818818,68896732,58168865,83246639,7196582,32794420,13174047,53220391,63765342,41125425,27258111,40235199,84904833}

    Returns: 5.984254856986883E7

  66. {93355,67,8,7953,49,38,52775,465,165,9,5216,4,8,857,2216,884344,6655,8842,8,829}

    {19372488,19624398,9258155,20184939,24950922,84180064,9868271,90590538,60026814,17574625,51132926,99211036,2287360,54401665,41617814,9203049,75689473,44509516,25121311,30872828}

    Returns: 2.535426937823278E7

  67. {43, 91, 50, 93, 7, 94, 10, 8, 38, 68, 59, 65, 77, 98, 27, 93, 65, 22, 29, 3 }

    {999999951, 999999953, 999999946, 999999921, 999999933, 999999996, 999999938, 999999947, 999999984, 999999990, 999999973, 999999934, 999999913, 999999918, 999999972, 999999995, 999999927, 999999993, 999999981, 999999919 }

    Returns: 4.1142579856139344E8

  68. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 3.597740924491638E9

  69. {1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

    {1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

    Returns: 3.550121685621355E9

  70. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    {100000001, 100000002, 100000003, 100000004, 100000005, 100000006, 100000007, 100000008, 100000009, 100000010 }

    Returns: 1.2542650627294576E8

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: