Problem Statement
Limak and John are little polar bears. John is cute and thus there are N bear girls who are interested in dating him.
Limak has decided to help John, so he went ahead and interviewed all N candidates. Limak is an excellent judge of bear girl beauty, so he was able to determine the exact beauty of each candidate. The beauties of the candidates turned out to be N distinct positive integers. (Larger values represent more beautiful girls.)
John has now planned a sequence of N dates: a single date with each of the girls. The order in which he is going to meet the girls was chosen at random, with each of the N! permutations being equally likely.
Before going on any of the dates, John has two sources of information.
First, Limak gave him
As soon as John starts going on the dates, he will be on his own and Limak will not be able to assist him in any way. Immediately after each date John will have to make a choice: either he rejects the current girl, or he accepts her. As soon as he accepts a girl, the dating is over: John will cancel all the remaining dates (and he will not pay the cost for those).
John's problem is that he is not such a good judge of beauty as Limak. John can only compare relative beauty. More precisely, whenever he goes on a date with a girl, he will be able to (always correctly) tell which of the previously dated girls were more beautiful and which ones were less beautiful than the current one.
John's primary goal is to accept exactly one girl. John's secondary goal is to maximize the expected value of B-C, where B is the beauty of the chosen girl and C is the total cost of the dates he went on. (That is, C is cost times the number of dates.) Find the optimal strategy for John and return the largest possible expected value of B-C.
The information about the girls is encoded in the following way: For each valid i, there are T[i] girls with the following values of beauty: A[i], A[i]+1, ..., A[i]+T[i]-1. The encoding is chosen in such a way that different values of i describe disjoint groups of girls. Hence, the value N mentioned above is equal to the sum of T.
Definition
- Class:
- BearGirls
- Method:
- expectedValue
- Parameters:
- int[], int[], int
- Returns:
- double
- Method signature:
- double expectedValue(int[] A, int[] T, int cost)
- (be sure your method is public)
Notes
- Pay attention to the unusual time limit.
- John can only accept a girl immediately after a date with her. In particular, if only one girl remains, he still has to go on a date with her, pay the cost for the date, and only then can he accept her.
- Your return value must have absolute or relative error smaller than 1e-7.
Constraints
- T will contain between 1 and 100 elements, inclusive.
- A and T will contain the same number of elements.
- Each element in T will be positive.
- The sum of all elements in T will be between 1 and 10,000, inclusive.
- The values in A and T will be such that the beauty values generated according to the problem statement will all be distinct.
- For each valid i, A[i] will be at least 1.
- For each valid i, A[i]+T[i]-1 will be at most 10^9.
- cost will be between 0 and 10^9, inclusive.
Examples
{10, 1, 100}
{1, 1, 1}
5
Returns: 40.99999999999999
There are multiple strategies John can use. For example, he could simply accept the first girl he dates. In this case, the total cost C would be 5, and the expected beauty would be B = (10+1+100) = 37. Hence, with this strategy the expected value of B-C would be 32. The above strategy is not optimal. In this case there is a better strategy that leads to the expected value 41. The strategy looks as follows: First, John rejects the first girl he dates. If the second girl is more beautiful than the first one, he accepts her. Otherwise, he rejects her and accepts the third girl (regardless of her beauty). The expected cost for the above strategy can be computed as follows: There are 3! = 6 different orders in which he can meet the girls. For each order we can simulate what happens and compute the corresponding values B and C. If we do so, we'll get the following six values of B-C: 0, 90, 85, 90, (-5), and (-14). The expected value of B-C is simply the average of these six values.
{10, 1, 100}
{1, 1, 1}
1000
Returns: -963.0
Here the dates are so expensive that the best strategy is to simply accept the first girl he dates.
{10000}
{10000}
100
Returns: 17706.37475360699
There are 10000 girls and their values of beauty are: 10000, 10001, ..., 19999.
{1000000000, 1}
{1, 9999}
0
Returns: 3.679155284022922E8
{1000000000, 1}
{1, 9999}
50
Returns: 3.675476907000374E8
{1000000000, 1}
{1, 9999}
5000
Returns: 3.316026716357059E8
{1000000000, 1}
{1, 9999}
500000
Returns: -395000.50000000035
{1000000000, 1}
{1, 9999}
1000000000
Returns: -9.998950005E8
{1,1000000000}
{9999,1}
0
Returns: 3.679155284022922E8
{1,1000000000}
{9999,1}
10
Returns: 3.678419547958604E8
{1,1000000000}
{9999,1}
150
Returns: 3.6681228947639704E8
{1,1000000000}
{9999,1}
15000
Returns: 2.6214461585638428E8
{1,999999996}
{9995,5}
0
Returns: 8.604358652709179E8
{1,999999996}
{9995,5}
10
Returns: 8.603748512029493E8
{1,999999996}
{9995,5}
150
Returns: 8.595209343730161E8
{1,999999996}
{9995,5}
15000
Returns: 7.721717680154073E8
{1,999999951}
{9950,50}
0
Returns: 9.999999688698268E8
{1,999999951}
{9950,50}
10
Returns: 9.999662066818933E8
{1,999999951}
{9950,50}
150
Returns: 9.99575165921099E8
{1,999999951}
{9950,50}
15000
Returns: 9.732761489586127E8
{1,999999501}
{9500,500}
0
Returns: 9.999999970265036E8
{1,999999501}
{9500,500}
10
Returns: 9.999956549978998E8
{1,999999501}
{9500,500}
150
Returns: 9.999455911279106E8
{1,999999501}
{9500,500}
15000
Returns: 9.963330292691402E8
{1, 2, 3, 1000000000}
{1, 1, 1, 1}
0
Returns: 4.58333334625E8
{452882143,855739307,215641076,2374120,854254203,942008605,635957507,160556306,191645554,217862002,513491449,30707215,135655438,24674098,590900908,51508009,696778112,34890972,585092971,824241483,146435426,366621154,78493349,659636331,807524197,866334376,355052060,751338306,54965556,591443416,247277532,507847698,299699075,462918607,362738170,153953277,404927211,851212028,314509582,449089116,69074030,828001031,479796331,57245819,705191480,70697238,108753827,254485943,958104562,546363149,931243777,957056339,912984302,9737125,616692669,573024851,876071500,824261081,176879508,931037055,268220848,424157039,291401105,567919922,887075645,506655626,721873199,144519207,357867653,888899132,593608322,279458034,569416514,73404652,336703853,127124346,996618242,297974031,381610288,807239155,696853532,165370417,764295493,462354185,175107541,233504513,35379035,903695393,57765593,212258542,687248799,178502793,636415580,978649903,746422714,376007576,337821880,320812264,520526782,695689533}
{92,94,96,98,91,94,94,91,94,95,98,94,97,99,100,97,96,96,92,97,95,98,92,90,94,96,99,94,98,94,90,98,96,94,94,97,97,96,97,90,90,92,94,95,91,91,92,97,97,94,91,90,100,94,90,92,100,97,94,95,99,92,93,94,94,97,100,90,92,94,90,91,96,92,96,95,94,98,91,99,90,91,97,98,95,95,98,92,92,91,97,99,91,98,91,96,92,90,96,93}
0
Returns: 9.966183314873302E8
{289899734,39148856,314511750,947749944,867172193,758412478,28405107,834407034,694770203,931127783,155330985,360653517,965462480,404163840,532896164,619456496,496573680,966981792,980096195,871719806,461248629,455180205,46837358,657208087,662218547,243231172,876551844,997849154,132327597,605339349,175027617,422227330,497004556,489539366,369977274,216693101,100468195,250898732,51100134,647754749,182026514,206431118,8408265,5346,610594958,393820781,619461841,107168637,360802572,452074388,831404794,822051200,759770944,878242151,331775638,421989490,121473323,208327481,272354995,106317271,666183182,299898963,528544601,15704089,789438328,898521874,232397189,742422875,1936957,283497323,390177623,183963470,342444792,251102240,183968815,953039749,644923020,655947008,912724737,858241943,108021395,596645882,532809494,720308690,327404385,864585132,142298179,301394059,72912612,267169526,407711329,591612145,567068488,936255929,607316234,209023168,687294154,839713422,951446042,689231110}
{95,92,90,90,92,96,99,95,95,99,90,99,92,98,100,99,90,97,96,99,90,96,100,96,96,96,94,90,93,98,93,97,90,93,95,92,98,93,96,92,100,94,91,92,91,99,99,100,95,95,97,95,99,96,100,94,100,93,92,90,100,96,95,98,99,100,98,96,93,91,97,92,96,96,94,95,94,93,95,100,96,100,92,92,93,100,94,92,91,97,92,90,92,98,98,99,97,95,93,100}
2
Returns: 9.978458754393902E8
{751812653,614595191,43935897,127075565,712456246,660250388,127701107,144041855,306765939,657040176,855672441,802928653,248905335,60837951,375895962,618655884,540096818,894113931,646516412,988063349,765839129,904941282,903314242,236042884,237079247,126049859,127923806,804250948,794229169,879392956,449054071,398558173,346504498,345506319,525633737,911477095,858273058,653334843,908035302,17555349,162891371,616224094,820484001,411796705,677062044,48896315,30452589,69675214,943010245,529485352,910254914,561365725,286942985,813569156,797408608,524022231,939619014,925332413,180789531,586364534,657241721,629843601,837439058,856262570,827866271,215589146,767739665,686139328,868923989,528291318,703694676,884331711,144515411,376695029,148644767,674093807,425591343,31613707,743769020,221117939,561099059,506540285,782483663,848042043,172625792,579892270,224580626,112244806,357741034,405370156,551125691,867499106,35213756,241081101,723761676,715596378,456670246,344017692,254252057,178110586}
{99,95,92,91,99,99,92,99,91,93,96,91,91,100,90,99,97,95,97,95,98,100,96,99,96,92,100,94,97,92,99,93,95,99,92,93,95,95,100,97,96,95,98,95,92,96,92,99,90,99,94,98,96,98,94,100,100,93,92,94,94,90,95,97,97,97,99,92,100,98,97,94,91,94,99,93,99,90,90,99,98,92,95,93,100,99,91,97,90,93,90,92,91,93,99,98,98,95,100,98}
7
Returns: 9.880524661324251E8
{546876984,5598246,166068078,782312823,59989821,81742132,480290707,117018835,49276741,837053960,758140486,999802732,964135994,117663776,825642032,988052975,922660517,955164965,316631800,468315249,125928451,144168001,746515514,253599996,94815174,117160993,168805754,514584038,422276777,60742587,292919887,969153760,66340833,458987964,603982934,126330653,393246447,84273640,95865839,442523187,773843952,706522676,442325918,737979945,824186452,120484302,578549272,599363320,75649266,895181071,67678568,54094069,39349072,666710433,307694064,986680597,783871425,476499817,353780986,206148201,537242404,646700872,27818312,603583236,958205187,484317597,582430240,351451634,421107589,530812430,793974820,194951540,89851457,88817090,785447836,914037908,209301391,216513459,365917579,137467008,111694530,286112498,191561076,3559953,952822930,499255140,842756901,589210707,828271308,196537887,795358907,218030063,695755110,675693571,821613298,653960297,160011167,256559889,857928282,581118755}
{92,99,95,95,96,92,94,94,99,98,91,96,95,93,92,96,99,98,92,95,92,90,92,97,92,100,94,97,99,93,90,91,92,96,96,96,96,100,90,94,95,91,99,99,92,99,94,91,96,94,96,98,94,96,93,95,93,95,91,92,99,100,93,99,95,97,94,90,94,94,93,100,93,91,96,96,100,100,97,94,91,90,100,93,94,92,98,98,96,97,100,92,97,90,90,91,97,94,90,90}
20
Returns: 9.997776114698908E8
{965148965,120887860,119603626,475378695,526104538,692541316,622761366,372755537,523545233,448183539,806949235,8006178,115770379,23848247,41706563,7677114,914370296,196122368,885221324,23393404,202740743,61247775,311272928,374167589,341006254,832718270,209144510,112003026,645740782,915414888,110555093,463406098,888819099,230158719,938784792,414923636,775216386,414062510,787679173,151277971,714762400,447144759,11800500,830532779,470993005,53507062,690726244,237879653,102145782,428463919,113789408,304886524,489711693,425062336,531570464,830717946,257780605,740714973,942720971,756037738,508646213,53276063,71960187,249981663,135951133,10744979,664905299,911167519,277323840,305100823,62445489,992086239,752245581,74245988,675135369,75754938,980269402,218377964,313634590,934931535,646841882,427423997,92334410,136553574,852486332,623904873,819787871,962783289,217136197,615025193,718821026,725782409,520817608,790781213,975764072,656768740,654042543,493185722,420452610,783882734}
{96,96,94,91,95,98,95,93,98,96,91,100,95,93,98,96,99,99,99,90,98,96,98,100,96,91,98,92,96,91,99,100,96,90,90,90,98,96,91,96,100,90,93,94,91,90,99,100,97,97,98,95,92,95,94,96,96,100,96,100,91,92,99,95,93,100,93,90,93,94,94,92,94,95,95,93,94,91,90,90,96,98,93,99,93,96,92,99,95,97,99,94,99,95,99,100,94,91,99,97}
80
Returns: 9.919954786002109E8
{121277274,219928215,517254296,86833086,985105326,264763228,760474889,301542517,427838658,888336040,704487177,451677611,138718797,491695537,352814491,905707825,39290488,791081265,264184565,822614606,80352441,929699828,147528486,23417965,121123671,802790817,346520404,165407329,544369785,637072070,15789101,518163410,857000284,385559748,457512848,842105609,650322975,217987736,996164477,930677984,106323776,700651654,234871946,97558924,44863542,587686437,855783100,84154029,231284053,119967664,906768634,311636493,902183844,906813471,335054457,23307514,562120640,681574860,41231194,106490424,171163281,57020294,624653833,28163565,295096393,82166680,722785525,945419367,152670768,718950002,728613702,111510895,272118007,963485648,61586170,169497900,403688436,917369269,253651928,634972488,889853284,12936913,946608980,792037127,919750384,134179788,667860992,334387375,668271000,709092186,440877798,839434280,618628831,918047982,867597844,913725224,852731014,442899721,711660942,5401781}
{97,92,95,91,95,91,90,91,93,99,95,91,97,91,90,96,93,95,98,93,91,92,94,95,97,93,96,97,92,95,92,99,97,97,100,91,96,98,90,97,96,95,98,91,94,98,95,96,91,93,97,90,93,90,95,98,94,99,94,96,94,96,95,90,90,92,90,96,99,99,92,92,94,99,93,96,96,99,91,95,100,99,96,90,99,90,99,90,100,90,97,91,97,100,91,95,100,100,100,98}
200
Returns: 9.959604153715045E8
{362617496,527741415,21328284,111619513,591875813,556831212,87577619,644798533,347817590,518734498,689678142,76028696,6636534,143808099,716599958,139748040,895627044,867747488,636712934,747298839,275385708,396493091,65164641,248379877,37449165,360872953,65024279,21974944,549832570,182112040,710897140,912450065,709853454,732225423,876585929,154245619,141572986,964163547,799044151,489390576,335414396,341238644,417935623,342050929,485046743,134535580,334315321,233190138,854799419,971028254,980488976,130185127,367521344,45653616,231081355,257486860,259042920,296105633,131978155,808875489,478217672,842875294,721325553,40587478,575100716,450427833,47349448,716673702,267107732,846393598,58580629,602522127,40148593,476516251,944573056,525195335,463568183,278888376,758385472,170883953,102432981,591390799,153585431,469954324,489560766,384666786,579957535,748603686,533288770,711935689,557479174,11506442,554810983,131321079,904610271,982428050,581748911,951959718,551618103,848856642}
{97,98,91,97,97,99,99,94,92,95,91,93,92,90,95,93,97,95,98,97,97,94,94,94,91,97,93,94,91,95,98,96,91,99,93,96,95,91,100,97,94,90,100,96,90,92,100,95,97,95,92,91,97,96,96,96,91,97,90,90,100,96,97,90,94,98,96,97,99,93,93,90,94,90,97,92,92,94,96,97,97,98,96,94,91,91,100,90,98,98,91,98,93,96,96,95,93,90,91,100}
250
Returns: 9.822461882039168E8
{37844065,296622528,430546854,383380103,111879663,289909978,135239463,37630015,47011280,257874179,458607675,63554130,101541408,471482423,406204718,585553803,432767723,683015721,976285233,976372388,526239672,49618337,697888738,827051150,527272718,98075121,75487154,379535293,469437571,10052854,87873868,359797988,159191734,370937073,743178090,123587748,660847051,878417552,13734115,560374682,136291730,324858141,623928811,90349489,796340563,30133528,528419644,81624638,565665601,357221228,57997025,91905272,259355916,608402114,771472773,786628633,558993586,846959926,18680277,28431157,709529132,106554144,388229144,868720865,477491216,983923585,844824964,990854618,714857489,858559078,551229300,703665570,35933571,27674462,646531411,832274133,57807990,27467406,913898770,475989942,384688633,824412146,420411565,644044548,285330611,191884337,283189532,844324197,38844263,301869808,725271705,600889746,260940303,113500848,322126962,738431518,949940784,166951925,581802488,664798272}
{96,96,95,98,95,92,92,90,90,93,97,96,97,98,98,90,93,93,99,95,98,91,98,94,96,100,92,94,95,92,97,99,96,91,96,91,93,99,100,93,100,97,97,96,94,94,96,95,95,92,98,92,91,95,96,97,92,96,100,98,99,96,94,94,97,90,93,100,97,93,90,94,100,97,100,91,99,96,95,93,96,92,93,98,96,99,92,98,94,91,93,90,97,98,93,93,96,96,90,90}
800
Returns: 9.902904963845539E8
{675035152,262712306,934675076,964582692,794035249,298287071,895944477,810117431,190553383,38502344,370376922,635740198,590416985,541134303,88418109,465836950,649650457,411625853,638455989,466650489,975892008,511501535,492145637,816543420,956162970,359178928,42403484,20172358,271565043,924774490,939947764,946600194,40003148,727139191,763699238,834038396,25426262,512160066,496672179,68495996,550662409,867049100,556752545,141079393,408183403,645170653,459432695,910350211,56796506,97888683,229517051,32688513,461906569,721662688,701748284,270585891,80841615,596668119,290758248,204923009,373958961,83222364,4039555,413962108,810361554,767738792,100516855,688304167,279898857,597189033,609316515,830561265,464238133,166069059,824157009,724937887,811239712,136106055,635288097,720552569,86511089,864805148,605757433,548417658,438984187,160022068,819003548,372342153,756690187,109761795,577265162,130649147,45500510,581304716,544611254,708378416,349043507,645128108,249198934,481458715}
{96,99,92,90,100,95,90,93,92,92,90,94,97,95,90,100,91,100,94,90,96,94,99,92,96,95,100,91,92,95,91,98,93,93,96,90,96,96,91,96,96,91,90,91,94,90,99,96,99,92,94,92,96,93,94,100,98,94,90,98,97,91,93,98,92,97,97,99,92,98,92,97,98,92,98,91,91,96,95,100,99,98,100,92,99,93,92,94,97,92,92,91,92,93,100,92,90,96,90,90}
6789
Returns: 9.724546270423675E8
{159102254,416971007,937804984,550744796,54328951,278086282,449073721,50419285,964717059,881278016,983973694,855708166,188785913,101034714,681302912,433609380,693145391,900532970,632437047,612743536,731538926,447085650,108949545,168887375,781689066,994431962,371681243,657001853,253927487,192749500,525271726,413029740,609720506,315593061,963774536,516565808,593679343,265364608,419501445,410912753,146642623,403475138,119137270,187944888,357026204,800440181,621554267,50171594,553489503,253991313,515431481,137544780,701076962,476897377,306432154,335282380,323845690,530629748,844800584,577773176,723379247,222588661,990802916,185616104,538181722,807093803,554698264,131861064,72458410,974199708,542773816,71617384,230191197,661911085,112078623,587217400,314867617,733632890,489905345,868357119,987624202,5336826,5901898,541217516,334750554,164850403,729016247,658596244,695480151,573816830,88885771,271375749,796405491,79688686,456991853,187103564,739298840,11690116,318964627,664273601}
{91,100,100,95,96,96,95,93,94,100,96,95,95,94,97,98,97,97,92,99,99,98,94,97,94,100,95,95,93,94,96,94,93,93,98,99,97,92,90,91,100,96,96,93,100,90,99,94,97,90,92,93,96,95,99,100,94,93,95,98,96,99,100,99,100,97,96,96,97,96,95,95,100,90,96,97,99,94,91,95,92,91,97,98,96,95,96,90,96,90,96,91,97,93,99,96,90,92,91,95}
50123
Returns: 9.852127291204545E8
{37301528,440793260,77134715,165230413,141242072,874689677,145243773,748669848,413524502,117549929,365118804,543075630,360288295,813931637,759214328,128006736,419889236,932467843,984761324,694876054,230211319,506298244,322257520,631577148,106769856,994621155,409137762,973958593,190785763,388467903,951461659,80603642,829261162,28596374,98350406,970503234,903286050,96110531,571689433,169326904,213660459,936808236,712402533,426465105,750739873,324133212,406988193,23145460,256601054,244265868,570537865,486812372,750564112,892795385,118389519,709850319,887416539,380043632,536325263,930718654,621027887,340303273,11322295,302805400,368899646,109672701,125824985,124702048,58299583,697514417,294028951,271960041,634322653,858947835,698425146,237578877,183081047,105413338,113240688,292198452,202195557,683778553,779010824,952759668,576573937,749916694,515126338,316506827,982476678,903967952,99741832,603504564,244271225,111064127,906309963,465687222,73253179,32134948,590389269,131552761}
{100,99,94,93,97,91,99,99,94,99,94,97,94,99,96,95,95,94,90,90,90,93,100,97,97,94,97,91,99,90,96,99,100,100,91,94,100,99,92,93,97,96,98,99,93,94,91,98,98,91,98,98,92,97,93,99,99,100,100,98,100,93,96,99,93,95,92,90,93,92,93,100,97,91,96,100,93,97,97,90,97,92,96,99,97,99,96,95,96,95,92,96,99,96,92,100,91,93,98,94}
180123
Returns: 9.693957620934808E8
{6496948,990203964,937805567,168935836,896704370,691896324,528950864,602999035,257024090,96696859,396586211,334905165,159772621,173964806,432030386,166830569,75904950,460922013,472833085,708863998,112388187,317393848,122204922,766338864,374808608,807257970,353680450,535861479,293686740,464806352,850436524,152700040,307526667,640758442,321635875,56747389,185171118,703103091,659746423,442195207,799799949,56332634,777100371,959572570,82813791,61647108,126403138,158718740,522569121,599236222,867582737,487473659,769146422,842304010,106328874,143955029,649561980,460009323,532332859,795765071,777332026,235285734,948465110,84858692,728560528,122617337,994122432,913731645,825720427,506385207,355926851,625520375,415234192,985543573,437609296,498047982,47190680,564012434,656766721,569759800,15765007,524349458,57233458,784911428,219169819,16078683,781382808,868731798,476088005,166232018,517013221,105936382,254034104,465478330,43311426,982594631,588095666,37433857,896326275,266332444}
{95,98,99,93,100,99,93,94,93,99,96,95,90,98,95,100,92,91,97,98,94,95,100,98,100,92,91,92,98,98,95,91,93,91,92,90,90,96,95,91,94,99,96,94,96,100,91,98,99,98,94,92,92,91,99,92,91,100,92,99,96,95,100,99,95,92,98,93,98,92,94,100,99,99,91,94,98,92,92,96,90,96,96,92,95,94,92,96,94,94,94,100,98,92,96,92,94,93,95,100}
1000123
Returns: 9.263824317605698E8
{126810491,180157887,863457287,226592666,648260037,82090435,840671345,185326165,543711289,159687602,824439115,384504286,997854165,617430101,257667082,127836495,575197142,281875661,365611478,133683834,163901676,417106208,887741805,729365572,679550491,831959456,548256966,66776441,51238234,225060292,97201055,30565077,405218178,813174693,109674094,53478215,895265127,950345438,91320731,438976416,962549391,915759846,675997053,960403555,385706298,933664134,940756401,960903439,68056147,158884230,947103625,231957822,575990438,687361781,961323393,255540928,371837588,362096710,322317369,275592174,587157001,272034775,306157250,992375178,85209468,415831343,898369744,980474594,218693133,989690475,271967361,33758875,757966672,947964414,994162430,996189321,734144899,787435182,809609111,802201045,946319412,609229087,34158866,522309849,149107220,847998610,630367128,520944807,210095319,952684496,796536980,797252319,77235623,102694229,642143849,162445090,371041924,540513592,995436035,442251408}
{91,92,100,99,91,93,93,91,99,94,96,92,98,96,94,95,93,99,93,94,90,98,97,92,94,91,93,92,90,92,94,90,94,93,99,93,97,90,93,95,94,97,95,100,92,97,95,93,93,96,96,91,91,92,91,95,91,94,95,91,95,99,91,97,92,99,99,97,99,100,100,90,96,92,100,96,99,92,98,100,96,93,91,98,93,90,92,94,95,96,93,98,94,93,92,94,91,90,90,100}
3888111
Returns: 9.00235214494843E8
{74716640,802865393,313514441,365494838,911941879,580898723,220875873,175977448,589792212,832280026,656609083,418477889,11288306,73190965,351841126,661701336,74829250,72428818,34496291,620558832,338862486,626196641,517366990,352015059,758497219,839644399,641286101,303845353,287214948,58764235,976597484,361931588,861629628,290111924,727426425,773571506,723526999,948302297,949548954,313319210,633098674,458674388,584313450,644386979,384381704,936154576,306088314,311727305,8583393,193100956,932286137,347445878,819297597,302169478,551977288,430311167,141813876,45779740,734156520,429028824,104543975,563270355,790960411,966173602,853382279,370903187,592261459,429425629,171721836,394326764,742744838,804820509,853001151,179574639,301723840,237382854,115729214,607812153,549110159,124312606,653429461,333912647,324274835,325243409,636082124,876252123,755554575,630412352,922031862,342227446,59441175,26575836,905497801,702917937,845265789,611396431,926337475,437527248,40822059,98059310}
{98,98,90,98,99,100,90,94,99,90,100,99,99,91,94,94,97,100,100,97,99,97,94,95,91,98,91,96,98,92,100,94,98,98,91,97,95,100,99,93,90,96,92,99,97,94,90,91,93,98,99,90,94,92,95,93,98,97,100,96,97,97,100,95,94,99,100,99,98,98,100,96,91,100,93,99,94,93,98,97,91,96,97,93,96,90,97,94,97,94,98,91,90,97,94,94,93,93,92,90}
10123123
Returns: 7.568419728106979E8
{559294416,80831003,938777881,639080916,383073823,959184974,361936748,770988101,674445619,541637629,201282497,566380518,766507491,120376766,28767898,208995154,732704812,10820273,476749822,706613323,93120337,877529704,898754692,396761037,698430668,359413617,208296898,763920095,544467270,723918806,378252437,103761686,804749808,317030317,595358953,187823630,128731642,957295700,958811730,803177260,498933328,12610579,369557778,117957170,132987344,250842027,326952324,865692155,114178651,656218497,572305477,207298987,386264553,323576520,604060023,84695220,682990136,812356920,701131667,79973758,388792077,79384103,36251795,193541884,248930771,631610747,233881866,377662412,441422798,45209947,33356023,940356125,57820525,402913800,910829647,190807868,653755826,90298322,56500022,767934476,746516818,481321850,975233462,132781370,804898370,431809836,69992942,340404857,96683107,623640960,272894966,485475183,555541414,309146760,679017067,804472184,793273858,912898932,34650947,234696655}
{100,96,96,93,96,97,99,92,100,94,90,100,91,91,95,99,98,99,97,90,95,99,94,93,97,95,99,97,91,96,91,99,91,95,100,97,100,99,98,97,90,96,96,91,95,99,99,90,97,95,91,100,91,93,90,96,98,99,93,97,92,92,93,94,97,91,99,96,100,94,90,98,100,96,97,95,95,95,95,100,98,94,100,100,95,100,95,90,97,98,97,99,100,99,90,94,100,98,98,97}
100123123
Returns: 3.491700990262005E8
{700648225,87178794,983721590,273450254,202106479,36929763,201834867,19946493,89641359,195521838,223719766,736751446,60914049,825120892,551082765,89889561,686353173,267121167,105859857,179124797,855077303,845135347,857278547,782440242,412200730,752729584,839235476,517404697,810764778,753887278,192931321,511413002,693582423,176652910,784863255,895688901,66099025,986698121,915635393,155740383,34736311,139355159,892491828,95650359,816992402,296090945,185539919,503345574,563212111,291399775,682470370,270805765,136535122,392265269,53246006,401252203,144994852,744997834,918656900,808275981,351401463,111588220,172205334,44983885,140757482,957068589,940672786,206856506,796283061,708824530,362596888,831019371,700696040,107605067,926669729,517688442,403696011,112209648,873550367,966908121,256125774,408537089,237713886,245177247,800802357,143476243,646429450,798313560,888474076,417602701,459105892,92391890,381707272,631311225,137375775,522464753,440896165,930564912,581837610,89695578}
{97,94,98,95,92,91,100,93,98,94,96,100,97,95,94,96,91,100,92,94,98,94,90,98,100,95,92,94,96,93,98,91,96,94,96,96,93,93,99,99,97,92,96,94,97,100,98,97,99,90,90,94,94,99,92,93,94,92,96,98,95,91,99,99,93,94,94,96,95,91,92,92,93,99,94,99,98,91,95,97,91,93,90,94,91,90,95,95,92,90,93,96,90,100,94,93,92,97,98,97}
1000000000
Returns: -5.2919494997152483E8