Statistics

Problem Statement for "TurretDefense"

Problem Statement

*** You may only submit a given problem once - no resubmissions will be accepted. ***

"Incoming! Fire the defense turrets at these coordinates! Go go go!"

You have been given a list of incoming targets that must be shot down in the order they are given. Assuming your turret is aimed at some location, it will take time to move the turret and fire at a different location. If you are currently aimed at point (a,b), and you must move to aim at point (c,d), the time required is the absolute difference in first coordinates plus the absolute difference in second coordinates. For example, starting at (3,7) it will take 4 seconds to aim at point (5,5). Along with the coordinates of each incoming target, you are also given their arrival times. The turret must be fired precisely at the arrival time in the direction of the target. Immediately after firing, the turret can be moved to aim at the next location (no time is lost firing). Your method will return the index of the earliest target that cannot be shot down. For example, let's assume
    xs    = {3,5,6}
    ys    = {7,5,6}
    times = {11,15,16}.
Your turret always begins aimed at (0,0) at time 0. Since the first target is arriving at location (3,7) at time 11 you have 11 seconds to move there and fire. This is 1 second more than is needed. At time 11 you fire the turret, and immediately start moving to aim at (5,5). Since the second target arrives at time 15, you have 4 seconds to aim. This is exactly enough time. At time 15, you fire at the second target. Unfortunately, the third target will arrive before you can shoot it down. You would return 2 since target 2 (third target) is the earliest one you couldn't shoot down. If you could shoot them all down, return -1. As shown above, xs[i],ys[i] are the coordinates, and times[i] is the arrival time of target i.

Definition

Class:
TurretDefense
Method:
firstMiss
Parameters:
int[], int[], int[]
Returns:
int
Method signature:
int firstMiss(int[] xs, int[] ys, int[] times)
(be sure your method is public)

Notes

  • xs will contain between 2 and 50 elements inclusive.
  • ys and times will contain the same number of elements as xs.
  • Each element of xs will be between 0 and 1000 inclusive.
  • Each element of ys will be between 0 and 1000 inclusive.
  • Each element of times will be between 1 and 1000000 inclusive.
  • The elements of times will be in strictly increasing order.

Constraints

    Examples

    1. {3,5,6}

      {7,5,6}

      {11,15,16}

      Returns: 2

      From above.

    2. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

      {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

      {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32}

      Returns: -1

      A target arrives every 2 seconds. Luckily it only takes 2 seconds to switch from target to target.

    3. {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

      {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}

      {2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,31}

      Returns: 15

      Same as before, but now you only have 1 second to switch to the final target.

    4. {1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0}

      {1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0}

      {2000,4000,6000,8000,10000,12000,14000,16000,18000,20000, 22000,24000,26000,28000,30000,32000,34000,36000,38000,40000, 42000,44000,46000,48000,50000,52000,54000,56000,58000,60000, 62000,64000,66000,68000,70000,72000,74000,76000,78000,80000, 82000,84000,86000,88000,90000,92000,94000,96000,98000,100000}

      Returns: -1

      Takes a while, but you hit them all.

    5. {1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0}

      {1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0, 1000,0,1000,0,1000,0,1000,0,1000,0}

      {2000,4000,6000,8000,10000,12000,14000,16000,18000,20000, 22000,24000,26000,28000,30000,32000,34000,36000,38000,40000, 42000,44000,46000,48000,50001,52000,54000,56000,58000,60000, 62000,64000,66000,68000,70000,72000,74000,76000,78000,80000, 82000,84000,86000,88000,90000,92000,94000,96000,98000,100000}

      Returns: 25

      1 second is all that is required to mess it all up.

    6. {4,5}

      {4,5}

      {7,8}

      Returns: 0

    7. {1,2,3,4,15}

      {1,2,3,4,15}

      {100,200,300,400,405}

      Returns: 4

    8. {516,223,201,335,571,995,948,61,577,982,472,72,505,312,847,897,657,425,665,916,749,890,321,393,795,489,481,552,121,248,225,15,239,749,980,502,388,823,221,815,494,454,134,775,954,531,833,965,149,898}

      {521,835,829,10,941,981,543,382,813,184,98,931,490,72,648,271,963,158,353,983,453,318,744,893,270,721,832,441,335,612,752,292,704,348,214,421,752,554,309,89,181,297,312,217,867,744,936,948,672,842}

      {1161,2103,2849,3970,6041,6911,7722,9061,10975,12130,13462,15297,16811,17491,18608,19876,21482,22611,24009,25141,26600,27306,29201,30016,31111,32232,33138,33641,34288,35505,35790,36767,37599,39262,39822,40775,41575,42399,43699,45189,45620,46518,47715,48999,49866,51300,52444,52828,54491,54759}

      Returns: 49

    9. {240,142,423,957,199,791,972,852,815,532,985,757,740,473,837,620,829,877,306,502,658,109,622,505,468,891,938,345,360,556,311,4,839,987,171,127,561,774,149,487,457,707,113,630,234,87,200,4,620,510}

      {684,266,641,712,520,197,607,775,510,595,499,512,100,845,893,111,2,343,609,199,942,837,830,325,91,832,502,471,902,593,471,650,398,974,934,783,184,235,494,66,832,249,283,751,602,35,402,830,865,316}

      {1090,1998,2656,4181,5588,7053,7645,8106,9262,10311,11320,11641,12090,13505,14101,15133,15737,16269,17257,18819,19975,20981,21649,22583,23611,25240,25618,26389,27231,28180,29518,30403,32090,33144,34511,34729,36726,37551,38762,39642,40849,42646,43650,44703,45965,46871,47549,48195,49508,49509}

      Returns: 49

    10. {259,190,99,42,996,737,415,555,990,59,959,681,707,734,398,355,352,764,341,403,948,578,585,879,781,77,603,42,937,281,400,613,383,561,567,23,29,397,882,456,443,107,68,650,488,3,406,546,932,997}

      {718,119,227,763,892,904,25,175,492,24,679,897,226,800,928,679,975,351,210,120,864,942,543,415,377,219,736,861,837,893,759,719,654,873,447,345,640,329,401,401,335,678,803,329,716,17,132,206,913,116}

      {1191,2446,3163,4410,6314,7474,9559,9906,10722,12560,14480,15907,16797,17739,18987,20060,21336,23268,24396,25011,27068,27978,29216,30167,30811,31917,33490,34634,35946,37382,37647,38469,39413,39939,41232,42128,43319,44595,45857,46333,47229,48358,49130,50270,51433,52931,53661,53999,55329,56443}

      Returns: -1

    11. {778,952,630,760,111,880,193,747,140,46,541,853,700,358,313,711,264,281,142,52,446,445,349,138,97,318,74,542,56,135,223,948,896,710,244,74,232,388,885,999,451,385,762,139,66,979,793,891,214,530}

      {286,462,243,120,737,744,705,667,223,176,558,741,580,410,824,943,462,261,492,621,729,854,953,940,599,104,871,750,405,666,968,518,832,271,834,602,23,933,556,488,972,848,640,222,260,945,440,155,260,941}

      {1113,1753,2903,3608,5296,7071,8732,9506,10853,11555,12937,13878,14540,15102,16306,17169,18993,19569,20265,21179,22063,22913,23938,24581,25761,26498,28350,29438,30495,31001,32076,33970,34972,36183,38132,38920,39812,41262,42274,43375,44485,44939,46097,47869,48973,51274,52494,52936,54251,54909}

      Returns: 49

    12. {511,426,332,538,913,716,287,661,673,257,76,355,293,825,65,847,836,508,473,122,141,336,227,51,305,472,901,852,517,668,565,218,609,112,432,264,811,221,556,791,47,434,474,211,797,549,613,902,957,703}

      {479,664,367,656,139,439,685,639,263,427,38,682,53,274,475,969,708,36,586,487,685,248,748,970,901,516,414,864,217,701,506,870,970,966,475,413,67,641,816,248,182,132,878,310,877,845,611,802,57,431}

      {1489,2247,2665,3631,4799,5419,6656,7183,7791,9337,10728,11651,13074,14173,15779,17523,18411,19767,21111,22123,22356,23800,25073,25859,26392,27723,28819,30289,31816,32569,33353,34581,35706,36910,38587,38856,40316,41667,42465,44164,45266,46162,47640,49447,51106,51609,52266,53658,54838,55492}

      Returns: -1

    13. {945,176,711,420,786,353,199,313,97,88,796,266,39,190,72,96,638,326,720,749,622,58,874,169,757,706,149,396,654,211,878,434,475,201,555,192,962,245,209,850,733,842,12,327,857,23,196,151,284,586}

      {38,913,850,898,428,653,209,851,371,995,231,72,524,580,118,712,796,353,724,174,865,559,358,965,408,909,637,430,796,187,793,540,940,761,224,3,51,850,965,985,34,124,172,359,400,182,716,988,583,732}

      {1408,3807,5185,6368,7782,8609,9728,10948,12430,13261,15144,16346,17521,18331,19615,20479,22071,23296,24702,25547,27070,28748,30498,32314,33518,34138,35515,36706,38165,39382,41530,42937,43973,44583,45996,47326,48678,51185,51787,53249,54959,56044,57279,58051,58836,60630,61651,62476,63642,63643}

      Returns: 49

    14. {947,696,66,304,883,847,207,110,512,856,680,805,552,810,580,250,818,560,292,786,488,914,369,932,362,476,40,950,335,94,791,552,478,565,178,878,561,421,465,651,595,321,969,284,994,822,984,607,234,86}

      {20,771,501,369,627,865,638,988,521,721,871,828,810,444,218,337,123,176,165,414,125,740,203,531,412,865,82,935,67,861,163,802,219,740,123,770,786,23,321,353,221,653,585,378,474,732,801,715,574,57}

      {1638,2907,4034,5185,6258,6916,8314,9616,10743,11915,12730,13197,13857,14540,15284,16510,17386,17763,18449,19557,20835,21917,23509,25320,26486,27179,29113,31811,34167,35817,37494,38687,40028,41181,43173,44611,45029,46409,47187,48074,48959,50100,51170,52930,53907,54868,55586,56698,57223,58667}

      Returns: -1

    15. {148,12,609,660,335,543,289,240,397,90,943,709,729,953,500,461,228,684,444,517,449,894,68,933,63,370,117,699,972,975,944,943,377,718,170,669,80,485,169,381,303,358,633,909,361,157,883,455,572,820}

      {556,398,916,500,796,647,73,811,104,437,638,492,546,267,513,836,113,333,695,675,655,202,943,328,926,668,99,919,10,699,151,686,563,127,486,408,65,289,170,906,569,104,484,624,207,200,423,676,74,565}

      {1016,1675,3764,5078,5932,6425,8154,9825,11152,11879,13007,13640,14438,15629,17119,18106,19690,20462,21447,22045,22486,23901,25510,27490,29179,30130,31332,33314,35084,36529,37260,38764,39593,40521,42119,42841,44249,45281,45978,47125,48185,48960,50321,50917,51989,52697,54129,55191,56386,56455}

      Returns: 49

    16. {522,236,79,407,582,600,396,82,670,557,972,383,654,201,681,962,462,384,469,365,888,811,540,794,454,756,361,396,400,686,382,475,120,194,965,63,474,837,774,836,200,646,61,459,319,315,623,33,805,341}

      {894,503,987,648,605,541,132,590,655,648,399,551,367,929,869,751,105,330,723,291,293,856,653,899,246,695,561,336,870,991,172,922,196,438,681,163,931,784,763,75,689,807,250,356,324,292,598,222,855,107}

      {2225,3280,4699,5855,6884,7253,8051,9074,10181,10937,11609,13117,13727,15399,16786,17368,19451,20483,21309,22397,22977,24170,25410,26152,27825,29571,30537,31041,31705,32720,33958,35581,37568,38635,40402,42722,44440,45115,45348,46699,48313,49719,50885,51772,52740,52826,53957,54957,56748,56749}

      Returns: 49

    17. {883,791,818,481,713,219,825,738,28,240,733,695,376,887,720,344,16,829,975,451,254,29,820,269,460,683,844,563,853,458,375,383,885,994,947,285,218,389,778,199,75,921,638,935,974,584,924,426,706,90}

      {200,127,721,873,910,672,960,310,539,775,599,767,965,601,52,343,380,285,88,157,726,70,882,823,222,576,358,301,256,23,229,683,567,868,736,578,415,197,194,673,158,371,110,742,471,909,827,833,247,299}

      {1413,2208,2913,3863,4269,5001,6032,7641,9510,10522,11226,12390,13823,15416,16637,17505,18600,20418,21092,22246,23082,24091,25957,26802,27732,28821,29768,30580,31328,32652,33890,34520,35361,36769,37624,38626,38949,40221,41535,43554,45054,46253,47223,48903,49321,50241,51508,52927,54335,55116}

      Returns: -1

    18. {191,595,488,221,416,629,43,834,206,840,563,985,303,162,734,843,832,197,509,402,487,504,287,120,770,350,773,774,748,395,593,23,438,624,382,724,866,253,516,549,31,276,881,35,500,755,39,804,130,965}

      {996,325,461,45,268,250,631,825,350,44,313,117,771,389,38,863,850,551,437,192,965,742,416,591,574,284,986,162,538,265,509,105,272,258,385,417,109,564,843,44,816,420,283,604,618,566,828,122,204,589}

      {1309,2551,2953,4127,4685,5088,7019,8008,9845,11484,12256,13155,15436,16859,17837,19494,20136,21521,22553,23760,25333,26358,27510,28241,29724,30981,32480,34115,35217,36652,37217,38287,39419,40342,41447,42287,43061,45111,46584,47799,49100,50413,51821,53355,53886,55020,56074,58138,59886,60225}

      Returns: 49

    19. {624,496,278,905,110,241,395,536,733,819,688,9,219,725,761,587,734,701,881,329,604,188,481,432,855,414,435,558,732,684,36,411,12,784,648,156,621,986,582,431,791,86,878,590,761,26,318,492,800,142}

      {182,654,174,795,959,809,508,172,473,947,886,334,670,748,965,168,603,878,293,757,991,38,19,843,101,772,198,444,602,998,909,431,470,955,503,825,969,737,378,863,263,885,826,409,199,563,664,130,369,695}

      {1338,2912,4285,5591,6564,7688,8329,9546,10988,11626,12092,13883,15022,15893,16805,17779,19094,19694,20706,21732,23158,25033,25676,26988,28892,30828,31491,32250,32772,33414,35031,36511,37684,39387,40802,41851,42633,43685,45269,46219,48047,50252,52080,53703,54552,56292,57000,58411,59773,59792}

      Returns: 49

    20. {716,340,938,276,579,870,811,817,838,455,338,220,630,493,306,4,929,178,130,551,546,63,636,123,737,283,162,210,758,845,772,746,941,228,403,900,906,411,37,985,347,371,610,307,388,46,187,587,938,731}

      {113,30,580,860,234,921,486,215,24,142,590,634,413,916,710,399,386,584,629,648,970,274,198,269,64,831,348,988,659,511,565,537,403,522,746,93,132,661,574,422,939,994,499,543,606,689,187,8,702,915}

      {1621,2425,4071,5960,7662,9220,10605,11330,11558,12276,13745,14136,15709,16894,18253,19519,21378,22947,23153,23842,24901,26916,27993,28628,29527,31310,32463,33746,34740,35889,36849,37460,38541,39768,40965,42607,42716,44491,45773,47086,48734,48956,50337,51616,52364,53215,54054,55043,56212,56213}

      Returns: 49

    21. {983,651,215,343,561,889,635,44,356,527,289,514,385,906,703,456,530,429,422,773,270,269,143,343,21,306,315,628,395,376,948,290,591,861,434,645,550,355,245,800,480,667,475,572,851,670,332,829,965,604}

      {846,756,793,257,261,598,824,94,793,899,323,795,723,857,510,867,43,426,884,952,237,995,109,213,99,7,619,706,894,671,399,959,564,15,170,89,163,859,569,631,122,962,773,954,524,490,418,532,56,186}

      {2415,3441,4816,5556,5889,7261,8173,9831,11279,11953,12958,14649,15636,16301,17179,18217,19561,20698,21510,22267,24085,25609,27354,28202,28830,29687,31125,32012,32453,33409,34256,35829,36918,38096,38980,40087,40681,41827,43224,44020,45112,46718,47206,47676,48721,49110,49790,50584,51204,51405}

      Returns: 49

    22. {196,850,348,957,863,144,911,440,178,76,142,227,68,577,299,854,618,656,477,432,90,639,515,750,406,680,782,329,618,524,800,645,971,559,314,15,583,808,794,869,418,685,561,431,189,2,707,154,79,922}

      {698,598,649,323,125,844,141,269,333,925,431,136,803,223,263,245,994,251,35,736,38,733,332,817,105,479,588,441,480,59,784,945,399,943,799,159,460,367,139,37,6,875,51,890,205,167,661,919,689,617}

      {1565,3167,4241,5761,6359,7893,10301,11339,12328,13163,14521,14917,16113,17598,18824,19505,20921,21907,22736,23929,25460,27010,27956,29250,30593,31674,31914,33433,34684,35763,37258,37984,39635,41276,42602,44455,45554,46703,47078,48140,48736,50504,51486,53096,54849,55569,57120,58722,59247,59248}

      Returns: 49

    23. {772,611,586,381,991,879,820,238,229,400,36,369,174,29,452,748,864,916,898,175,354,182,993,498,370,252,615,523,981,436,150,286,541,173,18,635,225,268,264,812,245,335,610,56,484,631,187,66,612,437}

      {337,551,938,135,283,972,174,195,165,23,12,339,954,369,918,257,971,628,826,392,348,630,477,452,543,539,998,539,164,492,938,982,734,56,385,232,715,924,982,464,38,985,618,865,656,75,334,915,127,497}

      {258,445,462,784,1153,1200,1275,1720,2095,2204,2496,2607,3078,3483,3888,4374,4535,4775,4980,5193,5396,5433,5689,6172,6544,6600,6841,7292,7644,7761,7816,7901,8391,8665,8964,9210,9635,9866,9896,10293,10552,10668,11026,11099,11113,11235,11730,12058,12144,12527}

      Returns: 0

    24. {726,125,62,994,676,196,807,850,500,872,177,356,860,989,543,477,829,38,418,361,164,320,675,382,95,912,78,623,330,689,883,728,799,951,568,393,692,986,868,285,743,248,141,589,344,686,765,947,986,180}

      {710,52,745,953,614,757,992,283,748,154,308,869,985,696,601,679,479,140,753,207,107,730,772,624,836,827,259,450,93,886,225,989,916,546,708,1,109,341,408,739,895,455,543,767,590,797,451,733,626,592}

      {1455,2995,4177,5633,6295,7121,8173,9080,9898,10872,12061,13090,13786,14276,15132,15760,16429,18033,19409,20491,21155,22153,22674,23116,23707,24718,26162,27248,28333,29544,30596,31900,32411,33222,34030,35235,35866,36500,36923,38222,38838,39787,40204,41335,42181,42892,43140,43678,44101,45397}

      Returns: 46

    25. {340,242,467,128,594,477,662,763,164,184,827,965,26,186,795,943,604,346,877,425,671,912,789,436,945,612,757,43,442,231,964,962,217,905,940,903,728,112,523,328,693,414,511,848,973,304,208,848,713,149}

      {630,18,690,91,273,433,598,959,989,445,764,681,694,185,634,437,336,672,196,793,828,595,414,376,371,622,651,205,950,700,5,673,594,187,453,306,361,791,731,851,918,267,886,945,14,515,537,610,98,219}

      {1447,2202,3520,4701,5463,5769,6281,7218,8324,8944,10023,10605,11580,12516,13823,14226,14927,15870,17054,18377,18851,19427,19771,20248,21258,22200,22490,24035,25479,26343,28011,28785,29722,31075,31793,32099,32426,33587,34259,34991,35573,36754,37738,38223,39722,40686,41123,42114,43074,44253}

      Returns: 45

    26. {776,303,614,170,380,461,611,356,51,301,818,629,624,871,866,960,919,177,323,420,133,552,517,41,925,267,56,108,405,151,946,65,188,695,374,849,324,941,703,670,417,261,915,951,481,989,813,391,100,740}

      {544,880,314,203,602,330,201,79,332,267,526,878,99,466,986,257,696,748,510,620,285,535,794,812,140,689,756,781,731,680,879,279,238,122,462,783,406,314,660,55,776,455,813,959,694,881,964,435,212,767}

      {1653,2858,4186,4971,5648,6417,7132,7895,8750,9397,10569,11308,12138,12962,13743,14935,15685,16750,17602,18022,18976,20013,20416,21392,23208,24496,25229,25780,26558,27336,28691,30474,30696,31638,32608,32932,34258,35376,36269,37362,38709,39497,40656,41335,42460,43484,43792,44854,45816,47195}

      Returns: 35

    27. {55,824,665,115,258,820,343,316,969,965,533,172,530,421,295,549,370,446,227,91,939,272,828,258,945,938,247,479,887,23,957,612,244,791,851,753,448,648,203,591,181,965,3,920,436,264,138,635,173,476}

      {45,498,421,489,497,260,114,477,352,253,16,573,253,392,620,295,465,654,2,751,253,479,234,50,472,210,101,574,332,660,543,674,619,100,478,160,998,517,381,455,426,748,271,604,96,208,583,435,799,268}

      {461,1693,1959,2579,3207,4141,5211,6063,7207,7771,8757,9940,10826,11267,11989,12579,13376,14114,15093,16091,17697,18869,20102,21304,22587,22907,23790,24912,25938,27239,28525,29454,30358,31452,32251,33133,34447,35190,36181,36927,37736,38912,40565,42212,43457,43854,44830,45022,46079,46960}

      Returns: 47

    28. {143,316,819,879,344,884,724,134,541,636,346,863,908,92,994,620,475,821,429,421,526,779,220,43,424,118,1,166,190,563,395,810,439,962,611,667,832,621,827,115,8,600,269,858,95,232,581,393,272,748}

      {415,755,546,30,442,285,840,211,870,468,740,38,377,270,765,663,859,775,801,805,709,312,460,28,461,764,429,207,483,169,582,152,75,278,483,721,754,241,174,708,757,192,569,257,745,81,602,522,523,758}

      {694,1632,2408,3462,4445,5530,6727,8211,9228,10112,11109,12359,13119,14414,16197,16980,17469,18360,18984,19158,19762,20445,21164,21905,23188,24037,24531,25345,26068,27090,27837,28714,29635,30478,31060,31586,32093,33241,33605,34950,35593,36794,37615,38962,40679,41560,42472,43023,43287,44283}

      Returns: 8

    29. {573,129,81,371,769,49,437,793,122,638,625,745,174,597,671,678,884,372,352,912,607,483,422,424,190,32,469,919,396,587,749,844,202,585,962,22,792,612,192,308,464,464,945,201,3,672,511,689,548,257}

      {676,650,355,852,148,58,417,940,924,860,330,929,237,857,394,928,635,124,489,638,221,517,849,479,77,579,531,163,394,753,2,242,926,115,990,749,938,998,457,980,957,767,325,604,271,702,353,754,311,418}

      {1458,2179,2905,3931,5162,6023,7021,8367,9404,10350,10975,11841,13195,14735,15583,16148,16883,18071,18580,19399,20297,21029,21640,22327,23010,24033,24811,25837,26892,27580,28644,29055,30438,31752,33216,34573,35801,36463,37473,38345,38801,39023,39041,40309,41255,42742,43565,44266,45287,46013}

      Returns: 42

    30. {873,277,448,158,671,358,716,697,386,518,339,71,244,925,119,991,610,509,408,771,756,627,502,925,540,169,588,343,851,339,393,701,608,797,362,613,703,382,53,435,749,155,716,570,708,93,432,570,473,342}

      {18,342,249,599,911,271,173,835,595,153,910,284,729,377,142,332,51,972,724,724,261,722,14,270,607,780,306,73,554,899,608,147,4,651,963,168,787,774,399,35,741,95,136,850,556,323,79,902,699,346}

      {1279,2331,2373,3318,4617,5885,6558,7507,8293,8927,9990,11361,12019,13476,14840,16378,17281,18406,19072,19754,20496,21577,22745,23832,25038,25888,27233,28054,29538,30450,31270,32182,32436,33502,34416,35740,36804,37415,38541,39581,40832,42128,42851,44106,44807,45798,46505,47728,48117,48671}

      Returns: 2

    31. {957,412,553,862,746,847,522,615,455,718,374,112,522,186,870,916,961,235,721,8,911,795,636,981,640,670,579,492,561,684,604,239,385,981,236,52,552,773,133,289,692,971,424,632,990,5,926,550,952,875}

      {210,130,282,896,314,744,260,901,747,15,292,637,325,847,29,974,279,859,814,80,33,447,993,125,23,796,55,223,937,642,408,267,798,222,73,20,380,913,519,330,549,246,352,637,264,608,612,965,126,695}

      {1652,2519,3093,4502,5307,5990,7280,8363,8693,9999,10802,11836,12682,13782,15541,16600,17506,19020,19808,21525,22599,23597,24608,26069,26721,27768,28606,29024,30248,30506,30862,31826,32754,34109,35379,36008,37083,38184,39362,39931,41014,41791,42610,43526,44737,46267,47404,48546,49829,50842}

      Returns: 29

    32. {147,324,11,778,285,69,661,418,266,260,181,249,210,370,321,551,775,165,128,795,631,424,722,401,271,383,348,694,884,903,709,631,793,39,875,728,951,935,43,506,282,765,280,678,268,716,946,263,992,866}

      {895,762,34,185,683,581,20,746,979,882,314,724,59,149,367,667,807,831,463,54,896,592,174,155,890,814,661,784,873,255,59,607,814,929,591,293,294,597,711,941,413,482,550,903,654,207,151,328,247,260}

      {1304,1867,2954,4217,5364,5852,7312,8359,8745,8908,9588,10522,11659,11945,12491,13392,14056,14709,15561,16842,18065,18607,19631,20334,21565,22019,22676,23589,24179,24852,25364,26166,26981,27993,29459,29975,30450,30788,31888,32669,33590,34143,34875,36046,36950,37632,38030,39304,40208,40798}

      Returns: 45

    33. {971,739,178,29,626,229,3,579,934,507,228,145,209,989,428,148,522,107,683,236,505,810,140,241,320,388,482,149,736,19,820,864,260,892,379,466,286,424,823,404,344,98,999,552,580,719,394,348,775,413}

      {589,289,351,544,604,910,18,821,49,995,933,262,679,169,532,356,48,235,434,724,674,550,186,795,308,511,948,563,682,766,599,247,344,31,166,800,17,550,929,534,261,55,17,796,62,785,842,539,396,526}

      {1674,2628,3616,4399,5399,6563,8125,9984,11564,13395,14093,15088,15618,17332,18494,19358,20327,21117,22389,23562,24176,24949,26045,27173,27850,28459,29120,30175,31288,32483,33574,33993,34843,35951,36708,37757,38995,39511,40603,41628,42339,43125,44542,46165,47260,48610,49170,49730,50571,51190}

      Returns: 37

    34. {909,525,35,311,865,138,840,508,473,645,626,57,895,52,315,228,440,550,913,171,956,376,48,296,212,128,296,360,61,802,498,425,57,961,366,896,785,711,80,505,611,395,255,222,718,223,589,790,280,354}

      {771,761,358,337,711,674,669,147,982,275,648,532,414,508,358,771,169,312,650,468,245,149,648,480,293,586,69,658,825,172,104,596,394,328,594,247,70,950,5,842,593,952,291,266,936,39,46,685,577,575}

      {1938,2336,3584,4155,5527,6517,7608,8579,9477,10544,11000,11911,13066,14110,14792,15713,16780,17220,18363,19306,20663,21688,22608,23133,23437,23852,24678,25787,26422,28187,28829,29772,30465,31799,32698,33704,34103,35062,36817,38340,38803,39294,40495,40715,41938,43339,44188,45477,46472,46798}

      Returns: 41

    35. {273,829,695,687,28,10,990,848,890,462,987,254,690,594,823,149,803,236,265,890,359,663,588,375,173,839,536,953,573,15,35,920,46,330,711,511,880,402,670,370,806,968,444,853,965,526,513,141,413,568}

      {270,85,744,458,888,885,381,212,80,221,514,430,378,182,676,441,157,426,466,249,329,309,982,250,299,326,125,782,526,132,25,500,769,541,539,250,917,387,889,583,79,854,281,298,523,897,534,451,867,675}

      {833,1605,2853,3402,4958,4966,6634,7300,7547,8468,9705,10916,11674,12376,13211,14613,15806,16721,17289,18500,19120,19911,20989,22274,22998,23702,24668,25800,26648,27935,28185,29716,30997,31933,32566,33102,34286,35777,36943,37801,38817,39906,41330,41911,42407,43677,44091,44927,45916,46714}

      Returns: 5

    36. {609,517,33,466,797,930,302,597,4,200,655,652,966,276,387,9,614,22,797,994,369,392,587,648,663,930,131,264,577,477,191,915,784,901,870,757,407,114,595,496,186,657,694,51,422,629,729,101,453,818}

      {41,895,51,456,128,449,29,169,379,999,496,297,357,363,660,990,301,719,843,163,793,107,328,640,527,896,25,614,957,348,470,829,192,347,554,743,881,372,519,285,977,767,180,748,235,425,33,739,971,52}

      {1096,2112,3532,4530,5677,6348,7561,8135,8863,10129,11184,11720,12546,13533,13986,15120,16705,17806,18835,19914,21236,22194,22990,23666,23986,24788,26608,27542,28258,29114,29765,31247,32185,32622,33179,33744,34551,35541,36634,37120,38435,39590,40643,42348,43491,43973,44565,46154,46843,48225}

      Returns: 8

    37. {436,975,739,424,614,694,887,46,874,828,301,809,414,787,355,57,995,128,747,297,760,49,675,179,176,1,688,163,224,823,937,10,765,717,664,144,725,529,388,629,538,295,486,952,117,701,511,78,474,155}

      {887,270,984,457,366,959,210,622,937,581,161,295,743,635,807,307,892,412,721,377,960,742,714,645,450,867,445,714,357,9,52,148,574,524,14,918,814,570,597,124,342,52,443,413,859,283,96,931,514,144}

      {1572,2874,3911,5130,5806,6492,7806,9372,10563,11062,12293,12950,13926,14584,15512,16714,18728,20528,21828,22731,23803,25169,25901,26166,26421,27297,28611,29643,30319,31380,31958,33000,34470,34884,35731,37198,37899,38775,39032,40158,40470,41017,41610,42423,43937,45180,46002,47475,48663,49435}

      Returns: 23

    38. {453,410,258,884,552,330,670,615,858,783,747,406,164,886,57,435,857,647,438,381,253,672,706,151,337,421,718,146,902,808,834,746,931,821,345,991,647,831,352,270,43,190,667,214,834,766,776,862,759,73}

      {576,628,820,745,603,537,610,188,723,706,107,412,809,58,414,147,772,820,757,629,379,452,664,580,749,244,689,234,31,0,193,523,750,888,702,843,548,751,82,212,547,927,325,974,365,885,38,652,897,794}

      {1448,2030,2544,3494,4321,4905,5597,6174,6982,7329,8387,9335,10301,12169,13511,14229,15659,16239,16822,17232,18103,18942,19469,19539,20302,21247,22000,23245,24611,25195,25516,26360,26938,27459,28408,29305,29980,30435,32038,32504,33347,34261,35347,36852,38262,38992,39867,41046,41511,42399}

      Returns: 23

    39. {194,189,964,684,464,46,628,74,425,872,186,16,289,238,945,658,534,219,774,123,598,824,122,216,761,48,670,392,295,101,157,57,919,586,629,369,300,499,211,98,600,889,500,928,76,995,884,859,330,426}

      {365,969,115,716,999,896,500,203,663,799,834,720,671,489,150,19,709,631,588,207,673,629,954,738,231,883,760,626,384,597,963,676,847,188,129,433,820,705,966,479,600,301,981,484,528,981,528,86,967,330}

      {893,1653,3466,4778,5308,6161,7625,8958,10048,10977,11911,12282,12822,13360,14556,15279,16402,17033,17944,19474,20499,21265,22577,23212,24281,25796,26919,27405,28208,28635,29126,29615,30966,32340,32438,33203,33686,34275,34873,35523,36163,36942,38497,39769,40870,42401,43143,44093,45849,46621}

      Returns: 34

    40. {889,530,948,935,626,416,233,60,919,116,698,907,229,924,502,842,305,185,150,572,756,480,902,186,409,486,889,819,892,806,909,921,940,11,518,776,369,703,544,679,517,670,624,165,262,112,686,761,346,463}

      {569,4,876,557,121,895,311,753,212,535,176,183,27,386,29,436,927,551,914,854,927,446,661,128,534,486,894,994,312,724,551,672,995,936,49,157,444,281,967,560,3,491,249,517,71,567,519,99,820,29}

      {1466,2756,4064,4465,5230,6420,7674,8723,10414,11989,12944,13229,14550,15896,17016,17969,19476,20247,21126,22033,22597,23634,24328,25675,26771,27351,28522,29078,29580,30386,31095,31464,31908,33320,34835,35221,35925,36661,37623,38527,39254,40018,40412,41244,42151,43011,43720,44595,45758,47038}

      Returns: 28

    41. {638,492,991,65,274,443,65,383,15,253,16,610,47,89,377,645,801,622,230,515,120,744,385,300,589,256,622,798,661,501,137,913,669,453,222,850,358,630,735,165,306,523,101,590,522,934,407,348,502,731}

      {692,360,270,46,645,357,266,874,748,390,448,356,384,670,665,783,526,971,176,480,407,49,154,305,32,684,178,448,440,952,991,560,405,310,266,51,657,903,716,534,765,273,648,3,529,293,998,302,126,737}

      {1796,2704,3417,4747,5729,6403,6966,8252,9242,10267,10640,11493,12319,12832,13172,13972,14422,15102,16750,17834,18448,19860,20570,21053,22012,23415,24480,24971,25569,26592,27234,28846,29701,30269,30692,31762,33343,34056,34476,35393,35796,35945,36947,38403,39159,40023,41542,42529,43244,44298}

      Returns: 41

    42. {519,873,423,320,297,464,193,161,128,939,138,803,985,352,311,903,678,660,216,582,61,282,936,486,585,201,246,923,283,25,913,715,832,762,275,207,869,605,551,351,122,686,71,884,258,555,747,434,570,172}

      {668,781,730,276,659,616,919,361,7,884,526,862,328,200,521,825,721,880,310,62,947,854,565,715,358,88,100,249,685,196,298,95,609,568,27,567,254,717,222,239,318,526,531,623,639,735,511,894,349,319}

      {1620,2283,3119,3856,4325,4930,5800,6723,7114,8905,10241,11563,12466,13680,14379,15709,16226,16407,17500,18317,20177,20636,21659,22339,23247,24012,24394,25436,26704,27655,28801,28993,29828,30393,31517,32612,33724,34613,35507,35861,36318,37139,38057,39365,40303,40810,41306,42080,42778,43433}

      Returns: 31

    43. {249,481,64,96,489,932,625,863,921,948,302,846,259,176,991,353,103,180,92,737,775,148,626,362,996,236,353,194,66,458,692,39,274,61,551,759,40,261,603,622,679,78,171,68,738,746,635,804,584,850}

      {189,84,266,900,874,469,747,533,20,131,235,907,625,983,719,132,750,546,805,807,706,459,590,774,649,983,636,269,250,678,57,506,234,672,364,590,922,582,0,344,421,201,400,293,683,532,39,567,514,597}

      {518,1321,2177,3211,4012,5109,5723,6562,7155,7768,8875,10358,11530,12088,13582,15127,16369,17027,17733,18615,19029,19962,20814,21473,22605,23848,24570,25257,25485,26747,27914,29018,29539,30615,31470,32155,33508,34437,35515,36041,36370,37580,38206,38683,40056,40644,40807,41578,42317,42897}

      Returns: 46

    44. {498,735,94,385,739,507,713,902,653,989,756,126,276,281,314,854,628,120,838,34,6,676,512,84,888,965,96,497,488,320,621,576,383,386,751,326,452,817,72,947,562,158,786,916,67,421,525,323,173,510}

      {91,9,696,942,910,52,532,301,936,319,413,479,517,128,182,14,507,549,842,803,481,493,118,40,504,569,125,468,298,591,4,960,32,768,63,990,211,837,60,766,271,851,725,678,603,877,541,249,667,611}

      {635,1423,3121,4060,4941,6531,7539,8172,9317,9445,10016,11063,11588,12343,12449,13415,14180,14911,16354,17288,18096,19193,20130,20756,22086,22566,24154,25298,25575,26308,27512,28964,30301,31357,32774,34370,35399,36838,38681,40721,41653,42753,43832,44210,45401,46240,46748,47378,48376,49048}

      Returns: 9

    45. {853,817,429,136,602,291,752,534,170,714,97,331,416,548,98,838,673,435,839,412,163,226,333,968,147,119,643,91,257,569,514,217,455,455,351,245,260,241,3,787,178,498,71,946,773,231,429,183,445,870}

      {197,355,790,704,689,424,329,761,730,733,557,829,325,960,468,416,858,35,174,897,868,389,790,27,12,841,487,283,962,352,511,205,849,616,23,37,378,206,768,460,857,518,999,173,219,349,556,371,569,264}

      {1382,2050,3334,3867,4781,5536,6370,7408,8048,8929,10158,11134,11790,12677,13963,15057,15672,17167,18074,19417,19920,20469,21154,22735,23726,24451,25718,26782,27689,28866,29376,30319,31380,32074,33224,33692,34306,34929,35910,37175,38629,39746,40661,42420,42789,43947,44541,45346,46021,47103}

      Returns: 25

    46. {831,518,377,259,723,498,827,409,839,102,224,899,397,414,541,18,435,723,242,308,687,29,777,33,493,157,922,360,512,276,878,145,387,515,300,155,907,518,114,81,433,23,46,962,550,967,311,452,933,212}

      {762,942,432,691,127,710,219,689,682,105,666,992,773,292,283,866,189,220,662,152,246,283,873,302,830,629,167,839,355,172,160,547,748,159,901,682,115,552,343,636,725,619,787,775,279,824,806,621,230,556}

      {2092,2664,3358,3864,5233,6441,7354,8369,8963,10528,11466,12949,14144,14898,15205,16388,17761,18364,19574,20476,21158,22191,23764,25179,26181,26803,28285,29624,30369,31011,32008,33503,34072,35121,36499,37096,38742,39876,40572,40935,41617,42269,42789,44069,45243,46560,47479,48110,48720,50119}

      Returns: 48

    47. {774,351,850,585,436,121,887,773,874,926,856,907,687,428,820,356,318,343,153,196,847,220,788,331,910,348,441,191,139,425,504,777,721,528,240,554,472,659,913,784,374,904,713,422,636,766,690,627,153,797}

      {407,268,729,34,706,548,526,72,814,4,985,823,967,714,915,150,897,481,503,593,816,131,795,358,959,841,546,564,395,585,445,528,524,367,396,512,658,898,947,920,104,782,952,422,437,54,255,850,14,153}

      {1450,2511,3643,5100,6130,6926,8018,9006,10162,11153,12459,12736,13246,14136,15030,16338,17341,18142,18586,19163,20197,21601,23019,24251,25733,26860,27564,28245,28574,29326,29722,30251,30508,30538,30980,31460,32004,32652,33445,34029,35333,36912,37627,38644,38937,39888,40535,41650,43443,44642}

      Returns: 33

    48. {527,61,29,320,375,703,999,905,403,190,561,928,383,964,467,382,955,88,166,198,960,555,946,660,281,706,205,341,717,524,27,836,180,666,544,427,619,913,799,781,673,97,947,924,957,713,674,16,301,125}

      {647,925,987,710,669,180,256,323,956,670,880,193,623,346,643,727,27,287,926,727,92,710,420,223,125,878,172,435,907,430,828,414,39,350,898,525,640,616,348,281,468,645,629,982,462,756,494,224,531,242}

      {1477,2555,2710,3328,3921,4899,5635,5848,7416,8046,8656,10084,11134,12433,13724,14108,15584,17087,18231,18711,20331,21666,22692,23622,24124,25529,27010,27753,28942,28987,30212,31554,33081,34243,35175,35953,36361,37162,37896,38167,38543,39749,41098,41479,42036,43006,43345,44462,45477,45966}

      Returns: 29

    49. {429,817,99,908,58,258,602,937,441,363,871,611,938,953,68,527,509,470,142,674,830,280,181,939,520,747,516,439,398,302,304,981,245,898,396,736,341,848,997,878,966,999,5,470,93,633,948,407,792,248}

      {102,549,189,606,749,510,422,30,487,740,691,976,205,619,392,311,607,339,314,567,144,191,57,692,867,755,151,446,928,181,843,654,462,372,142,987,124,451,529,798,814,304,672,810,47,343,584,146,954,917}

      {1012,1975,3118,4802,6205,7034,7680,7833,8848,9344,10056,10882,12426,13047,14433,15189,15525,15982,16800,17604,18390,19233,19513,21183,22014,22532,23772,24187,25057,26147,27195,28280,29703,30459,31436,32714,34158,35327,35559,36370,36823,37482,39257,39936,41321,42586,43640,44928,46539,47247}

      Returns: 7

    50. {552,733,512,887,663,678,906,461,235,894,211,700,612,372,701,346,384,808,934,330,237,600,873,581,902,286,638,597,26,226,458,140,66,819,941,388,496,315,850,546,727,68,969,215,137,158,504,789,517,408}

      {659,785,72,217,730,255,810,51,68,410,819,117,729,130,434,510,507,328,759,90,312,986,358,438,515,293,167,519,983,502,855,88,17,984,933,453,290,533,865,936,182,90,329,275,644,976,564,229,795,141}

      {1425,2175,3118,3714,4632,5357,6243,7657,7925,8952,10145,11656,12768,13663,14359,15059,15277,16303,17132,18806,18886,19927,21256,21880,22485,23456,24114,24716,26217,27060,28006,29277,29626,31588,31967,33091,33480,33911,35172,35947,37034,37950,39174,40464,40978,41357,42178,42843,43732,44960}

      Returns: 20

    51. {89,801,0,209,563,60,623,660,81,337,638,240,337,469,576,32,549,817,703,422,833,855,708,525,217,181,992,525,608,731,854,353,269,689,358,267,340,255,283,283,487,925,363,316,42,402,988,141,880,609}

      {604,967,845,518,372,490,761,675,991,800,922,373,245,394,487,386,491,855,403,73,256,464,303,442,104,138,334,438,172,583,17,352,103,504,50,723,639,23,449,528,788,221,505,781,319,839,864,860,297,752}

      {904,2002,3203,4115,5040,6037,6982,7397,8452,9361,10260,11665,12061,12769,12997,13700,14714,15596,16418,17168,18140,18867,19555,20353,21254,21635,22766,23544,24110,24657,25816,26703,27041,28241,29212,30011,30146,31144,31802,32349,32823,33944,35039,35752,36658,37567,38267,39575,41360,42441}

      Returns: 36

    52. {270,162,54,125,383,54,20,770,575,333,440,853,52,831,713,502,21,459,602,526,850,287,939,585,517,414,375,702,314,838,524,560,832,782,60,414,739,764,357,63,775,256,262,35,676,945,442,29,455,469}

      {565,697,570,965,242,70,54,963,260,265,580,928,164,631,782,243,614,164,900,553,309,849,940,129,443,551,113,403,846,242,268,865,939,620,389,296,620,634,11,687,27,53,580,272,869,945,362,816,714,885}

      {1087,1658,1965,2813,3908,4444,4586,6399,7784,8081,8911,10081,11882,13405,13978,14811,15850,17032,18294,19102,19711,20895,22106,23371,23688,24348,24896,25991,27286,28812,29221,29987,30475,31312,32397,33328,33988,34309,35654,36660,38529,39508,40080,40737,42221,42753,44287,45254,45942,46184}

      Returns: 24

    53. {22,649,647,505,427,764,534,214,354,869,124,72,627,654,375,997,13,178,919,825,751,942,832,310,496,740,346,835,680,977,293,400,480,667,173,104,951,270,600,798,387,818,286,21,639,566,913,653,959,524}

      {958,912,903,768,9,499,974,419,194,678,978,513,84,73,511,775,837,762,617,462,417,50,395,61,422,926,271,583,453,799,731,605,951,579,511,7,146,533,665,574,77,655,464,226,652,463,755,671,381,252}

      {1131,2159,2515,3198,4345,5290,6355,7509,7877,8991,10112,11039,12394,12772,13897,15166,16213,16671,17973,18260,18668,19435,20196,21546,22266,23270,24462,25676,26141,27152,27909,28349,29050,30069,30741,31358,32472,32751,33229,33597,34651,35947,37150,38001,39419,40164,41082,41727,42583,43632}

      Returns: 37

    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: