Statistics

Problem Statement for "PowerSupply"

Problem Statement

You have discovered a region in need of power, and as an enterprising businessperson, you have decided to build a power line there. The region is a cartesian plane, and consumers are represented as points on the plane. Your power line will be a single straight line that is horizontal, vertical, or parallel to any of two diagonals. Each potential consumer will purchase power from your line if and only if the distance between him and your line is less than or equal to D. This distance is measured as the Euclidean distance (the length of the shortest line segment between the point and the line). You would like to maximize your profit by maximizing the number of consumers using your power line.

You are given int[]s x and y containing the coordinates of the consumers. The ith elements of x and y represent the x and y coordinates of the ith consumer. Your are also given an int D, the value described above. Build your power line to maximize the number of consumers that will use it, and return this maximum number.

Definition

Class:
PowerSupply
Method:
maxProfit
Parameters:
int[], int[], int
Returns:
int
Method signature:
int maxProfit(int[] x, int[] y, int D)
(be sure your method is public)

Notes

  • More than one consumer may be located at the same point.
  • The power line may cross consumer points, in which case those consumers are at a distance of zero from the power line (see example 1).

Constraints

  • x and y will contain between 0 and 50 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element of x and y will be between -1000000 and 1000000, inclusive.
  • D will be between 0 and 1000000, inclusive.

Examples

  1. {0,3,0,0,0}

    {1,2,6,-4,1}

    1

    Returns: 4

  2. {-1000000,13,1000000}

    {0,0,0}

    0

    Returns: 3

    All points are crossed by the line, so all three consumers can connect to the power line even with D equal to 0.

  3. {-5,-2,2,8,-1}

    {1,2,1,2,8}

    1

    Returns: 4

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

    {-2,-3,4,6,9}

    2

    Returns: 4

  5. {-12245,-12345,123,123,-17,-17,-17}

    {-12345,-12345,735,735,999999,999999,999999}

    0

    Returns: 3

  6. {0,0,0,0,0,282,283,283,-1000000,-1000000,1000000,1000000}

    {0,0,0,0,0,282,283,283,1000000,1000000,-1000000,-1000000}

    200

    Returns: 10

  7. {0,0,0,0,0,282,283,283,-1000000,-1000000,1000000,1000000}

    {0,0,0,0,0,282,283,283,1000000,1000000,-1000000,-1000000}

    199

    Returns: 9

  8. {2,2,6}

    {-3,2,3}

    1

    Returns: 2

  9. {35,12456,-1000000}

    {0,0,0}

    0

    Returns: 3

  10. {0,1000000,0}

    {0,0,-1000000}

    0

    Returns: 2

  11. {177,177,177,224356}

    {177,177,177,134567}

    385298

    Returns: 4

  12. {177,177,177,224356}

    {177,177,177,134567}

    385299

    Returns: 4

  13. {0,7,0,100,107,100}

    {7,0,0,607,600,600}

    5

    Returns: 3

  14. {}

    {}

    0

    Returns: 0

  15. {0,7,0,100,107,100}

    {7,0,0,607,600,600}

    49

    Returns: 3

  16. {0,7,0,100,107,100}

    {7,0,0,607,600,600}

    50

    Returns: 5

  17. {0,7,0,100,107,100}

    {7,0,0,607,600,600}

    53

    Returns: 5

  18. {0,7,0,100,107,100}

    {7,0,0,607,600,600}

    54

    Returns: 6

  19. {40,24}

    {24,48}

    3

    Returns: 2

  20. {40,24}

    {24,48}

    1

    Returns: 1

  21. {40,24}

    {24,48}

    2

    Returns: 1

  22. {}

    {}

    1

    Returns: 0

  23. {2,2,2,3,-7,732784}

    {2,2,2,3,-7,732784}

    0

    Returns: 6

  24. {346732,346732,346732,877123,877123,877123,877123}

    {877123,877123,877123,0,0,0,0}

    0

    Returns: 4

  25. {0,12,0,100,112,100,101}

    {12,0,0,612,600,600,601}

    5

    Returns: 4

  26. {0,12,0,100,112,100,101}

    {12,0,0,612,600,600,601}

    56

    Returns: 7

  27. {0,12,0,100,112,100,101}

    {12,0,0,612,600,600,601}

    55

    Returns: 6

  28. {565436}

    {-565743}

    0

    Returns: 1

  29. {-549336,-548882,903031,-615918,293014,-361878,-667754,179873,-714192,814169,-506630,895387,-612564,-878892,937644,-616282,-193049,799086,-961144,313294,-581415,417360,-698296,194354,-426631,-310439,143024,-294737,969218,100493,338617,385080,-562076,-497365,931731,-221124,665890,-21586,788538,-544304,315903,-518672,564372,485068,906151,-11329,239064,-741348,565877,-265770}

    {-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091,-460091}

    0

    Returns: 50

  30. {-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708,-698708}

    {-666183,928102,563443,283370,982622,-408891,-405759,597007,8158,891074,977074,-392918,878545,-884396,698749,-76986,-50254,609040,-97454,-433755,-896054,893145,271336,656323,782885,-723002,-605157,428170,664094,-515903,342712,-6668,-816826,-409361,4396,555554,711530,-355997,-98544,-943795,92282,846091,-329521,939461,470328,995779,-726397,-842220,-838990,465590}

    0

    Returns: 50

  31. {-727030,274129,-214242,872547,-526875,414474,-400361,-288821,-135692,-468154,-370711,-79572,684351,898804,-868212,889896,-410555,-516068,-78878,-540501,-542676,948693,546927,-865838,196977,943565,-335954,-826817,-628829,974480,345232,-715917,-311645,-634014,-586603,186431,-788219,-487983,-606299,-105374,421044,651962,872306,-442535,-594450,963798,-133362,-317423,891982,821407}

    {727030,-274129,214242,-872547,526875,-414474,400361,288821,135692,468154,370711,79572,-684351,-898804,868212,-889896,410555,516068,78878,540501,542676,-948693,-546927,865838,-196977,-943565,335954,826817,628829,-974480,-345232,715917,311645,634014,586603,-186431,788219,487983,606299,105374,-421044,-651962,-872306,442535,594450,-963798,133362,317423,-891982,-821407}

    0

    Returns: 50

  32. {978046,113249,97006,-255241,-629587,220581,-913435,241648,360687,556348,883919,378844,-19909,290349,-330880,930574,-481659,-77607,353142,238702,-936504,-778572,620691,268816,633084,558944,940686,432228,844778,-752465,-905255,761080,-871210,-160214,94332,-601310,-784476,191374,469520,-421705,648003,-390400,927401,741451,434574,-450634,-857727,-438965,762221,-877279}

    {978046,113249,97006,-255241,-629587,220581,-913435,241648,360687,556348,883919,378844,-19909,290349,-330880,930574,-481659,-77607,353142,238702,-936504,-778572,620691,268816,633084,558944,940686,432228,844778,-752465,-905255,761080,-871210,-160214,94332,-601310,-784476,191374,469520,-421705,648003,-390400,927401,741451,434574,-450634,-857727,-438965,762221,-877279}

    0

    Returns: 50

  33. {300001,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    {-251613,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    195025

    Returns: 25

  34. {300002,300001,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    {-251613,-251613,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    195024

    Returns: 24

  35. {300002,300001,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    {-251613,-251613,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    195025

    Returns: 25

  36. {300002,300001,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    {-251613,-251613,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    195026

    Returns: 26

  37. {332803,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000}

    {333053,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    235416

    Returns: 25

  38. {332803,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000}

    {333053,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    235415

    Returns: 24

  39. {332803,332804,332803,332804,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000}

    {333053,333053,333054,333054,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    235416

    Returns: 25

  40. {332803,332804,332803,332804,0,0,0,0,0,0,0,0,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000}

    {333053,333053,333054,333054,0,0,0,0,0,0,0,0,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,-1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000}

    235417

    Returns: 28

  41. {-873653,-899569,999999,1000000,-736123,-999999,999129,913456}

    {-999999,725999,-1000000,819415,991356,891456,-693567,-993567}

    169399

    Returns: 6

  42. {-873653,-899569,999999,1000000,-736123,-999999,999129,913456}

    {-999999,725999,-1000000,819415,991356,891456,-693567,-993567}

    169398

    Returns: 5

  43. {-999875,-999845,998997,999153,-990246,-724673,987654,879257}

    {-999567,999964,-999863,997572,-999536,-999861,996123,756845}

    100287

    Returns: 5

  44. {-999875,-999845,998997,999153,-990246,-724673,987654,879257}

    {-999567,999964,-999863,997572,-999536,-999861,996123,756845}

    100288

    Returns: 6

  45. {-999716,-999716,999716,999716}

    {-999943,999943,-999943,999943}

    999716

    Returns: 4

  46. {-999716,-999716,999716,999716}

    {-999943,999943,-999943,999943}

    999715

    Returns: 3

  47. {-999716,-999716,999716,999716}

    {-999943,999943,-999943,999943}

    707066

    Returns: 2

  48. {-999716,-999716,999716,999716}

    {-999943,999943,-999943,999943}

    707067

    Returns: 3

  49. {-999883,-999883,999883,999883}

    {-999419,999419,-999419,999419}

    999419

    Returns: 4

  50. {-999883,-999883,999883,999883}

    {-999419,999419,-999419,999419}

    999418

    Returns: 3

  51. {-999883,-999883,999883,999883}

    {-999419,999419,-999419,999419}

    707025

    Returns: 3

  52. {-999883,-999883,999883,999883}

    {-999419,999419,-999419,999419}

    707024

    Returns: 2

  53. {-1000000,-1000000,1000000,1000000}

    {-1000000,1000000,-1000000,1000000}

    1000000

    Returns: 4

  54. {-1000000,-1000000,1000000,1000000}

    {-1000000,1000000,-1000000,1000000}

    999999

    Returns: 3

  55. {-1000000,-1000000,1000000,1000000}

    {-1000000,1000000,-1000000,1000000}

    707107

    Returns: 3

  56. {-1000000,-1000000,1000000,1000000}

    {-1000000,1000000,-1000000,1000000}

    707106

    Returns: 2

  57. {-1000000,-1000000,1000000,1000000}

    {-1000000,1000000,-1000000,1000000}

    0

    Returns: 2

  58. {-906296,-923656,968477,910988,-962103,-947183,-977147,-973001,938225,913030,909736,918896,-934491,966848,-980485,932600,932661,-925964,-967752,-904175,905444,-925593,902068,-944576,-929233,-949907,-932221,979852,926395,918131,969093,964941,946572,-919219,-943219,-994818,-977474,-906542,-948881,951154,-976591,-993206,997077,-958434,932195,-918612,944310,965334,988597,-934748}

    {936155,-974329,-978898,914947,934381,950182,-990613,944323,-930438,-988913,911649,986796,997934,947967,-914134,-969469,-993210,-950231,929394,-982295,-903387,-957386,-957846,-951729,-915898,-958714,-917747,927160,944354,-986073,975050,-996914,999912,922609,-904849,-977326,-974639,959133,973319,978889,994324,-977650,-931254,-919033,-981252,970471,-990736,926969,-989155,-919127}

    971499

    Returns: 41

  59. {-967471,-911844,936461,967942,982282,958535,-941762,970652,-980362,-948798,-937623,973378,908744,948368,-920656,989725,931465,963464,920911,-954893,-931650,989387,917175,901817,900434,-960425,-905318,961041,944143,-964708,-948329,-948157,992518,901931,-996078,-985206,902645,-959055,983315,-954719,-918995,-906345,962803,-949534,953914,-977029,971103,936532,-987227,-903568}

    {996699,945875,-949898,-952613,-942875,-915075,965614,970782,-923779,952673,-943659,-915645,915881,-988023,-925945,992087,973832,-936419,993043,927447,985438,926911,962489,954323,923690,-957231,-966979,908205,971092,-936051,-936406,916989,924946,959527,-946252,-962506,973144,960980,-943671,940384,955407,-916241,962338,-997486,911703,959413,986359,972727,-985197,-911086}

    978524

    Returns: 45

  60. {974602,961597,-987766,980818,998689,-970274,961606,-930856,990459,-901970,-911423,-963752,-927840,-985017,962429,943492,933738,909577,-934426,-935474,-912556,-956482,949640,998256,910729,-901530,-962111,983053,922391,-984551,912411,953118,918669,-948073,-910628,-933226,998690,-968572,908754,916603,996062,946331,-904516,-955980,901303,912106,957121,-980020,-982473,-978359}

    {-950956,-993727,994262,-932207,914643,917048,-953410,-917660,-908555,-913519,954974,-957719,-991939,-977248,-905158,907540,-997860,925915,-924277,-982741,-904378,979012,-959643,981224,981738,-916392,948344,973214,952009,-972775,978757,-921266,951583,-925495,-950482,944267,980515,-918394,955107,-908113,925129,-973950,-928026,-929065,928603,947395,973562,-946937,-937186,-936512}

    934990

    Returns: 44

  61. {970393,997948,958891,-927063,961842,-915819,-953498,918520,913123,-984690,998200,926360,911687,932449,-996413,993301,-953466,935726,985083,903886,-920880,967147,-954147,981109,995639,-995160,-948335,-933023,-991609,945958,966524,982283,-912794,-915899,-949973,-979745,-933113,-990590,-947332,983789,948627,969504,-972467,972845,915386,993781,903210,987525,921208,965039}

    {950557,-929363,925797,946728,932754,-960590,-910177,-993117,-948626,970702,924318,-925812,-913737,917472,-986694,928823,971526,911269,902050,-951966,902032,-902318,947594,962423,-932787,-913310,948133,943117,-999251,934510,-964287,993104,957816,900023,-947533,994905,-981071,-969920,-915777,-944706,943246,-978461,983987,-951252,-955313,932917,-940679,923574,-905197,954268}

    994439

    Returns: 49

  62. {-975700,918023,-982712,-998256,964070,928291,900334,-997534,958773,-949380,-909868,913839,-957781,-916652,-941572,905216,-905277,-924287,-911655,-997554,976277,965282,-934313,-928082,906898,909688,929977,-902717,-948592,990081,-910579,-985601,-995973,-963793,-919072,961063,940059,940413,-917809,964493,969951,957512,-965647,981379,970332,934690,907674,-959323,-917941,998729}

    {963284,996871,-991166,-994719,976501,981373,937803,915145,-944025,939796,-995394,-959734,914951,-980955,916185,996795,-914667,903644,939057,-957468,-902424,942704,943680,905148,954985,901618,-997911,924315,944076,917699,-906723,990717,-998584,928189,-951606,914889,-916548,-942348,-994725,-939145,-972506,910990,968176,-900057,-911165,939317,-999989,-920936,-921676,999128}

    923966

    Returns: 39

  63. {-994387,912845,916710,911331,-985723,955428,902882,-932557,941217,911183,950606,960506,934463,-940310,-966320,945855,-975189,980885,-904450,943933,950866,-987476,-997977,946382,931125,-928775,972380,-908645,-915813,-959862,958770,999255,-954347,906307,-905013,939440,931262,-901814,-988973,961294,-947902,993680,935669,951568,-970260,-930002,905399,-979534,904079,997891}

    {914042,-936348,-975015,-903681,929851,-989202,-913569,913751,979837,981440,-952426,-974455,-956842,-961847,-909372,-913525,-941573,962572,968012,-983889,994188,-997405,954856,947929,993137,940334,-917863,958742,951255,-961335,-991279,-965548,968951,-966033,913307,-998798,987169,-933775,929001,-996722,994751,944336,924343,924842,-945433,-987013,933993,970102,972910,-977627}

    179292

    Returns: 30

  64. {-906389,951730,-969728,-977487,967568,-941404,980819,-938715,-960738,-927380,901723,934101,-998736,958903,997544,920920,-930223,908836,902676,-968335,-914245,-994437,-987516,-945170,-956894,-928212,963917,-970664,-934100,946905,-989898,974430,-962237,940000,-902713,986583,-929883,903516,949019,-919020,967447,-997258,-954417,943747,-964438,-916019,-945464,994007,-999614,-938975}

    {986862,-959441,905041,970461,-960183,999414,-919598,934745,-988817,970098,-938924,979454,919183,-908099,-962250,960473,927642,-905101,954683,943666,-986142,-918950,-947030,958766,915425,-936604,916304,-954799,-978536,-922163,952530,-996776,-910840,-916262,-907761,966480,917014,967339,928007,953254,-915679,-924266,-964593,916813,907763,983441,-913525,-934120,910557,939007}

    151819

    Returns: 30

  65. {-906389,951730,-969728,-977487,967568,-941404,980819,-938715,-960738,-927380,901723,934101,-998736,958903,997544,920920,-930223,908836,902676,-968335,-914245,-994437,-987516,-945170,-956894,-928212,963917,-970664,-934100,946905,-989898,974430,-962237,940000,-902713,986583,-929883,903516,949019,-919020,967447,-997258,-954417,943747,-964438,-916019,-945464,994007,-999614,-938975}

    {986862,-959441,905041,970461,-960183,999414,-919598,934745,-988817,970098,-938924,979454,919183,-908099,-962250,960473,927642,-905101,954683,943666,-986142,-918950,-947030,958766,915425,-936604,916304,-954799,-978536,-922163,952530,-996776,-910840,-916262,-907761,966480,917014,967339,928007,953254,-915679,-924266,-964593,916813,907763,983441,-913525,-934120,910557,939007}

    1000000

    Returns: 50

  66. {-975700,918023,-982712,-998256,964070,928291,900334,-997534,958773,-949380,-909868,913839,-957781,-916652,-941572,905216,-905277,-924287,-911655,-997554,976277,965282,-934313,-928082,906898,909688,929977,-902717,-948592,990081,-910579,-985601,-995973,-963793,-919072,961063,940059,940413,-917809,964493,969951,957512,-965647,981379,970332,934690,907674,-959323,-917941,998729}

    {963284,996871,-991166,-994719,976501,981373,937803,915145,-944025,939796,-995394,-959734,914951,-980955,916185,996795,-914667,903644,939057,-957468,-902424,942704,943680,905148,954985,901618,-997911,924315,944076,917699,-906723,990717,-998584,928189,-951606,914889,-916548,-942348,-994725,-939145,-972506,910990,968176,-900057,-911165,939317,-999989,-920936,-921676,999128}

    0

    Returns: 1

  67. {-999875,-999845,998997,999153,-990246,-724673,987654,879257}

    {-999567,999964,-999863,997572,999536,999861,-996123,-756845}

    100288

    Returns: 6

  68. {-724673,987654}

    {999861,-996123}

    100288

    Returns: 2

  69. {-599458, -540917, -168259, 962508, 838114, 51667, 821351, 137626, -677178, 624494, 37818, 988703, -726164, 205458, 317963, 54476, -57510, -916804, 348346, 712641}

    {-285312, -112344, -716768, -619638, 370492, -836865, 588772, -7272, 757488, 469659, 774708, -162669, -218848, 293033, 282441, 902767, -694522, 290387, -967079, 771444}

    91

    Returns: 2

  70. {-263153, -444276, -834531, 94853, 779941, -682992, -504958, -375097, 592207, -882051}

    {-270371, -169328, 362629, -382528, -346471, 818360, -596077, -624832, -609580, 637926}

    6585

    Returns: 2

  71. {511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586}

    {-500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475}

    31194

    Returns: 4

  72. {468431, 786996, 703361, 334429, 717401}

    {-625108, 364603, 282455, -527052, 956784}

    526

    Returns: 2

  73. {612035, -402577, 752852, 979071}

    {260310, 584217, 118238, -606870}

    444

    Returns: 2

  74. {612035, 752852}

    {260310, 118238}

    444

    Returns: 2

  75. {-5, -2, 2, 8, -1 }

    {1, 2, 1, 2, 8 }

    1

    Returns: 4

  76. {90, 80, 70, 60, 50, 40, 30, 20, 10, 0 }

    {10, 0, 30, 20, 50, 40, 70, 60, 90, 80 }

    8

    Returns: 10

  77. {511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586 }

    {-500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475 }

    31194

    Returns: 4

  78. {999, 999, 999, 999 }

    {333, 334, 335, 336 }

    1

    Returns: 4

  79. { }

    { }

    111

    Returns: 0

  80. {1 }

    {1 }

    1

    Returns: 1

  81. {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    1000000

    Returns: 49

  82. {0, 1, 2, 3 }

    {3, 2, 1, 0 }

    1

    Returns: 4

  83. {-1000000, 1000000, 2000, -2200 }

    {1000000, -1000000, 2000, -2299 }

    3005

    Returns: 4

  84. {511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586, -806739, 358447, 685932, 663609, 276080, -213586, 511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586, -806739, 358447, 685932, 663609, 276080, -213586 }

    {-500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475, -806739, 358447, 685932, 663609, 276080, -213586, -500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475, -806739, 358447, 685932, 663609, 276080, -213586 }

    100

    Returns: 12

  85. {5, 0 }

    {0, 5 }

    0

    Returns: 2

  86. { }

    { }

    512

    Returns: 0

  87. {-3006, 0, -6012, -3006, -9018, -6012 }

    {0, 3007, 3006, 6012, 6012, 9018 }

    2125

    Returns: 4

  88. {511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    {-500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

    31194

    Returns: 44

  89. {1000000, -1000000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    {1000000, -1000000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    999999

    Returns: 50

  90. { }

    { }

    4

    Returns: 0

  91. {1231, 43434, 4545, 6565, 76767, 98989, 89089, 89089, 890890, 5656, 989, 9080, 98089, 8908, 66, 66, 77, 888, 899, 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, 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 }

    12344

    Returns: 50

  92. {511590, -60297, 337900, -322958, -806739, 358447, 685932, 663609, 276080, -213586 }

    {-500859, -840607, -792296, -379621, -890856, 362559, -98535, 617148, -128203, 802475 }

    38917

    Returns: 4

  93. {10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000, 10000 }

    {-10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000, -10000 }

    1

    Returns: 50

  94. {100, 101, 105 }

    {7, 12, 8 }

    0

    Returns: 2

  95. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 11, 12, 13, 14, 15, 161, 17, 18, 19, 20, 21, 22, 23, 24 }

    {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 22, 22, 22, 2, 2, 2, 2, 2, 2, 2, 2, 2, 22, 2, 2 }

    10000

    Returns: 50

  96. {0, 1, 2, 43, 5, 65, 658, 87, 56, 243, 653, 7, 76, 45, 23, 25, 568, 856, 423, 342, 65, 5, 6, 7, 67, 65, 2, 234, 523, 54, 54, 365, 56, 234, 312, 321, 54, 2, 3, 45, 2, 5, 65 }

    {5, 54, 0, 0, 9, 45, 87, 4, 321, 653, 87, 65, 54, 32, 234, 523, 7, 875, 345, 253, 56, 76, 857, 25, 234, 321, 354, 76, 56, 3, 324, 21, 65, 56, 234, 423, 47, 67, 423, 43, 4, 234, 234 }

    30

    Returns: 23

  97. { }

    { }

    0

    Returns: 0

  98. {111, 222, 333, 444, 555, 666, 777, 888, 999 }

    {111, 222, 333, 444, 555, 666, 777, 888, 999 }

    0

    Returns: 9

  99. {1, 2, 3 }

    {10, 1, 30 }

    1

    Returns: 3

  100. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50 }

    {100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 100000, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 100000, 200000, 300000, 400000, 500000, 600000, 700000, 800000, 900000, 1, 2, 3 }

    0

    Returns: 9

  101. {10000, -10000 }

    {-10000, 10000 }

    1

    Returns: 2

  102. {-589295, 674464, 803660, 551051, -409085 }

    {396429, 503609, -627080, -465065, 405660 }

    456934

    Returns: 4

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

    {1, 100, 200, 300, 400 }

    6

    Returns: 5

  104. { }

    { }

    2

    Returns: 0

  105. {-1, 0, 1 }

    {-1, 20000, -1 }

    1

    Returns: 3

  106. {-5, -3, -1, 2, 2, 3, 5, 6, 7, 8 }

    {7, 5, 6, 5, 2, 1, 7, -1, 4, -5 }

    2

    Returns: 8

  107. {0 }

    {0 }

    0

    Returns: 1

  108. {0, 0, 1, 1, 2, 2, 3, 3 }

    {-1, 1, -1, 1, -1, 1, -1, 1 }

    1

    Returns: 8

  109. {-1000000, 1000000, 0 }

    {-1000000, 1000000, 19601 }

    6930

    Returns: 2

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: