Statistics

Problem Statement for "ProgrammingDevice"

Problem Statement

You work in a company that produces measuring devices. The software for each device is stored in reprogrammable memory. To program a device, you must connect it to a personal computer and transmit data to the device's reprogrammable memory through a serial interface. Your task is to make this process as efficient as possible.

You are given two int[]s offset and size. Each corresponding pair of elements in offset and size describes a piece of data that must be transmitted to the device. The i-th piece of data consists of size[i] consecutive bytes that must be written starting at the address in offset[i]. To successfully program a device, you must write every piece of the given data. Memory addresses that are not referenced in this data are not important - so you can write anything to those addresses, or write nothing at all to them.

Data is transmitted from the computer to the device through packets. Each packet can contain a maximum of maxData bytes of consecutive data that will be written to a specified memory address. Return the minimum possible total number of packets required to transmit all of the given data to the device.

Definition

Class:
ProgrammingDevice
Method:
minPackets
Parameters:
int[], int[], int
Returns:
int
Method signature:
int minPackets(int[] offset, int[] size, int maxData)
(be sure your method is public)

Notes

  • Assume that the reprogrammable memory of the measuring device is infinitely large.

Constraints

  • offset will contain between 1 and 50 elements, inclusive.
  • offset and size will contain the same number of elements.
  • Each element of offset will be between 0 and 1,000,000,000, inclusive.
  • Each element of size will be between 1 and 1,000,000,000, inclusive.
  • None of the pieces of data described by offset and size will overlap.
  • maxData will be between 1 and 2,000,000,000, inclusive.

Examples

  1. {0, 10, 20, 30}

    {8, 5, 3, 11}

    6

    Returns: 6

    Send 15 bytes starting from offset 0 in 3 packets. Only 13 of those 15 bytes are meaningful. There are 2 dummy bytes starting from offset 8. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 6 packets are sent.

  2. {0, 10, 20, 30}

    {8, 2, 3, 11}

    6

    Returns: 5

    Send 12 bytes starting from offset 0 in 2 packets. Then, send 3 bytes starting from offset 20 in 1 packet. Finally, send 11 bytes starting from offset 30 in 2 packets. A total of 5 packets are sent.

  3. {15, 95}

    {1, 20}

    100

    Returns: 1

  4. {77, 7777, 777}

    {700, 70000, 7000}

    1

    Returns: 77700

  5. {50,10}

    {100, 35}

    7

    Returns: 20

  6. {0,1000000000}

    {1000000000,1000000000}

    2000000000

    Returns: 1

  7. {0,1000000000}

    {1000000000,1000000000}

    1

    Returns: 2000000000

  8. {0,1000000000}

    {999999990,1000000000}

    2000000000

    Returns: 1

  9. {0,1000000000}

    {999999990,1000000000}

    1000001000

    Returns: 2

  10. {745805579,676874121,379656197,848113610,89587158,451523175,550,147380788,938736125,532882074,738566487,329594432,822596439,621115948,115131131,948154911,421264571,155842622,244574963,15931562,586844424}

    {11499137,9393821,4302149,14626991,10630027,14009930,11051113,8222075,26104,15608095,914594,6362715,14841524,13998693,14029867,14765012,15306666,8562181,8069123,13273431,9582221}

    42266312

    Returns: 15

  11. {707247239,569205780,26931382,431}

    {7066980,12085965,4513495,14513012}

    715276339

    Returns: 1

  12. {149,721992119}

    {10392251,1588905}

    510909561

    Returns: 2

  13. {955600405,824,629723063}

    {6248574,14632307,2697668}

    735293618

    Returns: 2

  14. {273463461,138}

    {5641257,14936313}

    986263102

    Returns: 1

  15. {186592286,155634176,92327797,468,114545882,161976449,32362083,99904667,227570737,95157915,40399859,19146625,184332965,21134641,35729150,213325026,116732115,131139098,176689682,124265668,179872145,109495529,89669678,172657842,207018619,26674390,11452339,166219863,148803649,143309911,50836650,7867600,199722804,49012180,39370322,162234598,122241199,212294459,78206689,69522609,222977071,74175741,192626728,82402724,168924888,59557889,137486694,46720965,192292149,5530094}

    {5692360,6309643,2761707,5482172,2125173,257554,3365044,9571939,5909045,4675851,6248464,1913653,2227140,5503398,3592201,9630636,5442994,6320069,3109932,6825131,4384669,5013905,2623745,3988500,5219077,5624489,7688727,2691283,6769904,5447928,8697133,3551188,7291293,1816292,1011111,3952469,2005766,999882,4169349,4650030,4587707,3956264,7067626,7218024,3692588,9928929,5778689,2264481,296961,2261365}

    26383

    Returns: 8802

  16. {148278816,23848475,161306270,184310969,186063694,91386709,106193212,185781746,60511321,171839804,63817406,105702250,82480963,116146888,84656332,18282073,35320171,136307964,64025541,77606022,150685455,126151900,46672461,44211391,7482709,189959987,31422093,153710148,95124134,171775323,57906989,65877791,921,22815824,132676359,70138506,94455700,140235319,120922140,121357561,122187741,51514852,44631999,175127799,34947695,16873811,141289549,35141604,102220434,165956363}

    {2382937,7568997,4618509,1442934,3869649,3036798,9936045,270388,3298850,3280962,197802,482448,2140905,4743566,6711087,4529611,8889494,3903045,1832488,4865222,2993403,6495625,4829298,395001,9364019,2098989,3518062,7592274,7091173,56125,2590875,4235761,7463567,1023391,3629175,7438289,651985,1042299,407054,800866,3938189,6373605,2022654,9169638,179556,1388911,6960431,171109,3473306,5800907}

    11738

    Returns: 16312

  17. {198822800,121808162,226378898,98088415,105215218,115937983,81501299,206881107,241001975,33189353,752,27543543,68474849,46341826,126386166,173196799,93583635,183088172,199143587,174830678,164587713,134863880,236012353,36498443,8861884,76131627,126955190,13242841,137156013,91061841,2056079,213196081,98802691,113103870,96325564,52976638,29993196,194221949,19846765,65047321,247584786,161453586,167645145,140282295,146866896,56322870,190017876,222303418,62487817,153937399}

    {318078,4573711,9632326,710722,7884419,5865300,9558443,6314379,6580882,3305402,2052699,2443759,7652258,6631643,568175,1631555,2740474,6929018,7733613,8254462,3056951,2288765,4987790,9838407,4379231,5368972,7903070,6603850,3122125,2518239,6802544,9107329,6408764,2831144,1761089,3343102,3194052,4597980,7691398,3426521,2574370,3129150,5549568,6581154,7068048,6159238,4199046,4073090,2553961,7513547}

    1965

    Returns: 127254

  18. {10829423,165309115,197095487,180965733,139289762,123091649,56757534,14627146,45309480,144935983,81945547,165556224,40170981,190876793,129628667,152468162,35202847,43667844,84964923,90415206,133542128,136099831,193102949,7009481,48591135,152258644,3872562,67402502,169173290,22467436,107810583,254,27859561,190631061,125063867,101400242,161701906,115326251,204567842,96410876,140175980,154772761,74696385,62820845,205346384,8013367,84371949,39439662,174341283,9427054}

    {3773373,242386,7448298,9628316,846268,1912312,6054184,7768937,3231091,7266543,2381598,3571061,3462617,2188048,3886270,2263606,4167613,1632861,5405125,5947542,2519013,3164252,3942483,957758,8150238,154212,3096692,7288404,5108316,5325428,7477924,3814715,7282502,196153,4527709,6398723,3600478,7711249,777554,4920620,4717144,6898089,7229676,4554727,5682905,1353839,517931,661900,6600375,1392751}

    25590

    Returns: 8196

  19. {121110230,68950233,17341301,411,213774510,174235470,13887186,109272087,91095016,79220225,82946221,142759116,11488744,77040202,156421687,46953210,135234408,115162195,219427467,24080492,62811131,180906280,187461964,44294714,13740236,179830532,63238336,40531041,53446234,210668336,8030876,164327017,127362239,101075186,197182017,68758781,106046784,120240233,74818245,202639091,67527389,194260571,148926822,148964011,32061433,64332664,173473638,95042934,149241972,186557362}

    {6205069,5823011,6738394,7995288,5626032,5575282,3413319,5851806,3913048,3700935,8122621,6137931,2239712,2151875,7858580,6487592,7521317,5057394,3805915,7972254,418547,5612568,6752617,2618850,103964,1040302,1090339,3728077,9361346,3086261,3431578,9124789,7867322,4927244,5410712,158774,3221472,864926,2204132,8021790,1223905,2875267,7899,248482,8455364,3180210,719299,5987163,7149156,881147}

    15889

    Returns: 13991

  20. {418469424,421460020,257300272,200800106,120018735,99175916,348095753,320283030,91563609,270280275,6740199,468999883,70263672,88243530,382,59017634,228163584,369844075,331163533,310381732,85235924,132777822,106244584,377313110,340061854,458060381,28849306,380441262,47071872,188390159,409125853,359997162,177313371,77446073,147015200,238647761,426266880,286244457,20179747,36660158,301741991,217715321,162716114,383184986,403102383,352040611,440485993,390034794,206749888,141329901}

    {2220008,4173000,7057182,1273932,2830159,5252377,2020038,8327176,5347827,7180524,7629768,3826469,4116878,1080832,5635502,4077742,8359005,5692504,2588679,4453371,2342096,6436578,5077019,18221,2085082,4485428,6158990,686224,6442365,9648241,6331242,4541398,5065908,4197651,5794222,9522862,5500320,7633658,3367204,733070,2861053,5434359,7425314,4622669,265646,5265269,7943753,3665534,1393495,4240524}

    1

    Returns: 232328368

  21. {241094466,15656330,7215773,129355065,414073267,222281854,406297120,99085587,73110946,328328766,46098317,340350867,229271597,471800803,89569316,201034118,176607780,421899036,166967750,382739228,264757923,289110156,444990452,234738330,193385615,258908618,57190751,28272517,434844620,80114904,257106658,36820096,374906096,148786256,833,270511991,159220520,457044837,362760759,186865917,296607077,279910022,115236839,106939807,353392617,427310184,135093310,211989970,312413088,392007835}

    {9195538,9458934,2350187,2400381,1708964,774706,4520615,5091348,4712369,5413176,7783886,5146151,462326,307660,9090339,1572177,3384834,1677832,83555,2221571,5475957,3743362,5247216,5865910,6476048,1421493,7287532,7190847,6409283,3909237,1781273,7249246,5034598,4483408,517434,2229601,1136606,4951101,8791837,207980,9812326,6800976,7199699,846743,5990357,6081690,6623643,3512860,9352920,5456127}

    1

    Returns: 228443859

  22. {457355266,197689951,67894519,88503282,315121779,14602765,390271266,413736150,170012228,237365249,262366722,382422380,465405661,110440998,285901585,106760826,78243124,186248504,292894361,435386104,45769413,271161544,446715589,343297005,462,502794009,368594764,35678838,402863627,222038985,426578047,118201955,38788291,28338231,491403245,161859640,330960182,469941169,302521249,104735148,445568235,362059036,250079695,53610699,310124378,127501177,479822744,353669624,207835844,145939433}

    {1981440,2054522,5515426,6903969,7928764,9929412,3620124,5391421,7431448,4308498,647191,2951824,3449011,34581,2341415,3284599,5767212,6258711,7654392,2483789,2274123,6229750,6581775,2637480,8933900,3814558,6055883,1854035,4290967,9913101,5785018,744192,5858365,6252126,1468496,3211844,4248137,1188312,3428155,372869,693451,1489672,6567887,6626377,973917,9726247,5232871,5991748,6711454,8875734}

    1

    Returns: 227970193

  23. {76876997,62532060,31823950,5468,49173606,68842476,5514746,34586871,86514769,34586386,9108436,9447,74649592,10104,5515260,76882240,51299369,51302693,71538250,51301430,74648347,44159128,31822790,71537010,76880862,5513549,8399,68844429,62530973,57082683,13191870,7194,76880304,11374740,9107592,68842887,51300727,76881359,31821278,31819003,86513233,31820255,76879286,31822108,71536323,21889487,51303877,9109490,76878204,6371}

    {566,6309643,2761707,356,2125173,66,126,9571939,5909045,187,736,397,2227140,5503398,3592201,9630636,336,575,3109932,559,275,5013905,87,730,141,523,223,2691283,672,5447928,8697133,642,419,1816292,483,745,588,70,293,742,599,20,650,378,682,9928929,5778689,2264481,735,255}

    383

    Returns: 241255

  24. {87630470,21368263,100603161,123479957,123483092,62269689,72841372,123480462,44612707,111028072,47911784,72839064,55555013,82778151,55557297,16835511,28945620,87623527,48111378,55554123,90014716,83991403,38235396,37836893,7467988,123484778,28939003,93008967,62271526,111025440,44612375,48112271,2921,21365237,83992987,48114393,62269762,87625842,82780187,83187492,83989611,38237168,38232470,114309211,28940741,16833666,87626971,28943463,69364538,105223244}

    {2382937,7568997,4618509,14,729,18,9936045,1464,3298850,3280962,197802,472,833,282,6711087,4529611,8889494,1129,776,578,2993403,605,1102,395001,9364019,2098989,910,7592274,7091173,917,127,125,7463567,1355,3629175,7438289,1121,775,407054,800866,1129,6373605,1086,9169638,1344,651,1395,1269,3473306,5800907}

    738

    Returns: 170112

  25. {108219895,52918241,135456207,50073743,50079941,52915624,40507665,115958211,145090410,16567390,5752,16561090,35135616,26411982,52920908,89528784,50069596,99419302,108222478,91162312,80921123,53494407,145088556,16572030,8863387,35137592,53491216,8865967,53497523,50068054,2060401,122272725,50077652,50084085,50072714,26415047,16564248,103621845,8866899,35133404,151673022,77791443,83979015,56622538,63206256,26417843,99420488,131380568,32577781,70277192}

    {1450,1299,9632326,1354,1457,438,9558443,6314379,6580882,1896,2052699,1467,762,1769,568175,1631555,1206,890,7733613,8254462,3056951,1011,1078,9838407,1367,5368972,1490,424,3122125,625,6802544,9107329,352,2831144,877,1594,528,4597980,7691398,1617,894,3129150,5549568,6581154,7068048,6159238,4199046,4073090,2553961,7513547}

    965

    Returns: 157116

  26. {15622,76059271,89835531,76064451,66734732,59133131,33416930,17164,22034266,66737088,39476353,76059591,20398584,85890399,61048481,66894726,20395883,20399754,41860505,41861816,61049612,63570393,85892559,11186,25265516,66738784,9351,39473548,76061527,7786670,59130762,7254,13113378,85693542,61045647,52731826,76057640,59132201,97285172,47810080,66735191,69158972,39474194,39471866,98063146,12374,41858882,20397465,76063205,13333}

    {849,230,7448298,9628316,220,1912312,6054184,7768937,3231091,867,2381598,261,789,768,614,2263606,309,1632861,337,5947542,2519013,3164252,3942483,986,8150238,154212,756,132,416,5325428,264,771,7282502,196153,1177,6398723,422,249,777554,4920620,760,6898089,524,839,1097,707,851,4,555,835}

    590

    Returns: 166151

  27. {59553040,29891308,10257016,9411,103624489,90578785,10253044,47771976,43849869,35721758,35725597,67429587,8009946,35718916,80731395,18721053,67425526,53625846,109252104,10259241,28084909,91621303,92505881,18719444,10251747,90580952,28504003,18716166,18723136,100537719,8006454,80733719,59557255,47767206,92512231,29732286,47769879,58685455,35716085,92514740,28507768,92508555,73569676,73580050,10259614,28506151,89859096,47765095,73582111,91622609}

    {1761,5823011,1388,7995288,5626032,552,1331,5851806,3913048,1697,8122621,6137931,2239712,471,460,310,1723,5057394,1641,74,418547,208,1083,1220,1194,1040302,511,1523,9361346,3086261,1762,9124789,7867322,1222,484,158774,260,864926,472,8021790,1223905,1593,7899,780,8455364,184,719299,637,7149156,881147}

    889

    Returns: 122822

  28. {249,1427,1046,1188,993,1398,903,713,513,1850,2209,909,294,466,758,827,2139,187,59,1696,2373,2533,1195,136,357,1515,2065,2071,522,547,2292,1121,826,1387,1254,2456,562,1616,1763,1550,425,2343,732,1935,1330,1025,633,2013,0,940}

    {34,75,63,3,30,22,4,5,3,75,75,22,61,37,55,76,58,58,72,62,80,33,58,46,60,34,2,57,21,12,45,57,1,6,76,77,61,68,78,55,27,29,13,75,50,9,73,43,57,51}

    10

    Returns: 243

  29. {173,159,118,18,91,14,104,71,57,67,187,93,0,110,202,149,148,96,137,131,142,25,175,199,87,45,143,64,156,75,37,183,133,124,141,154,29,129,53,209,167,6,83,192,195,9,140,145,66,7}

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

    1

    Returns: 213

  30. {168,7,91,1154,631,792,1254,842,918,447,607,297,981,354,542,1233,893,1056,135,95,49,477,496,330,271,1142,1167,593,732,1092,1188,964,242,45,0,401,741,825,912,640,1017,693,646,572,202,1050,714,1113,723,1025}

    {32,30,3,13,7,31,31,47,38,22,20,25,36,46,25,19,16,28,27,37,38,14,45,21,19,9,16,6,4,17,42,16,25,2,7,43,46,10,1,2,3,18,40,20,35,4,3,25,1,20}

    6

    Returns: 199

  31. {345,459,323,605,188,769,554,269,675,532,98,478,669,133,835,420,695,833,762,649,619,382,52,502,19,0,714,511,264,244,737,854,330,589,389,800,360,568,353,153,179,223,65,848,434,495,37,449,288,526}

    {4,16,3,12,31,29,9,19,17,18,31,13,4,16,10,10,14,2,4,20,26,3,8,9,16,17,23,15,1,19,20,15,12,11,30,29,18,18,2,22,6,20,29,2,13,5,11,10,32,3}

    4

    Returns: 197

  32. {90,811,423,1524,1174,549,1466,309,472,1000,390,1067,948,1504,935,219,502,1146,622,1611,1247,1058,178,165,570,0,858,362,135,1366,1272,276,1208,1456,1315,940,35,888,589,1573,149,754,661,1292,1125,910,719,255,1407,399}

    {36,44,44,46,26,21,34,49,26,51,7,56,52,12,3,35,46,21,31,45,22,6,41,12,14,30,25,21,8,40,11,30,37,10,50,5,51,15,26,29,10,52,53,17,14,16,29,19,47,20}

    7

    Returns: 224

  33. {1193,2066,868,1601,723,1210,1575,3,39,991,1930,1774,1402,2447,1657,1853,2208,267,2136,222,2369,683,1433,949,552,2289,374,1108,93,289,152,783,1798,1553,2051,671,1749,1979,1333,1076,985,1499,1278,1378,0,1415,621,1785,522,445}

    {9,63,75,45,54,62,12,24,51,77,35,7,11,2,78,77,80,11,71,45,73,40,56,32,61,74,58,75,45,73,68,76,44,22,1,3,20,68,35,29,3,49,46,15,1,9,50,8,29,67}

    10

    Returns: 229

  34. {1836,393,1447,1561,0,4,1485,1633,1265,1544,1327,1233,1036,1905,132,2000,137,164,1570,42,735,1336,1413,97,210,582,1530,1682,184,842,1215,784,1978,514,1182,465,713,762,1093,1752,1132,333,1384,997,1820,658,915,284,896,922}

    {59,61,33,7,2,37,44,49,53,15,8,30,53,69,1,68,17,16,57,48,22,46,30,25,63,71,12,69,23,52,17,53,17,62,28,47,18,14,29,56,40,49,23,27,12,52,2,43,12,65}

    9

    Returns: 215

  35. {1457,1270,0,255,629,170,1340,1722,1924,1892,707,1153,2237,546,100,850,1362,908,1707,1858,1194,623,2072,1179,889,465,795,588,1782,1064,1517,1425,82,1075,1580,2128,1556,2146,1619,1666,357,942,272,982,42,417,1131,146,1990,420}

    {46,58,40,6,72,74,9,59,59,29,80,13,64,42,39,28,63,33,5,32,63,1,55,10,14,77,55,26,63,10,28,22,8,42,26,10,15,80,39,35,50,32,72,80,34,2,17,18,70,34}

    10

    Returns: 209

  36. {1880,929,1698,253,1343,825,1921,1722,109,169,1465,476,718,1624,1511,461,0,153,737,1817,297,667,533,984,883,1760,1558,1030,186,446,1246,1119,362,1207,1068,599,228,1672,1968,564,31,1402,1286,778,373,51,1148,395,901,1855}

    {41,53,19,35,55,58,44,27,41,8,42,53,16,48,38,4,30,16,36,29,56,43,28,37,7,57,61,32,37,5,31,21,3,35,46,62,14,17,24,25,14,57,55,47,21,54,53,43,25,17}

    8

    Returns: 231

  37. {1134,1168,88,588,617,808,457,1097,722,186,0,11,886,966,279,996,685,912,852,302,625,123,1175,365,268,794,556,256,443,519,46,926,761,1041,1062,502,643,1057,399,1092,251,947,37,80,332,565,1189,209,217,144}

    {34,4,35,27,8,38,40,31,37,17,6,24,23,26,19,40,32,11,33,29,13,15,11,32,10,12,9,6,13,37,34,20,32,10,27,12,39,3,40,3,1,17,7,4,32,17,13,7,34,37}

    5

    Returns: 227

  38. {740,61,696,518,291,302,569,315,658,451,352,150,610,684,828,373,481,827,857,703,708,784,0,50,845,118,381,325,565,209,584,221,182,82,224,662,257,771,23,802,429,368,722,280,863,492,545,413,632,11}

    {31,16,6,27,8,12,13,5,1,30,11,32,17,9,17,7,10,1,4,4,10,13,7,8,9,28,31,22,2,9,26,2,24,31,29,18,21,11,27,25,19,1,14,6,14,22,19,14,26,10}

    4

    Returns: 203

  39. {270,527,1017,804,1029,255,674,1066,861,460,611,298,409,308,198,432,577,835,652,202,722,982,944,547,393,906,335,784,356,1082,93,505,1070,1106,1149,398,0,742,96,157,29,726,416,269,244,679,844,140,475,50}

    {26,14,7,26,31,12,2,1,40,14,36,6,2,22,3,24,28,3,20,40,4,32,38,25,5,33,19,14,31,24,2,19,6,40,35,6,25,37,40,37,20,10,14,1,7,39,11,15,29,37}

    5

    Returns: 218

  40. {1456,1131,1889,2303,1958,2150,659,2083,1912,2228,2075,1586,924,1155,231,1038,2207,70,0,1402,357,1662,828,1637,1322,581,905,2035,105,522,87,1439,130,491,1197,1140,1110,757,732,1870,1821,1280,1727,1780,150,295,858,991,1525,427}

    {61,9,22,72,72,47,61,55,46,63,5,43,66,39,57,68,18,16,65,31,67,64,23,24,70,68,10,40,17,47,16,11,20,31,72,5,19,62,20,16,45,35,46,37,69,52,43,44,58,64}

    9

    Returns: 249

  41. {360,196,426,382,587,510,466,667,613,265,648,709,220,0,635,577,530,402,554,622,291,318,50,124,40,496,177,338,258,77,608,309,692,106,168,502,116,491,130,15,367,673,237,86,94,153,450,71,457,411}

    {5,22,22,18,18,18,22,6,7,24,18,23,16,15,12,7,21,6,22,12,18,18,20,5,10,3,16,21,5,6,4,6,16,9,6,5,5,5,20,23,14,16,21,8,10,15,4,5,6,14}

    3

    Returns: 226

  42. {1133,288,1563,1389,0,17,1329,2160,1515,1444,655,584,574,1059,768,515,64,1177,633,952,305,1622,1954,358,391,1030,651,1255,2035,672,1825,750,1545,2124,137,905,1789,412,1879,147,2106,210,481,841,1650,1760,447,1728,1661,990}

    {37,16,55,45,8,47,50,69,30,68,8,40,7,71,72,55,66,69,6,33,45,21,71,30,9,20,4,69,69,71,53,11,15,29,8,47,30,29,65,62,16,67,27,63,3,22,31,26,64,40}

    9

    Returns: 235

  43. {249,1427,1046,1188,993,1398,903,713,513,1850,2209,909,294,466,758,827,2139,187,59,1696,2373,2533,1195,136,357,1515,2065,2071,522,547,2292,1121,826,1387,1254,2456,562,1616,1763,1550,425,2343,732,1935,1330,1025,633,2013,0,940}

    {34,75,63,3,30,22,4,5,3,75,75,22,61,37,55,76,58,58,72,62,80,33,58,46,60,34,2,57,21,12,45,57,1,6,76,77,61,68,78,55,27,29,13,75,50,9,73,43,57,51}

    2000000000

    Returns: 1

  44. {406894957,0,529193604,707660424,311634371,950442515,108739409,990744646,832438477}

    {53842378,15128057,37278354,65028061,37340766,16062987,63327752,16829157,70089660}

    1243099099

    Returns: 1

  45. {462848457,915322304,0,837987219,682664192,342881865,206869033}

    {26512881,5952803,64626881,26090530,15201747,25005380,19589468}

    1713406736

    Returns: 1

  46. {342467049,568192749,0,664609968,850403389,173763443,416949542}

    {2300277,6219482,50896875,58656066,63948384,37685464,29279285}

    1337926100

    Returns: 1

  47. {281985367,174467019,529975269,0,354059653,900986532,750362590}

    {3474779,404054,70595004,24508266,32375315,57444637,18951788}

    1324792001

    Returns: 1

  48. {0,94141070,538109245,369932424,724094226,929836838,225964561}

    {43000933,39938857,28359462,78994233,34728696,69840715,57073099}

    1243145435

    Returns: 1

  49. {0,449974984,191773728,86251808,327590391,845855444,671630963}

    {19128475,74812758,21937550,46706150,49002386,40446541,36070834}

    1183595946

    Returns: 1

  50. {479504954,208301028,497570232,787382793,843144134,0,708529726,350100071,319884610}

    {6235113,53718987,73035982,24149241,16148279,58557364,39220730,51982833,28985839}

    1914309992

    Returns: 1

  51. {0,983312374,766291157,125275496,589104702,402281929,192746246}

    {29228140,47137272,62414164,58577335,48252453,30077569,28132534}

    1444196433

    Returns: 1

  52. {152956530,992467557,763460707,644467990,837494701,225995118,0,448626906}

    {61679342,25820820,72546358,25980030,14090079,62546492,64897044,418060}

    1005829822

    Returns: 2

  53. {302149220,492784113,0,230761895,767522701,570711832,931474195}

    {20363197,9914006,49375583,43359901,29328590,23859739,25453071}

    1007057958

    Returns: 1

  54. {406894957,0,529193604,707660424,311634371,950442515,108739409,990744646,832438477}

    {53842378,15128057,37278354,65028061,37340766,16062987,63327752,16829157,70089660}

    243099099

    Returns: 4

  55. {462848457,915322304,0,837987219,682664192,342881865,206869033}

    {26512881,5952803,64626881,26090530,15201747,25005380,19589468}

    713406736

    Returns: 2

  56. {342467049,568192749,0,664609968,850403389,173763443,416949542}

    {2300277,6219482,50896875,58656066,63948384,37685464,29279285}

    337926100

    Returns: 3

  57. {281985367,174467019,529975269,0,354059653,900986532,750362590}

    {3474779,404054,70595004,24508266,32375315,57444637,18951788}

    324792001

    Returns: 3

  58. {0,94141070,538109245,369932424,724094226,929836838,225964561}

    {43000933,39938857,28359462,78994233,34728696,69840715,57073099}

    243145435

    Returns: 4

  59. {479504954,208301028,497570232,787382793,843144134,0,708529726,350100071,319884610}

    {6235113,53718987,73035982,24149241,16148279,58557364,39220730,51982833,28985839}

    314309991

    Returns: 3

  60. {0,983312374,766291157,125275496,589104702,402281929,192746246}

    {29228140,47137272,62414164,58577335,48252453,30077569,28132534}

    444196433

    Returns: 2

  61. {406894957,0,529193604,707660424,311634371,950442515,108739409,990744646,832438477}

    {53842378,15128057,37278354,65028061,37340766,16062987,63327752,16829157,70089660}

    43099097

    Returns: 13

  62. {462848457,915322304,0,837987219,682664192,342881865,206869033}

    {26512881,5952803,64626881,26090530,15201747,25005380,19589468}

    13406729

    Returns: 16

  63. {342467049,568192749,0,664609968,850403389,173763443,416949542}

    {2300277,6219482,50896875,58656066,63948384,37685464,29279285}

    37926097

    Returns: 10

  64. {281985367,174467019,529975269,0,354059653,900986532,750362590}

    {3474779,404054,70595004,24508266,32375315,57444637,18951788}

    24791998

    Returns: 12

  65. {0,94141070,538109245,369932424,724094226,929836838,225964561}

    {43000933,39938857,28359462,78994233,34728696,69840715,57073099}

    43145433

    Returns: 10

  66. {0,449974984,191773728,86251808,327590391,845855444,671630963}

    {19128475,74812758,21937550,46706150,49002386,40446541,36070834}

    83595945

    Returns: 7

  67. {479504954,208301028,497570232,787382793,843144134,0,708529726,350100071,319884610}

    {6235113,53718987,73035982,24149241,16148279,58557364,39220730,51982833,28985839}

    14309983

    Returns: 29

  68. {0,983312374,766291157,125275496,589104702,402281929,192746246}

    {29228140,47137272,62414164,58577335,48252453,30077569,28132534}

    44196429

    Returns: 11

  69. {152956530,992467557,763460707,644467990,837494701,225995118,0,448626906}

    {61679342,25820820,72546358,25980030,14090079,62546492,64897044,418060}

    5829822

    Returns: 61

  70. {302149220,492784113,0,230761895,767522701,570711832,931474195}

    {20363197,9914006,49375583,43359901,29328590,23859739,25453071}

    7057949

    Returns: 32

  71. {406894957,0,529193604,707660424,311634371,950442515,108739409,990744646,832438477}

    {53842378,15128057,37278354,65028061,37340766,16062987,63327752,16829157,70089660}

    3099075

    Returns: 126

  72. {462848457,915322304,0,837987219,682664192,342881865,206869033}

    {26512881,5952803,64626881,26090530,15201747,25005380,19589468}

    3406665

    Returns: 56

  73. {342467049,568192749,0,664609968,850403389,173763443,416949542}

    {2300277,6219482,50896875,58656066,63948384,37685464,29279285}

    7926067

    Returns: 35

  74. {406894957,0,529193604,707660424,311634371,950442515,108739409,990744646,832438477}

    {53842378,15128057,37278354,65028061,37340766,16062987,63327752,16829157,70089660}

    4

    Returns: 93731797

  75. {462848457,915322304,0,837987219,682664192,342881865,206869033}

    {26512881,5952803,64626881,26090530,15201747,25005380,19589468}

    1

    Returns: 182979690

  76. {342467049,568192749,0,664609968,850403389,173763443,416949542}

    {2300277,6219482,50896875,58656066,63948384,37685464,29279285}

    1

    Returns: 248985833

  77. {281985367,174467019,529975269,0,354059653,900986532,750362590}

    {3474779,404054,70595004,24508266,32375315,57444637,18951788}

    2

    Returns: 103876923

  78. {0,94141070,538109245,369932424,724094226,929836838,225964561}

    {43000933,39938857,28359462,78994233,34728696,69840715,57073099}

    4

    Returns: 87984002

  79. {0, 1000000000 }

    {1000000000, 1000000000 }

    1

    Returns: 2000000000

  80. {0, 10, 20, 30 }

    {8, 5, 3, 11 }

    6

    Returns: 6

  81. {77, 7777, 777 }

    {700, 70000, 7000 }

    1

    Returns: 77700

  82. {1 }

    {1 }

    1

    Returns: 1

  83. {0, 15, 22, 100, 129, 200, 230 }

    {10, 5, 3, 29, 1, 29, 1 }

    30

    Returns: 4

  84. {999999999, 1000000000 }

    {1, 1000000000 }

    2000000000

    Returns: 1

  85. {0, 1000000000 }

    {1000000000, 1000000000 }

    1500000000

    Returns: 2

  86. {0, 10, 20, 30 }

    {8, 2, 3, 11 }

    6

    Returns: 5

  87. {10, 0, 20, 30 }

    {5, 8, 3, 11 }

    6

    Returns: 6

  88. {10, 100 }

    {90, 1 }

    100

    Returns: 1

  89. {10, 20, 40, 30 }

    {4, 4, 4, 4 }

    3

    Returns: 8

  90. {1, 1000000000 }

    {999999999, 1000000000 }

    1

    Returns: 1999999999

  91. {50000000, 49000000, 48000000, 47000000, 46000000, 45000000, 44000000, 43000000, 42000000, 41000000, 40000000, 39000000, 38000000, 37000000, 36000000, 35000000, 34000000, 33000000, 32000000, 31000000, 30000000, 29000000, 28000000, 27000000, 26000000, 25000000, 24000000, 23000000, 22000000, 21000000, 20000000, 19000000, 18000000, 17000000, 16000000, 15000000, 14000000, 13000000, 12000000, 11000000, 10000000, 9000000, 8000000, 7000000, 5000000, 4000000, 3000000, 2000000, 1000000 }

    {1000000, 990000, 980000, 970000, 960000, 950000, 940000, 930000, 920000, 910000, 900000, 890000, 880000, 870000, 860000, 850000, 840000, 830000, 820000, 810000, 800000, 790000, 780000, 770000, 760000, 750000, 740000, 730000, 720000, 710000, 700000, 690000, 680000, 670000, 660000, 650000, 640000, 630000, 620000, 610000, 600000, 590000, 580000, 570000, 560000, 550000, 540000, 530000, 520000 }

    750000

    Returns: 58

  92. {0, 10, 20 }

    {1, 1, 1 }

    30

    Returns: 1

  93. {2000, 0 }

    {1000, 1000 }

    1000

    Returns: 2

  94. {0, 8, 21, 49, 61 }

    {7, 12, 4, 7, 20 }

    50

    Returns: 2

  95. {1 }

    {1000000000 }

    1

    Returns: 1000000000

  96. {15, 95, 300 }

    {1, 20, 200 }

    1000

    Returns: 1

  97. {100, 200, 110 }

    {10, 10, 10 }

    30

    Returns: 2

  98. {0, 10, 11 }

    {1, 1, 1 }

    2

    Returns: 2

  99. {0, 1000000000 }

    {1000000000, 1000000000 }

    2000000000

    Returns: 1

  100. {0, 10, 20, 30 }

    {8, 5, 3, 11 }

    100000000

    Returns: 1

  101. {1, 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000, 11000, 12000, 13000, 14000, 15000, 16000, 17000, 18000, 19000, 30000, 41111, 51111, 61111, 71111, 81111, 91111, 101111, 111111, 121111, 131111 }

    {1, 8, 7, 9, 5, 8, 9, 8, 9, 7, 8, 88, 89, 89, 87, 45, 36, 89, 45, 12, 54, 45, 78, 54, 54, 65, 99, 98, 45, 46, 45, 74, 456, 897, 897, 456, 987, 798, 897, 468 }

    1111

    Returns: 21

  102. {0, 2, 50 }

    {1, 1, 100 }

    10

    Returns: 11

  103. {30, 20, 10, 0, 50, 100, 200, 900000000, 900000010, 900000020, 900000030, 900000050, 900000060, 900000070, 900000090, 900000110, 900000120, 900000130, 900000140, 900000150, 900000160, 900000170, 900000180, 900000190, 900000200 }

    {11, 3, 2, 8, 49, 96, 899999797, 7, 1, 8, 11, 9, 8, 18, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1 }

    6

    Returns: 150000021

  104. {0, 5, 9 }

    {2, 2, 2 }

    2

    Returns: 3

  105. {0, 999999997, 999999999 }

    {499999998, 1, 1000000000 }

    499999997

    Returns: 5

  106. {100, 1, 10 }

    {1000, 5, 2 }

    6

    Returns: 169

  107. {1000000000 }

    {100000 }

    2000000000

    Returns: 1

  108. {4 }

    {4 }

    4

    Returns: 1

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: