Statistics

Problem Statement for "Embassy"

Problem Statement

You've just qualified for the on-site round of a major coding tournament! You now need to sort out a visa to allow you to travel to the event. You know that this is likely to be a long process, but are determined to sort it out as quickly as possible, even if it means working day and night. The process involves filling out a series of forms, which then have to be approved by the embassy. When the last form is approved your visa is granted. The approval process is very quick (instantaneous for the purpose of this problem), but there is a catch: each form has to be approved by the embassy before they will give you the next form to fill out. The embassy opens at exactly the same time each day and remains open for openTime time units. By the non-standard embassy clocks, a day is dayLength time units long, so the embassy then remains closed for dayLength - openTime time units before it opens the next day. Forms can be approved at any point in time between the time that the embassy opens and the time it closes, inclusive. However, if you finish filling in a form when the embassy is closed, you have to wait until it opens again before the form can be approved. The length of time it takes you to fill out form i is forms[i] units and the forms must be completed in the order they are given in forms. You already have the first form in your possession and can start filling it out at any time. Return the minimum length of time between starting to fill out the first form and getting your visa granted.

Definition

Class:
Embassy
Method:
visaApplication
Parameters:
int[], int, int
Returns:
int
Method signature:
int visaApplication(int[] forms, int dayLength, int openTime)
(be sure your method is public)

Constraints

  • forms will contain between 1 and 50 elements, inclusive.
  • Each element of forms will be between 1 and 1,000,000 (10^6), inclusive.
  • dayLength will be between 1 and 1,000,000 (10^6), inclusive.
  • openTime will be between 1 and dayLength, inclusive.

Examples

  1. {4,4,4}

    24

    8

    Returns: 12

    The embassy is open for 8 hours out of a 24 hour day. Each of the three forms takes 4 hours to fill in. If you start filling in the first form 4 hours before the embassy opens, you can get it approved just as the embassy opens. The embassy will still be open 4 hours later to approve the second form and the third form can be approved just as the embassy shuts. Since you never have to wait, the total time is 12 hours.

  2. {4,4,4,4}

    24

    8

    Returns: 28

    Now there is an additional form to fill in. You can't complete the process in a single day.

  3. {2,2,2,2}

    24

    1

    Returns: 73

    The embassy is only open for one hour each day, so you can only get one form approved per day.

  4. {25,500,630,2500,1000,350,22,58,100,400,500,5000}

    1440

    360

    Returns: 16945

    Time is now measured in minutes. It's optimal to start filling in the first form 335 minutes after the embassy first opens.

  5. {567213,494175,41987,510822,279719,889559,572483,117704,641618,110895,259588,721431,930617,438350,184363,37908,784347,842509,563146,965103,966945,204978,136741,308997,814758,672822,774768,279015,303415,142975,980557,678292,354894,539685,246801,649725,110680,480112,286912,941249,157936,208727,608459,283950,983841,505666,684633,863492,84134,478601}

    389114

    349228

    Returns: 24712086

  6. {889580,869937,865011,116251,240526,124148,801592,708043,687255,650744,270700,63427,272771,966678,910755,500529,912189,398677,395295,672054,188961,788267,572694,517536,300730,563969,140777,582576,229444,78383,869420,213909,184235,824891,833892,183022,75977,271837,273411,58507,141290,420221,386990,6956,434506,720818,721911,149823,235733,965188}

    503266

    46143

    Returns: 35065525

  7. {822309,543722,719971,835309,730439,550668,140188,15318,314613,891904,771106,47760,546908,468752,961208,823739,102358,696370,898450,51877,855792,246285,188499,473551,919013,389369,333646,838248,860192,915711,95176,328784,340221,556563,292274,521301,800391,503457,202802,401911,952314,491005,473947,184167,835456,395056,839152,252548,37367,849200}

    808932

    130971

    Returns: 38788777

  8. {986281,794727,150874,73327,999891,852459,110313,972204,980574,344772,715024,203317,830311,939112,984389,21399,167097,232577,559532,562516,786064,642149,843286,272281,618712,293658,160138,42054,789419,343579,585976,195819,591958,794893,711174,483912,756051,537416,996230,763468,826639,53972,199739,9494,992932,158184,878427,619638,616159,452012}

    185096

    178356

    Returns: 27496129

  9. {944891,531831,160598,119270,205410,143441,774535,148228,658098,180080,230735,270935,184821,879805,345043,282653,10215,226128,421286,618438,175283,363247,351499,978865,173877,555411,378228,85615,29496,488418,179335,619390,72312,570036,549399,50574,906208,957970,600167,110909,875532,455601,549738,674205,598663,811577,911556,757933,648653,895044}

    297033

    296155

    Returns: 22711182

  10. {223497,750486,458108,181064,397207,982953,82256,703362,643588,797539,226026,576011,71943,976029,131292,229840,189712,7069,294762,886065,835705,105180,642440,92351,279948,288767,173400,941880,395783,358817,631344,331916,490004,568392,969169,527834,717774,233321,168943,820466,438658,156911,814255,751059,779947,450737,964259,658797,723060,689652}

    128720

    417

    Returns: 28026600

  11. {676344,516658,89960,697659,287877,266130,637071,733629,137875,270186,790553,484886,753681,618564,106952,506918,385048,289685,880274,561084,134771,345991,463959,642966,874529,922479,395310,693734,749450,308310,665370,871307,111244,334132,893451,176851,876271,925871,483368,99774,341171,992927,106244,257725,16896,962763,706403,222702,970292,264364}

    9335

    4819

    Returns: 25564852

  12. {388440,207849,537123,813653,191850,383128,289788,467450,579539,843843,207877,544432,667377,978207,183154,734981,71566,870166,735141,328698,215654,728957,133492,636798,603747,595230,895392,584944,13923,13422,863646,727137,952496,165462,811857,19726,602758,113581,961933,45289,329360,275131,348436,378128,91306,674871,443868,26003,451295,793673}

    638725

    2467

    Returns: 41903098

  13. {776683,969160,400486,962970,487737,385083,992513,759662,538022,874587,265161,948027,290810,287310,260898,630467,74485,494957,244321,461746,403968,324798,328582,654059,487990,230073,871367,964027,718179,105926,602313,981155,37700,690045,44187,157073,734786,68387,27333,914790,341243,736690,426999,444913,316089,803729,309783,111538,154167,66327}

    807671

    291129

    Returns: 32146212

  14. {17698,262667,449563,586368,993236,902566,77559,559487,384218,439951,519663,335952,628720,62684,879828,301795,961918,223255,351211,121946,703843,162869,171112,20162,524970,8608,349359,90397,743500,885100,160849,401431,382903,745828,629204,682131,421062,465535,65577,660957,865092,590626,184311,772535,145070,608808,433615,932625,267821,458645}

    317429

    48555

    Returns: 27902895

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

    9

    2

    Returns: 422

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

    9

    7

    Returns: 271

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

    8

    5

    Returns: 299

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

    1

    1

    Returns: 299

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

    8

    7

    Returns: 240

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

    3

    1

    Returns: 235

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

    4

    3

    Returns: 262

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

    9

    5

    Returns: 305

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

    7

    7

    Returns: 217

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

    5

    2

    Returns: 267

  25. {89,22,22,9,97,89,79,74,68,86,90,61,38,29,35,96,26,70,45,79,23,58,39,69,51,32,98,83,39,48,9,46,97,21,78,93,52,95,5,23,13,8,75,56,35,27,67,45,84,88}

    84

    73

    Returns: 2770

  26. {43,16,82,90,27,98,94,57,100,6,60,67,22,79,44,14,35,76,87,3,84,34,79,97,14,16,58,80,25,81,46,3,68,29,63,64,90,26,58,2,4,59,19,21,43,31,53,23,100,21}

    19

    8

    Returns: 2624

  27. {70,46,59,58,22,61,77,67,25,33,63,11,89,92,18,3,92,11,25,27,30,83,36,91,54,6,62,8,52,61,75,36,55,6,93,78,80,92,6,96,16,48,43,3,98,60,9,77,21,9}

    19

    14

    Returns: 2447

  28. {60,9,29,20,29,61,1,14,48,59,13,57,4,24,66,54,49,30,74,13,91,6,33,49,40,86,99,16,60,47,24,4,40,71,13,65,22,67,28,52,2,48,18,1,91,29,14,55,29,96}

    9

    9

    Returns: 2010

  29. {36,11,43,47,86,79,12,24,63,96,87,58,16,63,27,4,51,72,29,93,3,81,27,47,98,26,25,4,13,99,58,15,39,99,28,11,71,3,32,46,37,48,50,70,58,31,96,6,90,23}

    49

    30

    Returns: 2490

  30. {80,1,66,74,59,81,64,59,15,15,28,57,94,99,8,71,51,81,30,93,34,50,91,17,13,38,73,15,81,38,65,21,52,27,88,27,3,35,97,50,56,85,24,34,68,45,63,13,86,64}

    24

    20

    Returns: 2591

  31. {30,9,44,35,81,83,17,56,98,15,11,11,46,92,74,62,82,89,13,16,96,86,15,26,65,74,57,96,88,41,61,20,64,14,96,65,56,96,43,38,39,8,41,64,99,61,62,2,60,37}

    100

    65

    Returns: 2835

  32. {95,6,21,32,61,2,90,63,5,64,25,70,2,69,58,36,28,88,13,29,22,96,97,84,12,97,13,47,21,61,70,69,97,86,34,77,32,76,74,39,16,100,55,15,59,24,52,44,53,22}

    9

    4

    Returns: 2561

  33. {21,82,92,91,74,99,20,56,53,63,43,35,3,24,27,38,83,79,73,46,23,78,66,12,91,82,77,50,26,53,81,59,98,91,59,13,13,20,45,16,17,68,76,57,62,53,25,62,24,92}

    43

    36

    Returns: 2703

  34. {97,51,87,84,93,23,65,71,45,90,11,9,31,8,53,78,7,61,57,31,67,61,31,66,10,13,23,16,51,64,40,68,38,87,42,98,63,87,39,4,60,9,73,83,38,56,5,18,15,93}

    88

    72

    Returns: 2476

  35. {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    999999

    49

    Returns: 50000000

  36. {999999,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    999999

    49

    Returns: 49999999

  37. {999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999}

    1000000

    49

    Returns: 49999950

  38. {999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999,999999}

    1000000

    1

    Returns: 49999998

  39. {999999,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    999999

    1

    Returns: 73999927

  40. {2,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    1000000

    1

    Returns: 49000002

  41. {737694,129837,342608,993554,666642,234695,392026,400099,825661,322874,116904,423881,96968,847914,991485,248640,11339,59883,597511,391219,288461,758975,506022,708031,675076,568220,264360,970798,462104,635043,62157,337338,53027,150698,485190,75666,854953,708722,805680,437520,631076,165487,331485,399806,314683,77637,975820,195097,55300,481672}

    972523

    378099

    Returns: 31480331

  42. {562505,836348,270427,650229,882431,69907,7786,16859,623888,994608,821849,65789,395857,560169,762647,254789,153100,125631,394436,382990,901366,988391,977262,943141,384184,54916,138838,426630,416041,292649,69545,831961,779281,381467,437002,200830,123815,412300,401991,631485,844627,293792,37856,348563,257068,722602,163268,147947,524537,287600}

    262673

    82596

    Returns: 26040200

  43. {654451,293730,856600,837505,664896,850789,366233,459588,409145,1677,115716,11481,595876,504861,476150,206617,237945,918345,877440,906641,435552,6323,900257,686587,613169,291376,316938,562884,127345,416899,996442,895751,66202,356256,155231,708622,288851,243370,508953,226455,639219,279476,340217,437963,23938,962498,446044,737864,516342,847368}

    538964

    185364

    Returns: 30651071

  44. {804281,185832,699358,189623,377056,954552,273581,731280,957749,414010,667357,251006,798061,321633,417344,438415,713777,561873,100115,276348,872728,216797,777544,516464,367979,475659,431741,608586,666655,71435,624386,513491,680157,724161,108886,100421,295868,332740,892394,395343,591939,374036,246812,930314,738859,46501,894203,521539,747994,551644}

    732488

    587891

    Returns: 25889596

  45. {906921,611530,718451,686729,283167,316725,487513,536479,13170,366288,402315,416384,19915,416766,386378,143399,89858,823058,641410,204865,251549,873744,453845,439400,193556,742060,966162,614505,816463,250953,549945,542911,122917,845370,328505,644757,815837,305219,120433,44615,652784,571225,106672,831264,261956,995549,852983,881115,862643,693539}

    990581

    339682

    Returns: 35237574

  46. {94657,750063,841738,285913,694504,392118,273732,793859,374926,503449,792676,273949,834379,974381,640281,281171,879335,131636,384771,203265,778713,752932,395312,721011,363017,415903,827872,685411,945231,952055,120899,562558,859312,481459,609274,73886,259622,15171,262801,101455,200920,896524,346378,542158,33181,154851,462868,841092,552764,390089}

    13008

    2991

    Returns: 25158082

  47. {229678,394227,502154,370233,85209,409731,181316,569726,121429,575695,854892,859208,314347,3160,248100,278197,388496,660563,893689,904783,815725,593635,127532,345554,323929,701020,25388,600489,7644,963712,26648,602992,522606,885508,761343,709042,803379,772492,7075,164075,300232,994345,922673,281862,812464,117345,473354,793823,127909,441190}

    968764

    631882

    Returns: 27133508

  48. {513230,505885,280008,524201,313153,154519,264093,419137,773960,544922,383642,404644,496216,775129,730512,411294,505050,686966,142653,772844,40037,795846,921361,929207,446209,628172,645674,771933,883045,279228,931931,589991,265592,927800,44000,977811,56339,444246,84394,380363,55997,16855,945560,629291,52781,129776,678268,83390,954314,624900}

    296465

    221574

    Returns: 25091540

  49. {671852,668263,257354,385499,695452,854235,803910,107501,508047,254805,69204,881216,399470,24760,981490,288272,512593,111832,295378,954696,867326,682679,895761,767237,612909,465035,551490,431952,491270,350965,367650,707814,233760,588681,466144,105907,845379,148812,566876,17233,18854,31921,631847,228684,79664,996890,623615,711777,901177,504284}

    577044

    397813

    Returns: 25435504

  50. {219593,72954,997574,245233,144408,138536,713187,612501,396365,78729,744812,677471,446014,532208,950224,965628,732340,154209,940654,621511,175206,465296,214,321674,731132,784160,499592,473731,923021,421412,414770,277788,737121,458081,983477,844529,678639,989577,593824,426061,173534,540095,294322,239404,735943,865177,343387,772409,448881,27161}

    900539

    598584

    Returns: 27637833

  51. {909203,929332,946299,918164,123049,99456,207198,847038,423185,998596,369377,420903,429507,162184,711541,147978,109354,102527,975035,640214,779741,417295,272007,305960,416872,943118,173976,284558,348099,979650,698976,865350,640472,202400,540672,697850,170369,449421,884171,867724,603526,909598,586882,771720,834595,148251,393174,760234,763007,443895}

    230888

    62400

    Returns: 30659882

  52. {389493,962136,279500,955530,961933,872724,218496,266418,60290,966704,443896,481880,272317,626979,715477,900137,132120,946449,165223,575745,296731,293967,507058,186672,502081,991140,615782,201009,142259,325445,877412,302771,304459,11160,39680,674258,849233,924976,681976,373662,946368,944662,497407,249490,107009,632637,325304,811294,540333,571659}

    421747

    417961

    Returns: 25921341

  53. {39183,942551,862129,927966,198110,873317,759461,800414,402951,448426,73583,754250,492128,689998,297762,960834,726901,166244,699326,853072,658813,178866,834934,868211,59556,999598,91690,6618,281602,820605,285293,628576,270945,324406,931454,673940,654139,73564,398866,919347,477433,901351,365641,804970,790900,802491,956915,475800,437686,660974}

    341844

    292157

    Returns: 28636138

  54. {204601,59845,241179,683580,432229,481142,545516,157725,887958,641638,967318,294474,204690,939436,865371,621264,992791,450636,881327,662510,521546,291067,396210,594769,651912,150560,795124,459669,920663,893647,387960,901898,592691,914575,338992,621035,783558,890262,539387,323495,213224,112198,33838,802395,924003,998521,266952,804757,592945,348849}

    814267

    744856

    Returns: 28281932

  55. {402107,29797,453353,650751,913562,247100,715556,540218,18584,154120,392619,573713,506350,39185,622131,91649,63238,398347,214939,241080,854970,955230,438133,281107,223443,550685,511939,421087,573322,659726,868726,495963,631433,753255,630512,112756,608875,766862,881538,925190,412342,541528,650606,400480,212711,436937,389733,279038,538853,949401}

    748489

    4792

    Returns: 43061188

  56. {925194,215404,422507,922930,284897,515864,752589,181362,927459,629282,295648,51852,719864,230144,281286,540655,670651,931799,810896,275128,170100,153086,7808,918005,817054,822073,393735,205027,545443,841981,539846,81712,406810,582897,329488,532919,30095,652137,139174,347786,548667,472748,57017,64867,470662,419888,531883,975986,713802,158488}

    634188

    367021

    Returns: 25665397

  57. {972753,407739,275424,725649,873558,878047,64342,217069,579904,52856,216210,833557,768297,811437,659556,754276,382683,428562,918350,213354,106769,210734,243904,55842,201522,476534,154014,687675,703896,312400,902008,862738,597517,951824,233807,551860,487499,577276,55190,238688,71675,396938,759278,605570,927031,238624,42279,908409,588103,345042}

    629637

    284048

    Returns: 29075896

  58. {335142,960167,330744,227720,682941,166804,790241,106508,608422,457534,486738,935930,81769,11642,210510,705055,569536,923024,440004,584569,419350,334644,214360,940279,417027,3529,723865,704052,537297,645225,777866,80959,30779,516247,88797,843156,458023,161160,245043,501411,364081,459363,873436,743432,202723,458941,502299,979216,192181,695067}

    294433

    177362

    Returns: 24548028

  59. {23504,680884,563153,542065,446607,669162,10170,913494,926524,312599,255135,347251,541710,577789,348978,457672,6320,644436,644627,204866,323709,25408,192661,427453,608508,810967,469496,391817,266087,994910,950382,534880,151721,445194,400089,793523,836826,440131,758155,729055,3203,590812,180932,451952,406752,874460,587702,563235,936472,352566}

    277059

    70854

    Returns: 28766786

  60. {358471,53908,995005,681306,174644,99399,601507,318728,605593,729495,836074,344750,720929,151544,481456,42557,927076,846674,953866,213967,914475,688823,189175,333554,908402,588721,607017,842532,953440,212209,625026,484052,468624,543326,185619,389021,840202,165198,516830,420942,412298,65864,348948,795429,355191,809469,627095,220940,120300,482648}

    163320

    22701

    Returns: 28263490

  61. {358577,333867,432121,670396,876418,64892,850570,398285,473222,733889,103759,759495,619736,457439,507736,534856,349633,523629,221287,816155,693178,201902,499117,781568,291245,684762,720460,901988,432179,907157,339797,799395,548184,349557,769098,982860,109713,63423,505755,142493,135243,844264,421356,611842,135776,114520,800973,326553,449366,142818}

    366144

    57967

    Returns: 32521282

  62. {166249,948173,69366,937668,476866,721421,196049,242882,491067,295945,16545,122696,632412,623061,770474,982053,856096,735993,921820,337811,580912,664616,283992,117380,564198,60232,357745,100945,564042,250991,149863,331915,547543,84450,360749,900205,214326,574487,551971,948007,829056,564596,954204,593748,114879,203406,910233,188355,12781,490473}

    446090

    99477

    Returns: 30960139

  63. {547956,801789,207122,866764,614315,420206,599555,323953,694365,41682,899998,587629,395140,937710,479763,660159,385864,122424,26181,494355,107269,499605,202374,113928,402882,719580,467798,21930,278458,347473,620457,338614,386838,635242,413277,936283,124527,965515,753285,463479,974031,804749,237027,242838,425072,189426,854633,206583,2811,278449}

    600375

    295734

    Returns: 26870136

  64. {599560,49326,423392,521057,418148,835266,851619,261334,775749,100208,439669,220450,511575,866221,577845,592882,545970,789024,982261,952677,698592,90206,713912,671495,613530,457515,108205,821399,562060,437439,709111,577600,126987,774847,281575,974690,182628,113919,664831,392266,818000,191301,671089,66484,821751,874184,214301,203792,426100,145452}

    62485

    35361

    Returns: 25958633

  65. {63376,769799,369243,536511,709316,488989,701473,108317,525819,414310,493959,295874,28941,591750,631903,345418,294340,379155,832299,545861,655001,413970,694748,170158,829686,7802,448852,68725,23350,676782,575395,878516,40223,811653,723214,568317,914029,868997,613763,218250,583626,218595,65764,512969,708365,610244,396869,469081,484290,100030}

    117029

    28036

    Returns: 24845628

  66. {858274,370710,85366,379919,12949,613762,376922,554911,692533,670503,38818,150679,730062,54747,138127,138882,9237,20837,658644,529438,521400,148855,82514,544024,439117,811449,915098,474447,932384,776448,800366,320463,710377,727633,964799,993110,240338,749793,833774,929299,302837,121176,907022,250913,522843,692618,199712,913102,971132,853371}

    782677

    493143

    Returns: 28285596

  67. {221380,440034,462350,869934,75020,625381,43550,713772,111453,844697,321606,140191,73776,956162,715063,432262,473071,729816,398417,526348,274611,930944,115945,65169,810438,469901,881023,37538,773922,822664,512387,201276,309553,357924,637850,547659,922697,98696,124753,832176,234168,193928,27628,478326,198261,46123,232605,707675,63529,902502}

    197061

    48977

    Returns: 25048001

  68. {477040,159902,378037,575784,240977,740009,91502,726204,684743,190156,372322,414789,344443,912061,494388,959792,319558,276066,269939,472858,900467,580239,583138,787795,397178,919819,993843,307416,5700,356363,1414,494933,846828,288179,661998,635943,399035,247579,771435,834717,226987,350279,598064,887924,661092,626413,431773,552539,346818,523955}

    563461

    542859

    Returns: 25320433

  69. {195916,860013,720359,781624,244028,825249,735288,885307,361021,374535,228631,500643,769576,765120,98391,260748,190916,87844,895800,577094,536718,207994,812460,578892,432685,543285,335381,417549,407420,276283,829508,604838,105797,535074,751419,236452,244799,717488,224300,187590,156245,143833,166775,771960,149218,488964,237806,77977,426604,939909}

    81171

    42066

    Returns: 23287585

  70. {461040,575843,800215,415114,379605,444819,670556,226438,484278,415866,697651,159045,846684,330734,84831,90775,747585,69941,131918,900856,420045,816322,458469,899541,629531,458174,468981,553548,401651,255485,269758,842603,168785,297156,827698,805679,998748,500488,966195,521734,13102,212848,799441,906573,80147,199697,840081,572049,323904,677808}

    967265

    124659

    Returns: 43863306

  71. {350,636,897,298,829,877,624,131,778,590,493,80,25,693,29,764,193,381,143,320,94,192,39,467,397,542,690,355,598,595,607,927,228,638,459,528,950,762,931,520,890,311,709,777,196,576,62,805,802,782}

    941

    746

    Returns: 25970

  72. {51,923,973,424,729,999,158,980,908,742,356,879,34,247,124,316,919,629,470,293,241,336,605,658,502,107,750,565,763,167,954,816,470,373,820,788,803,320,801,84,162,320,824,638,190,447,693,784,951,103}

    247

    164

    Returns: 27907

  73. {240,127,627,177,559,389,334,740,540,95,494,475,129,319,56,184,77,520,274,930,374,298,642,461,562,78,700,250,229,784,895,210,453,159,888,599,664,709,188,810,866,629,208,701,739,815,332,393,158,486}

    627

    94

    Returns: 35885

  74. {530,721,883,11,572,892,962,948,378,239,54,908,826,812,956,612,606,813,609,999,440,210,354,878,668,599,999,98,38,467,995,20,300,313,180,832,854,425,248,196,406,302,476,724,100,41,535,713,149,404}

    381

    26

    Returns: 35198

  75. {941,887,635,550,732,13,256,890,613,103,369,128,367,295,660,996}

    824

    242

    Returns: 10822

  76. {25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000 }

    1440

    360

    Returns: 16945

  77. {2, 2, 2, 2 }

    24

    1

    Returns: 73

  78. {25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000, 5000, 6000 }

    1450

    360

    Returns: 28865

  79. {386291, 290658, 179663, 994703, 477306, 352469, 989725, 782832, 147750, 215895, 164052, 919433, 5166, 393507, 358604, 319473, 441608, 28271, 996323, 908552, 817510, 601232, 445385, 357108, 275754, 92737, 855739, 131797, 875150, 420453, 675673, 851897, 592954, 814385, 246169, 916093, 887586, 157222, 27985, 373788, 935608, 217798, 954921, 55138, 361104, 136088, 126416, 45290, 260959, 480070 }

    553640

    382472

    Returns: 23890578

  80. {25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000 }

    1440

    37

    Returns: 20148

  81. {21312, 34534, 124434, 254356, 345477, 12367, 152457, 12354, 2450, 7654, 32456, 45823, 949999, 214312, 344534, 142834, 25356, 344877, 123467, 142457, 184354, 245480, 76454, 32486, 45623, 99999, 28312, 34534, 12384, 25356, 34577, 12367, 12857, 123544, 24450, 76354, 32456, 456323, 999999, 23312, 34834, 12334, 25356, 34277, 12367, 12457, 12354, 2450, 7654, 325456 }

    935235

    334555

    Returns: 10944111

  82. {2, 2, 1 }

    24

    1

    Returns: 26

  83. {41, 18467, 6334, 26500, 19169, 15724, 11478, 29358, 26962, 24464, 5705, 28145, 23281, 16827, 9961, 491, 2995, 11942, 4827, 5436, 32391, 14604, 3902, 153, 292, 12382, 17421, 18716, 19718, 19895, 5447, 21726, 14771, 11538, 1869, 19912, 25667, 26299, 17035, 9894, 28703, 23811, 31322, 30333, 17673, 4664, 15141, 7711, 28253, 6868 }

    1000000

    123456

    Returns: 5084900

  84. {25, 500, 630, 250000, 1000, 350, 22, 58, 1, 400, 500000, 5000 }

    1440

    360

    Returns: 762865

  85. {999999, 996999, 999499, 999399, 999199, 999969, 999099, 999969, 1000000, 999999, 999999, 1, 3, 214215, 999999, 996999, 999499, 999399, 999199, 999969, 999099, 999969, 1000000, 999999, 999999, 1, 3, 214215, 999999, 996999, 999499, 999399, 999199, 999969, 999099, 999969, 1000000, 999999 }

    1000000

    1000000

    Returns: 32410829

  86. {12, 2, 9, 4, 10 }

    12

    6

    Returns: 37

  87. {446468, 411850, 481085, 941043, 559453, 388802, 364571, 313292, 116166, 65005, 316340, 286473, 390194, 119612, 928013, 894594, 129836, 441904, 590690, 813863, 900731, 261402, 979707, 6842, 387112, 489122, 306939, 707619, 423883, 912934, 278813, 404106, 60988, 948, 396348, 449303, 907730, 9469, 596733, 618536, 985720, 383208, 23414, 922684, 119378, 399158, 774602, 648365, 315241, 162252 }

    100000

    50000

    Returns: 23230446

  88. {6, 4, 3 }

    8

    7

    Returns: 13

  89. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    999999

    1

    Returns: 73999928

  90. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    1000

    1

    Returns: 50000000

  91. {4, 20 }

    24

    8

    Returns: 24

  92. {4, 1, 5 }

    10

    4

    Returns: 11

  93. {5, 5, 5 }

    24

    8

    Returns: 26

  94. {2, 1, 3 }

    10

    2

    Returns: 11

  95. {383, 886, 777, 915, 793, 335, 386, 492, 649, 421, 362, 27, 690, 59, 763, 926, 540, 426, 172, 736, 211, 368, 567, 429, 782, 530, 862, 123, 67, 135, 929, 802, 22, 58, 69, 167, 393, 456, 11, 42, 229, 373, 421, 919, 784, 537, 198, 324, 315, 370 }

    2300

    1500

    Returns: 27369

  96. {999929, 992999, 999999, 999992 }

    1000000

    1000000

    Returns: 3992919

  97. {1 }

    1

    1

    Returns: 1

  98. {5, 2, 2 }

    24

    4

    Returns: 9

  99. {999999, 999997, 1989, 7, 15, 199993, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 999995, 123456, 123456, 123456, 123456, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 543126, 12312 }

    31

    10

    Returns: 33855246

  100. {1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 2, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 8, 9, 6, 5, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6, 1, 2, 500000 }

    1000000

    499999

    Returns: 500181

  101. {58284, 4285, 275822, 58382, 100000, 1, 1, 28, 5726, 4582, 5725, 8, 1, 2, 5, 1825, 28572 }

    10000

    1000

    Returns: 577284

  102. {1000000, 1000000, 1000000, 1000000 }

    999

    1

    Returns: 4000997

  103. {10, 52, 11, 100, 34, 52, 90, 12, 330, 402, 526, 988, 155, 33, 12, 312, 1, 25, 3, 58, 44, 98, 55, 55, 65, 85, 88, 99, 547, 6, 3, 2, 1, 58, 5, 5, 6, 8, 8, 8, 9, 45, 65, 66, 54, 25, 88, 95, 65, 645 }

    396

    215

    Returns: 6603

  104. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    999999

    500000

    Returns: 50000000

  105. {1, 1, 1, 2 }

    24

    3

    Returns: 24

  106. {3434, 2332, 21223, 122, 1, 232, 1244, 5334, 1, 1, 1, 1, 1, 1, 1, 1, 2, 12, 2, 2, 2, 2, 3, 3, 3, 4, 4554, 34545, 34443, 3223, 22222, 345644, 32334, 33425, 66754 }

    100

    50

    Returns: 611284

  107. {999999, 999999, 99999, 999999, 99999, 9999, 9999, 999, 99999, 9999, 999999 }

    1000000

    99999

    Returns: 6009996

  108. {914, 550, 84, 947, 309, 277, 84, 82, 523, 278, 57 }

    452

    382

    Returns: 4105

  109. {1, 25, 2 }

    24

    3

    Returns: 28

  110. {200, 200, 200 }

    3

    2

    Returns: 600

  111. {500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001, 500001 }

    1000000

    500000

    Returns: 49000001

  112. {100, 9500, 999 }

    10000

    1000

    Returns: 10599

  113. {25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000, 1131, 131, 1313, 133, 133, 133, 343, 344 }

    1347

    131

    Returns: 26834

  114. {4, 8, 3 }

    1000000

    10000

    Returns: 15

  115. {10, 4, 5, 2 }

    4

    2

    Returns: 21

  116. {25, 25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000 }

    1440

    360

    Returns: 16970

  117. {1000000 }

    24

    1

    Returns: 1000000

  118. {2, 2, 4, 1 }

    7

    3

    Returns: 9

  119. {2, 1, 3, 5 }

    10

    5

    Returns: 11

  120. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    734234

    334212

    Returns: 54796402

  121. {4, 32, 49, 48, 16, 4, 48 }

    24

    8

    Returns: 216

  122. {2, 2, 5 }

    4

    2

    Returns: 9

  123. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    1

    1

    Returns: 50000000

  124. {1000000 }

    1

    1

    Returns: 1000000

  125. {1, 5, 4 }

    12

    7

    Returns: 10

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

    24

    8

    Returns: 20

  127. {25, 25, 25, 25, 25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000 }

    1440

    360

    Returns: 17045

  128. {3, 2, 2, 5 }

    10

    4

    Returns: 13

  129. {25, 500, 630, 2500, 1000, 350, 22, 58, 100, 400, 500, 5000, 6788, 78985, 555, 555555, 5555, 5555, 5555, 55555, 5555, 2345 }

    1000000

    999999

    Returns: 733088

  130. {1, 2, 40, 40 }

    7

    4

    Returns: 83

  131. {1, 1, 10 }

    13

    3

    Returns: 12

  132. {4, 3, 4, 5 }

    24

    8

    Returns: 27

  133. {100, 5, 8, 23, 12, 14, 24, 5 }

    36

    16

    Returns: 210

  134. {2, 4, 16 }

    24

    8

    Returns: 22

  135. {4, 20, 4 }

    24

    8

    Returns: 28

  136. {1, 1000000, 1000000, 1000000, 1000000 }

    2

    1

    Returns: 4000001

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: