Statistics

Problem Statement for "WallClimbing"

Problem Statement

A robot needs to climb a flat vertical wall with several handholds on it.

The robot has four mechanial "hands". Each hand can grab a handhold positioned anywhere within or on the boundary of a circle of radius armLength from robot's center. While the robot is climbing the wall, three of the hands have to remain anchored at three distinct handholds at all times. To move between holding positions, the robot can use the fourth hand to grab next handhold and release one of the previous handholds. At the start of the climb the robot can stand on one of its hands anywhere on the ground. Thus, it can grab any single handhold which is not higher than 2*armLength from the ground, and to start climbing it must grab three handholds while still standing on the fourth hand.

The wall is described as a plane with a cartesian coordinate system on it. The ground is the line y = 0. Handhold i is positioned at the point (holdx[i], holdy[i]).

Return the y-coordinate of the highest point the robot can reach with a hand while standing on the ground or hanging on the wall using the other three hands.

Definition

Class:
WallClimbing
Method:
maxHeight
Parameters:
int[], int[], int
Returns:
double
Method signature:
double maxHeight(int[] holdx, int[] holdy, int armLength)
(be sure your method is public)

Notes

  • The robot can't grab one handhold with two or more hands.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • holdx will contain between 1 and 16 elements, inclusive.
  • holdy will contain the same number of elements as holdx.
  • Each element of holdx and holdy will be between 1 and 1000, inclusive.
  • The location of each handhold will be distinct.
  • handLength will be between 1 and 100, inclusive.

Examples

  1. {10, 10, 10}

    {20, 40, 60}

    30

    Returns: 80.0

    The three handholds are arranged in a vertical line, and it is possible to hang on them and reach 80.0.

  2. {20, 40, 60, 80}

    {20, 20, 20, 20}

    20

    Returns: 40.0

    The four handholds are arranged in a horizontal line. It is possible to hang on any three successive handholds, but this doesn't let the robot reach higher than from the ground.

  3. {10, 10, 10, 10, 10, 10, 10, 10, 10}

    {20, 40, 60, 80, 100, 120, 140, 160, 180}

    30

    Returns: 200.0

    Each triple of successive handholds is a valid holding position, and it is possible to get to the triple {6,7,8} and reach a height of 200.

  4. {10, 10}

    {10, 20}

    40

    Returns: 80.0

    There are not enough handholds to hang on them.

  5. { 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200}

    { 50, 50, 50, 50, 100, 100, 100, 100, 150, 150, 150, 150, 200, 200, 200, 200}

    25

    Returns: 50.0

    Here no three handholds are close enough together for the robot to hang from them.

  6. { 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200, 50, 100, 150, 200}

    { 50, 50, 50, 50, 100, 100, 100, 100, 150, 150, 150, 150, 200, 200, 200, 200}

    50

    Returns: 250.0

    The robot can move to the highest row and hang on a horizontal triple.

  7. {545, 153, 463, 795, 32, 425, 498, 7, 777, 639, 170, 45, 732, 141}

    {693, 152, 783, 525, 137, 729, 770, 146, 768, 954, 99, 901, 696, 137}

    81

    Returns: 277.92286708761526

    Tests #6-#45 are randomly generated and chosen so that each time the robot can climb (at least 3.9*handLength before finding the bug, worse after, #10, #18, #30 and #42 - no climbing).

  8. {845, 270, 205, 905, 265, 901, 212, 403, 334, 652, 386, 916, 843}

    {403, 59, 231, 383, 413, 631, 595, 451, 85, 217, 133, 484, 517}

    90

    Returns: 234.91942002527782

  9. {776, 939, 187, 409, 418, 116, 406, 371, 608, 407, 209, 963, 342, 77, 413, 308}

    {157, 866, 846, 344, 299, 664, 549, 253, 150, 122, 804, 739, 11, 285, 342, 76}

    74

    Returns: 158.99431309418705

  10. {3, 594, 573, 585, 644, 926, 274, 908, 924, 499, 358, 537}

    {617, 172, 358, 187, 282, 486, 254, 458, 290, 63, 278, 740}

    97

    Returns: 257.0

  11. {333, 248, 717, 938, 356, 281, 736, 555, 693, 612, 670, 891, 983, 708, 808}

    {368, 460, 943, 142, 641, 598, 774, 254, 632, 905, 927, 98, 448, 503, 9}

    96

    Returns: 192.0

  12. {621, 928, 734, 675, 143, 709, 525, 786, 349, 777, 316, 324, 940, 308, 577, 702}

    {549, 966, 183, 595, 1, 573, 916, 699, 987, 58, 97, 6, 411, 70, 692, 448}

    84

    Returns: 174.0

  13. {302, 177, 770, 100, 120, 76, 130, 555, 133, 514, 370, 806, 139, 565}

    {40, 183, 761, 320, 106, 55, 232, 809, 126, 781, 238, 430, 614, 804}

    64

    Returns: 183.0

  14. {305, 953, 333, 85, 356, 821, 137, 515, 236, 967, 93, 741, 932, 350, 406}

    {700, 149, 730, 986, 564, 95, 940, 699, 940, 334, 896, 457, 16, 298, 714}

    85

    Returns: 181.91892881334365

  15. {984, 8, 818, 123, 275, 385, 787, 95, 976, 49, 328, 354, 250, 104, 312}

    {952, 457, 953, 533, 134, 54, 285, 722, 614, 415, 89, 570, 821, 394, 498}

    88

    Returns: 227.16629932366158

  16. {214, 403, 380, 686, 796, 268, 868, 849, 366, 691, 57, 198, 342, 713, 595, 67}

    {877, 286, 733, 121, 176, 632, 723, 987, 699, 228, 810, 970, 604, 158, 459, 650}

    99

    Returns: 353.3985119783001

  17. {187, 647, 981, 796, 234, 170, 488, 881, 799, 833, 309, 727, 54, 972, 488, 808}

    {577, 538, 298, 113, 9, 481, 172, 88, 932, 414, 720, 53, 893, 283, 913, 335}

    99

    Returns: 227.7289870359923

  18. {285, 732, 498, 803, 363, 262, 659, 398, 702, 703, 314, 362, 163, 406, 753, 626}

    {146, 39, 873, 653, 960, 569, 4, 499, 151, 932, 361, 885, 629, 884, 131, 284}

    92

    Returns: 223.0

  19. {459, 445, 422, 939, 561, 916, 161, 449, 754, 161, 666, 452, 618, 112, 50, 519}

    {436, 24, 352, 596, 408, 758, 657, 807, 915, 137, 770, 62, 8, 923, 279, 307}

    95

    Returns: 190.0

  20. {512, 418, 111, 965, 920, 611, 832, 502, 431, 877, 565}

    {256, 425, 518, 115, 60, 901, 63, 379, 258, 506, 713}

    97

    Returns: 244.8833181080845

  21. {163, 701, 583, 478, 932, 149, 132, 98, 145, 333, 838, 20, 271, 228, 510}

    {732, 542, 659, 135, 238, 153, 735, 327, 860, 161, 518, 347, 803, 534, 85}

    100

    Returns: 247.72016338060234

  22. {648, 412, 222, 345, 90, 397, 589, 566, 410, 523, 683, 16, 257, 307, 525}

    {735, 998, 231, 39, 430, 524, 694, 815, 632, 142, 219, 389, 36, 58, 701}

    93

    Returns: 212.37160610673163

  23. {944, 587, 336, 692, 381, 747, 514, 77, 611, 23, 378, 633, 549, 321, 167}

    {753, 421, 687, 434, 281, 405, 100, 435, 177, 653, 456, 361, 48, 656, 191}

    93

    Returns: 234.0

  24. {43, 173, 114, 436, 508, 798, 592, 182, 498, 142, 48, 465, 207, 695, 562, 536}

    {422, 479, 573, 86, 376, 833, 727, 173, 573, 156, 425, 625, 40, 877, 737, 700}

    93

    Returns: 226.0

  25. {418, 791, 878, 245, 894, 825, 794, 419, 383, 582, 216, 839, 583, 877}

    {739, 422, 76, 393, 32, 434, 425, 321, 21, 623, 31, 274, 201, 88}

    100

    Returns: 232.0

  26. {731, 554, 340, 302, 932, 685, 365, 934, 248, 758, 757, 239, 111, 378, 679, 340}

    {518, 470, 654, 502, 518, 829, 138, 841, 822, 122, 98, 885, 463, 958, 190, 935}

    96

    Returns: 290.0

  27. {422, 767, 646, 337, 736, 904, 132, 279, 721, 954, 774, 765, 833, 283, 211, 283}

    {502, 163, 334, 583, 767, 77, 551, 990, 709, 565, 71, 991, 135, 669, 644, 677}

    84

    Returns: 239.0

  28. {183, 145, 397, 988, 903, 527, 384, 444, 553, 181, 504, 401, 271, 156, 542, 516}

    {265, 313, 846, 456, 98, 171, 815, 892, 748, 31, 81, 796, 587, 661, 181, 951}

    91

    Returns: 263.0

  29. {754, 560, 438, 689, 689, 187, 885, 149, 659, 226, 656, 500, 738}

    {870, 129, 352, 722, 243, 34, 344, 5, 873, 43, 943, 795, 741}

    94

    Returns: 192.98814477485564

  30. {589, 67, 937, 250, 101, 685, 243, 161, 977, 276, 12, 591, 365, 624, 556, 433}

    {318, 940, 902, 928, 536, 565, 884, 936, 865, 222, 604, 121, 865, 739, 63, 135}

    93

    Returns: 243.57007934587148

  31. {294, 511, 613, 829, 883, 581, 652, 467, 786, 32, 373, 702, 451, 6, 654, 388}

    {234, 428, 367, 44, 891, 489, 929, 933, 52, 734, 63, 153, 371, 306, 950, 640}

    92

    Returns: 219.5099230213084

  32. {765, 229, 344, 917, 99, 787, 751, 763, 612, 761, 37, 406, 462}

    {834, 510, 624, 98, 287, 844, 869, 97, 825, 18, 22, 642, 279}

    90

    Returns: 180.0

  33. {675, 274, 26, 667, 65, 767, 485, 254, 299, 988, 284, 845, 736, 152}

    {607, 196, 74, 19, 782, 27, 753, 157, 262, 410, 138, 385, 69, 242}

    70

    Returns: 141.6707245442576

  34. {238, 851, 469, 878, 796, 824, 489, 7, 368, 957, 369, 301, 744, 313, 730, 632}

    {479, 465, 475, 814, 162, 999, 268, 171, 526, 914, 500, 537, 547, 200, 131, 96}

    100

    Returns: 272.3839740592175

  35. {809, 322, 378, 139, 695, 383, 431, 249, 133, 252, 749, 496, 725, 381}

    {305, 505, 450, 263, 627, 3, 52, 494, 527, 333, 935, 80, 701, 307}

    95

    Returns: 191.00677065145146

  36. {128, 129, 974, 275, 709, 528, 146, 271, 975, 488, 904, 215, 984, 382, 315, 706}

    {491, 587, 168, 115, 609, 985, 592, 519, 193, 405, 325, 89, 766, 956, 129, 512}

    82

    Returns: 248.41560523183512

  37. {514, 353, 716, 636, 370, 557, 10, 806, 366, 112, 319, 508, 819, 770, 533, 919}

    {267, 54, 586, 313, 131, 57, 773, 982, 439, 574, 130, 317, 494, 175, 365, 561}

    97

    Returns: 248.0

  38. {215, 276, 25, 229, 230, 635, 940, 976, 662, 983, 232, 388, 11, 203}

    {245, 101, 39, 169, 169, 813, 921, 318, 858, 433, 479, 929, 905, 984}

    85

    Returns: 338.99852939904315

  39. {527, 547, 312, 135, 848, 551, 641, 810, 496, 159, 41, 615, 7, 532, 601, 919}

    {572, 310, 483, 187, 933, 191, 121, 855, 494, 265, 468, 304, 133, 160, 843, 484}

    100

    Returns: 391.0

  40. {188, 165, 231, 311, 138, 747, 161, 236, 74, 539, 864, 590, 880, 109, 549, 830}

    {635, 48, 143, 140, 688, 203, 649, 519, 590, 990, 515, 80, 537, 681, 614, 217}

    95

    Returns: 222.62939486210144

  41. {365, 530, 405, 298, 190, 727, 293, 185, 81, 417, 960, 149, 386, 541}

    {985, 968, 889, 230, 84, 98, 87, 154, 739, 47, 936, 529, 993, 864}

    93

    Returns: 271.2009477265179

  42. {567, 704, 549, 859, 896, 660, 807, 835, 746, 971, 542, 795, 103, 752, 707, 687}

    {692, 398, 77, 214, 814, 961, 11, 82, 150, 436, 628, 994, 984, 55, 677, 599}

    90

    Returns: 233.35068667255564

  43. {544, 638, 812, 546, 429, 782, 381, 803, 465, 224, 120, 597, 729, 390, 734, 270}

    {627, 722, 102, 813, 678, 948, 919, 310, 685, 50, 631, 346, 398, 48, 572, 5}

    96

    Returns: 192.0

  44. {144, 719, 694, 652, 221, 215, 135, 647, 742, 242, 144}

    {396, 821, 142, 160, 346, 346, 356, 969, 111, 770, 786}

    99

    Returns: 308.8979262054661

  45. {452, 667, 678, 592, 515, 471, 434, 520, 706, 254, 411, 378, 345, 400, 358}

    {827, 928, 20, 252, 265, 140, 244, 893, 497, 738, 504, 481, 57, 132, 969}

    89

    Returns: 226.9334526597255

  46. {816, 876, 185, 3, 150, 755, 206, 405, 801, 198, 482, 50, 563, 77, 109}

    {944, 100, 984, 192, 12, 659, 38, 529, 292, 109, 58, 959, 358, 865, 951}

    92

    Returns: 196.0

  47. {100,145,173,244,260,260,260,260,260,260,93,93,93}

    {100,130,196,142,150,151,152,298,299,300,120,121,122}

    75

    Returns: 270.83313533261025

  48. {100,100,171,157,99,98,97}

    {100,244,184,204,100,100,100}

    72

    Returns: 243.99999965556202

  49. { 55, 55, 60, 60, 25, 25, 20, 20, 47, 47, 33, 33, 64, 64, 16, 16 }

    { 60, 20, 55, 25, 60, 20, 55, 25, 64, 16, 64, 16, 47, 33, 47, 33 }

    100

    Returns: 260.0

    Combinatioral time out worst case test, probably not an issue.

  50. {613, 295, 216, 634, 857, 796, 817, 618, 688, 703, 688, 391, 821, 584, 911, 943}

    {407, 139, 428, 140, 501, 120, 806, 138, 282, 237, 255, 382, 773, 116, 2, 519}

    89

    Returns: 415.0

    #49-#56 are more random climbing, generated with updated solution

  51. {662, 694, 599, 577, 698, 850, 589, 761, 855, 857, 349, 871, 555, 963, 498}

    {617, 106, 184, 173, 389, 127, 207, 399, 705, 104, 993, 665, 270, 117, 227}

    100

    Returns: 403.42322368294344

  52. {661, 447, 880, 693, 880, 303, 991, 565, 873, 876, 865, 575, 154, 883, 817, 684}

    {226, 823, 111, 758, 110, 702, 138, 420, 535, 234, 257, 893, 821, 503, 243, 148}

    93

    Returns: 418.575090861993

  53. {738, 337, 749, 224, 288, 499, 520, 299, 322, 677, 545, 585, 460, 738, 180, 386}

    {931, 139, 496, 151, 32, 9, 688, 197, 298, 175, 997, 712, 797, 120, 231, 575}

    92

    Returns: 371.4595871295397

  54. {333, 669, 112, 558, 710, 958, 811, 55, 794, 770, 234, 758, 818}

    {455, 240, 790, 50, 207, 712, 53, 667, 240, 35, 382, 147, 469}

    99

    Returns: 404.5157914992508

  55. {678, 376, 413, 423, 449, 948, 204, 465, 90, 689, 922, 372, 182, 146, 466, 867}

    {578, 151, 634, 74, 128, 291, 517, 145, 178, 221, 814, 155, 232, 167, 187, 641}

    73

    Returns: 292.6849634234984

  56. {137, 33, 353, 625, 82, 90, 2, 989, 901, 52, 40, 905, 639, 650, 102, 822}

    {83, 653, 773, 708, 107, 219, 514, 405, 643, 160, 87, 900, 947, 64, 216, 496}

    69

    Returns: 298.0

  57. {290, 656, 18, 445, 712, 559, 520, 512, 464, 779, 656, 726, 790, 224}

    {360, 86, 842, 201, 45, 273, 46, 28, 435, 294, 148, 224, 210, 750}

    97

    Returns: 403.19263005591165

  58. {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}

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

    1

    Returns: 9.0

    Minimal armLength with climbing.

  59. {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2}

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

    1

    Returns: 2.0

    Minimal armLength without climbing.

  60. {100, 200, 100, 200, 100, 200, 100, 200, 100, 200, 100, 200, 100, 200, 100, 200}

    {100, 100, 200, 200, 300, 300, 400, 400, 500, 500, 600, 600, 700, 700, 800, 800}

    100

    Returns: 900.0

    Maximal armLength and climbing high.

  61. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {10, 76, 142, 208, 274, 340, 406, 472, 538, 604, 670, 736, 802, 868, 934, 1000}

    99

    Returns: 1066.0

  62. {10, 30, 10, 30, 10, 30, 10, 30, 10, 30, 10, 30, 10, 30, 10, 30}

    {66, 132, 198, 264, 330, 396, 462, 528, 594, 660, 726, 792, 858, 924, 990, 1000}

    100

    Returns: 1124.0

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

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

    100

    Returns: 200.99499987499377

  64. {149,174,84,28,84}

    {134,81,10,81,157}

    73

    Returns: 153.99295731584547

  65. {101,142,77,96,77,96}

    {117,19,9,116,130,10}

    57

    Returns: 132.71700791583754

  66. {180,103,20,59,103}

    {134,9,57,175,198}

    89

    Returns: 190.1091975777134

  67. {101,101,12,29}

    {196,4,64,163}

    96

    Returns: 195.9999998356098

  68. {10,20,12,19,15,19,17,18,16}

    {15,15,19,18,10,10,5,5,10}

    5

    Returns: 24.0

  69. {100,105,113,87,88,100}

    {1,2,14,14,19,27}

    13

    Returns: 40.0

  70. {100,105,113,87,88,100}

    {1,2,14,14,19,27}

    12

    Returns: 24.954356057317852

  71. {134, 137, 28, 166, 44, 86, 137, 243, 150, 172, 113, 28, 191, 60, 14, 600 }

    {177, 41, 177, 173, 237, 212, 119, 68, 180, 33, 31, 113, 124, 68, 136, 600 }

    98

    Returns: 374.6235141933719

  72. {15, 2, 13, 5, 7, 18, 6, 3, 12, 9, 11, 1, 12, 9, 13, 8 }

    {7, 12, 2, 10, 3, 11, 9, 1, 15, 17, 3, 12, 1, 6, 10, 9 }

    3

    Returns: 8.23606797749979

  73. {143, 2, 3, 412, 5, 6, 7, 8, 9, 102, 11, 12, 133, 14, 159, 1000 }

    {443, 5, 6, 143, 2, 3, 789, 8, 9, 100, 11, 12, 139, 14, 150, 999 }

    97

    Returns: 294.0

  74. {146, 345, 797, 134, 555, 23, 765, 987, 345, 234, 150, 78, 120, 140, 188, 233 }

    {234, 146, 333, 222, 111, 88, 96, 145, 235, 322, 255, 177, 99, 88, 176, 254 }

    100

    Returns: 445.4741645808863

  75. {10, 10, 10 }

    {20, 40, 60 }

    30

    Returns: 80.0

  76. {1, 4, 77, 12, 66, 77, 88, 55, 33, 22, 33, 90, 23, 25, 20, 100 }

    {11, 14, 72, 19, 62, 73, 84, 5, 38, 2, 3, 95, 2, 22, 30, 10 }

    20

    Returns: 62.0

  77. {16, 50, 60, 212, 241, 123, 70, 20, 16, 50, 60, 212, 241, 123, 70, 20 }

    {11, 60, 29, 90, 124, 51, 6, 293, 31, 900, 112, 31, 59, 125, 295, 100 }

    60

    Returns: 199.83980889538503

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: