Statistics

Problem Statement for "TrappingRabbit"

Problem Statement

There is a grass field that is represented by a 1000 by 1000 grid. Initially, a rabbit is present on the square located at coordinates (1,1) (1-based). The rabbit can move to a horizontally or vertically adjacent square in one second and can only move that way.

You are going to trap the rabbit. To do so, you have set some traps. The i-th trap is located on a square given by trapX[i] and trapY[i] as its X and Y coordinates (1-based) respectively.

Return the minimum number of seconds so that after this time has passed there is a non-zero chance that the rabbit has fallen into one of your traps (the rabbit falls into one of your traps if it is in the same square as one of your traps).

Definition

Class:
TrappingRabbit
Method:
findMinimumTime
Parameters:
int[], int[]
Returns:
int
Method signature:
int findMinimumTime(int[] trapX, int[] trapY)
(be sure your method is public)

Constraints

  • trapX will contain between 1 and 50 elements, inclusive.
  • trapY will contain between 1 and 50 elements, inclusive.
  • trapX and trapY will contain the same number of elements.
  • Each element of trapX and trapY will be between 1 and 1000, inclusive.
  • All traps will have distinct locations.
  • No trap will be located at coordinates (1,1).

Examples

  1. {4,6,8}

    {1,2,1}

    Returns: 3

    If the rabbit goes 3 squares in the positive X direction it will fall to your first trap. Going 3 squares requires 3 seconds.

  2. {5,4,3}

    {5,4,3}

    Returns: 4

    The rabbit will be trapped within 4 seconds if it moves 2 squares in the positive X direction and 2 squares in the positive Y direction.

  3. {1000}

    {1000}

    Returns: 1998

  4. {358,585,940,750,736,913,873,565,513,856,289,583,882,135,841,198,707,352,634,526,534,868,983,802,329,606,969,383,456,509,694,247,833,845,253,816,798,622,188,106,302,708,883,821,196,885,742,689,311,719}

    {145,262,496,305,629,607,229,198,995,517,310,535,506,801,219,703,376,178,948,301,235,816,251,460,248,39,845,803,559,155,324,29,901,110,16,370,841,587,385,685,207,943,87,788,296,403,723,667,256,123}

    Returns: 267

  5. {711,443,169,871,409,895,792,235,686,792,911,529,34,394,590,694,173,217,158,520,893,567,102,323,58,250,817,72,945,988,293,90,602,625,222,695,609,436,641,709,8,522,305,282,876,541,149,59,747,907}

    {155,929,487,810,225,354,681,740,189,851,950,34,86,817,522,177,749,819,294,643,59,227,21,677,997,240,528,111,551,871,554,272,879,925,925,983,797,23,123,507,58,787,350,900,646,36,521,143,247,330}

    Returns: 64

  6. {152,198,853,333,992,959,728,920,640,687,714,343,830,585,83,215,685,355,408,233,148,475,41,508,725,415,140,129,111,484,176,221,660,632,82,634,204,488,188,262,873,498,857,83,713,404,315,973,631,20}

    {356,230,353,976,428,182,305,748,281,399,825,410,438,264,560,393,108,752,31,276,223,462,140,194,31,114,242,975,329,377,375,897,780,189,61,932,804,770,354,86,554,51,744,532,530,659,22,515,748,380}

    Returns: 141

  7. {531,5,47,931,610,150,794,947,677,951,140,650,88,649,569,323,723,695,665,556,118,816,834,741,9,713,347,901,655,312,721,909,422,890,654,738,217,750,893,111,727,767,671,705,665,798,857,458,583,182}

    {817,365,44,65,674,35,542,294,775,675,506,758,328,422,418,53,761,409,250,875,83,430,615,674,112,297,150,41,34,700,624,108,53,379,757,338,832,856,741,509,720,728,560,702,772,516,400,703,866,689}

    Returns: 89

  8. {240,554,835,153,224,396,86,352,480,69,43,503,782,729,946,637,660,15,640,339,312,284,622,255,23,790,184,937,261,418,119,168,294,287,984,70,409,65,907,311,319,143,205,183,281,69,310,993,383,450}

    {807,380,347,83,228,883,948,764,456,401,756,424,375,26,240,349,177,584,691,734,667,454,307,906,972,736,530,422,504,185,398,86,936,338,305,248,816,418,82,706,968,873,106,727,763,476,879,382,19,756}

    Returns: 234

  9. {296,943,584,760,980,551,485,358,205,657,530,177,989,773,966,260,883,797,473,995,226,811,239,344,640,729,345,321,551,143,652,871,735,241,840,616,634,838,98,854,559,954,746,334,896,572,957,610,108,569}

    {20,745,429,860,435,882,5,940,960,840,21,968,931,670,335,843,561,281,896,53,345,833,780,1000,631,524,999,28,756,402,109,13,428,969,443,128,894,563,67,849,752,380,980,999,233,516,328,942,277,883}

    Returns: 163

  10. {648,703,86,489,944,523,288,131,160,445,223,275,237,221,753,274,270,503,631,326,244,579,53,733,800,42,298,365,755,657,355,190,287,761,917,446,181,716,93,399,909,570,374,78,171,607,966,506,136,189}

    {671,46,769,28,996,426,236,808,402,98,74,442,289,420,121,289,607,292,521,884,199,476,331,103,975,914,547,955,950,32,242,244,316,728,929,368,921,546,314,810,66,66,140,966,784,32,332,615,145,138}

    Returns: 279

  11. {252,332,886,971,105,93,375,670,708,270,712,246,89,495,537,779,530,320,660,246,292,683,920,655,441,110,333,387,72,491,672,977,368,566,605,792,390,442,805,98,299,632,271,544,298,806,970,130,747,236}

    {308,881,878,678,696,788,59,372,706,719,356,317,577,217,13,1000,242,470,638,255,515,832,971,499,107,421,190,165,796,664,179,124,128,951,958,268,386,586,514,659,531,436,791,365,463,900,245,338,7,558}

    Returns: 432

  12. {314,337,639,964,929,527,580,110,464,983,460,680,825,379,246,454,850,144,690,691,418,65,896,51,637,9,523,372,608,779,588,984,984,279,577,246,482,152,65,964,851,619,970,219,401,547,930,968,756,329}

    {556,965,214,987,346,337,586,575,81,439,190,25,842,610,387,878,81,398,453,423,605,663,710,781,266,816,75,958,279,158,306,308,154,652,247,403,148,382,739,365,811,206,54,305,761,472,76,91,898,726}

    Returns: 522

  13. {282,207,436,971,581,462,989,537,847,529,715,774,939,616,524,713,965,570,360,423,875,454,589,796,873,635,791,724,370,373,683,899,729,720,839,651,856,867,877,936,634,974,308,470,916,592,512,352,665,535}

    {744,943,712,491,261,951,340,409,360,330,992,673,6,560,675,977,824,915,867,334,197,484,299,695,724,979,461,958,564,730,405,416,919,148,386,742,79,363,841,868,326,37,452,324,940,541,618,682,690,266}

    Returns: 755

  14. {256,180,744,782,901,673,763,760,513,449,763,409,815,317,725,939,502,900,841,792,926,595,824,640,604,851,178,753,434,898,819,874,984,795,508,812,960,266,582,684,883,791,566,389,981,498,700,865,741,995}

    {784,967,990,805,561,675,731,666,640,563,628,738,680,913,708,682,627,228,587,238,941,678,834,699,948,421,995,423,584,210,950,587,61,633,793,494,203,955,641,699,987,939,549,666,998,933,460,960,746,992}

    Returns: 1010

  15. {907,804,906,701,783,844,844,967,584,987,944,978,787,825,871,608,890,914,512,932,943,653,755,853,434,920,878,959,918,928,457,542,940,774,738,846,919,597,578,691,746,712,740,873,901,704,851,582,708,711}

    {474,608,690,741,898,761,814,774,995,789,483,358,572,571,744,958,681,821,835,872,914,732,699,676,937,630,931,453,884,879,905,805,469,567,894,509,516,855,776,735,838,685,663,553,903,792,857,851,822,894}

    Returns: 1334

  16. {825,969,963,959,839,989,967,997,893,816,752,922,947,965,975,881,915,797,859,821,925,855,851,989,972,960,859,877,984,884,946,825,958,928,823,861,951,906,901,828,901,955,839,877,841,994,997,951,916,867}

    {924,935,995,898,959,924,986,922,882,945,981,839,914,850,899,971,835,941,913,933,807,991,994,862,806,876,962,928,902,896,919,1000,788,909,939,942,841,921,935,974,985,975,936,875,889,760,843,922,974,994}

    Returns: 1728

  17. {11,2,3,2,11,4,22,22,9,20,686,906,626,257,872,394,454,242,302,545,306,841,830,187}

    {18,27,26,28,19,25,8,7,20,932,437,897,408,4,194,987,799,365,194,70,824,664,187,227}

    Returns: 27

  18. {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}

    {443,225,835,937,108,785,995,663,165,865,1000,567,292,249,779,451,934,206,331,922,906,548,685,616,737,372,197,107,576,521,72,633,513,29,373,585,495,241,914,439,473,909,59,244,129,900,313,236,493,668}

    Returns: 28

  19. {168,139,84,525,134,970,933,852,80,619,884,558,67,509,589,138,346,11,662,400,226,671,25,989,153,181,461,132,705,150,858,471,607,104,244,726,801,740,34,382,728,417,103,470,946,159,897,959,930,46}

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

    Returns: 10

  20. {32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32}

    {506,268,200,49,758,755,28,563,298,646,516,610,951,539,417,123,274,306,806,967,865,102,139,467,188,63,483,222,302,307,88,693,875,270,213,748,276,480,171,870,649,558,616,679,919,851,70,472,410,744}

    Returns: 58

  21. {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    {891,709,706,930,663,535,692,945,598,640,556,161,997,948,178,766,148,735,870,476,822,58,249,523,507,781,744,653,244,702,444,834,391,728,357,839,116,200,872,762,103,548,998,121,496,885,399,667,551,38}

    Returns: 1036

  22. {334,363,957,152,291,884,586,496,824,895,973,589,108,867,309,414,672,290,822,499,60,474,83,336,192,318,637,502,638,990,658,546,505,636,265,930,426,955,557,397,301,385,72,131,535,839,850,317,607,545}

    {15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15}

    Returns: 73

  23. {702,489,32,868,746,894,485,716,445,377,8,546,944,349,59,927,639,414,288,559,582,710,410,334,878,505,483,552,283,418,817,300,768,839,286,704,20,115,832,355,958,275,343,223,928,523,550,678,800,657}

    {370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370,370}

    Returns: 376

  24. {327}

    {731}

    Returns: 1056

  25. {699,790,179}

    {871,790,71}

    Returns: 248

  26. {91,424,567,807}

    {9,145,263,727}

    Returns: 98

  27. {841,6,760,262,710,885}

    {92,323,302,456,773,409}

    Returns: 327

  28. {97,15,467,304,522,200,65,47,552}

    {57,995,746,945,746,999,188,359,238}

    Returns: 152

  29. {294,575,273,184,885,45,783,319,907,859,212,251,705,278,298}

    {163,161,41,101,764,662,38,927,929,281,471,400,656,601,980}

    Returns: 283

  30. {390,188,9,288,234,763,912,906,519,908,261,516,296,599,343,987,574,769}

    {265,425,448,39,854,842,708,536,454,364,927,506,461,828,551,60,317,298}

    Returns: 325

  31. {122,232,343,699,271,697,786,231,772,380,825,38,401,868,893,589,385,937,114,758,169,854,120,110}

    {965,920,638,331,847,123,381,546,449,198,677,162,455,887,250,985,689,668,213,465,465,995,212,855}

    Returns: 198

  32. {445,794,429,663,107,498,913,600,77,413,672,984,316,847,324,599,368,231,672,389,873,697,654,25,1,372,362}

    {670,915,191,158,76,353,267,332,682,460,923,660,611,929,371,451,485,624,331,603,909,157,362,963,105,249,128}

    Returns: 104

  33. {931,151,773,629,650,813,898,563,991,227,744,789,120,667,55,88,830,827,864,755,127,998,141,597,461,106,753,317,893,459}

    {308,124,190,690,670,766,398,826,737,586,836,349,213,310,457,692,730,430,353,971,8,505,388,908,961,858,774,85,274,465}

    Returns: 133

  34. {446,480,729,105,553,588,222,256,98,184,907,434,320,298,412,246,705,203,872,64,878,17,640,431,826,78,100,799,295,807,31,288,969,46,910,989}

    {607,684,978,856,746,603,564,47,35,391,659,151,650,901,716,295,430,423,698,485,485,923,526,391,809,836,858,698,533,887,589,926,740,919,899,735}

    Returns: 131

  35. {984,273,941,77,378,128,10,541,951,435,440,557,980,769,373,102,504,282,485,762,626,855,253,301,433,180,168,652,42,117,661,693,790,654,967,655,537,457,548}

    {674,138,706,102,905,826,374,582,109,549,589,984,888,597,491,752,600,848,584,902,276,329,445,990,650,182,603,775,124,504,740,991,518,46,687,518,610,778,360}

    Returns: 164

  36. {549,604,28,382,311,716,280,813,953,289,212,259,290,264,584,23,358,425,410,427,333,586,364,814,66,938,531,411,500,822,634,215,865,576,742,751,350,27,528,752,352,160}

    {647,164,778,870,755,502,152,260,221,957,955,736,526,26,764,63,595,162,489,287,618,583,982,556,521,645,191,268,815,453,39,850,953,894,164,566,606,359,593,715,747,350}

    Returns: 84

  37. {101,341,950,180,921,532,804,528,120,745,826,136,307,890,731,476,393,609,670,866,276,93,745,778,624,906,825,104,759,364,419,126,327,184,990,431,210,587,854,845,550,441,243,844,851}

    {603,472,512,788,52,905,617,574,347,75,342,861,513,251,836,39,125,359,361,661,946,763,28,459,740,534,155,859,967,722,266,186,464,360,651,976,25,313,937,5,441,782,755,87,874}

    Returns: 233

  38. {487,1000,373,807,441,141,916,917,646,365,506,106,127,808,827,303,443,890,809,649,398,114,688,340,541,340,96,20,219,848,246,514,591,569,211,190,708,271,836,639,720,445,440,468,542,524,621,870}

    {881,832,765,713,490,445,839,289,99,944,707,313,780,97,554,778,528,635,257,898,654,887,856,131,481,658,726,76,608,514,4,455,119,557,341,738,572,666,909,407,243,229,799,147,930,816,148,610}

    Returns: 94

  39. {25,60,14,47,37,60,20,45,42,42,35,39,58,28,62,53,40,11,44,20,14,22,55,34,8,62,46,35,55,41,36,63,63,31,46,1,9,15,41,26,1,11,50,28,25,8,44,63,5,31}

    {26,55,5,52,41,37,37,54,34,11,61,1,40,54,13,11,53,40,41,1,22,24,54,3,45,48,49,38,46,14,41,49,35,3,64,33,40,23,46,37,48,3,62,34,62,53,14,48,44,15}

    Returns: 12

  40. {203,80,145,65,90,23,78,187,171,152,85,136,105,183,190,197,110,15,4,160,21,28,148,109,25,202,122,148,29,27,116,65,114,101,53,58,132,177,27,21,205,101,17,159,24,27,70,182,111,16}

    {16,178,110,14,13,106,205,200,27,195,175,158,115,45,38,162,26,97,147,5,34,119,136,52,167,86,101,94,114,168,181,63,193,115,166,16,157,138,100,141,211,1,110,54,148,60,63,63,157,9}

    Returns: 23

  41. {394,246,156,469,164,191,456,58,218,180,485,444,261,370,380,60,259,187,350,510,51,501,284,40,507,168,398,326,67,260,333,457,503,89,312,131,392,413,243,301,364,489,355,226,154,252,308,161,271,438}

    {46,89,246,291,220,39,129,187,167,322,333,358,27,417,1,2,28,46,473,165,92,326,291,278,486,317,450,337,407,215,431,7,160,464,371,284,261,341,174,40,33,137,147,247,288,257,106,9,387,328}

    Returns: 60

  42. {729,540,92,426,613,558,190,613,687,263,512,367,718,512,198,507,466,477,694,72,441,331,578,94,276,221,315,479,346,317,167,449,313,619,19,704,373,595,529,277,634,544,95,477,273,641,521,351,34,361}

    {386,30,571,676,653,379,215,319,259,108,700,16,613,33,174,520,718,711,354,599,435,279,373,21,556,35,694,675,483,118,701,366,159,270,521,522,574,603,475,233,109,613,114,636,358,39,537,367,532,131}

    Returns: 113

  43. {453,496,735,65,435,580,407,74,605,927,105,343,145,613,932,708,14,210,347,490,937,784,124,146,268,909,33,422,394,83,994,729,564,94,89,873,952,937,765,244,44,674,111,496,223,161,720,482,649,716}

    {706,970,13,453,695,382,341,5,690,328,913,282,683,627,138,161,311,709,721,313,248,792,449,238,754,626,449,633,192,862,547,78,461,216,808,365,315,804,457,146,920,32,311,453,356,741,820,466,604,674}

    Returns: 77

  44. {1, 500, 1000}

    {1000, 500, 1}

    Returns: 998

  45. {702,489,32,868,746,894,485,716,445,377,8,546,2,349,59,927,639,414,288,559,582,710,410,334,878,505,483,552,283,418,817,300,768,839,286,704,20,115,832,355,958,275,343,223,928,523,550,678,800,657}

    {891,709,706,930,663,535,692,945,598,640,556,161,1,948,178,766,148,735,870,476,822,58,249,523,507,781,744,653,244,702,444,834,391,728,357,839,116,200,872,762,103,548,998,121,496,885,399,667,551,38}

    Returns: 1

  46. {3,4,5}

    {5,4,3}

    Returns: 6

  47. {958,375,195,686,483,629,377}

    {104,505,882,357,759,400,869}

    Returns: 878

  48. {958, 375, 195, 686, 483, 629, 377 }

    {104, 505, 882, 357, 759, 400, 869 }

    Returns: 878

  49. {3, 4, 5 }

    {5, 4, 3 }

    Returns: 6

  50. {600 }

    {700 }

    Returns: 1298

  51. {500 }

    {800 }

    Returns: 1298

  52. {1000, 999 }

    {1000, 999 }

    Returns: 1996

  53. {1000 }

    {1000 }

    Returns: 1998

  54. {4, 6, 8 }

    {1, 2, 1 }

    Returns: 3

  55. {600, 700, 800, 900, 1000 }

    {1, 2, 3, 4, 5 }

    Returns: 599

  56. {900 }

    {900 }

    Returns: 1798

  57. {2, 5 }

    {1, 4 }

    Returns: 1

  58. {30 }

    {35 }

    Returns: 63

  59. {5 }

    {5 }

    Returns: 8

  60. {3, 1, 5 }

    {6, 100, 2 }

    Returns: 5

  61. {3, 2 }

    {1, 1 }

    Returns: 1

  62. {2, 3 }

    {2, 2 }

    Returns: 2

  63. {1000, 900 }

    {1000, 800 }

    Returns: 1698

  64. {1, 4 }

    {7, 5 }

    Returns: 6

  65. {2 }

    {3 }

    Returns: 3

  66. {999 }

    {999 }

    Returns: 1996

  67. {104, 2 }

    {104, 2 }

    Returns: 2

  68. {4, 1 }

    {5, 6 }

    Returns: 5

  69. {2, 3 }

    {2, 3 }

    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: