Problem Statement
You are the proud owner of a window washing company. Your workers tirelessly clean the outside of tall buildings. Of course, not all of your workers are equal. Some are faster than others. So your job is to place them at the best locations so that the job gets done the fastest. All the workers work in the same pattern. They start at the top of the first column of windows they are to wash. Using lifts, they wash the highest window, then the second highest, and so forth until all the windows in a column are washed. When they reach the lowest window, they use the lift controls to move to the column to the right. In this column, they work their way up the building until they reach the top. Using this zig-zag pattern, they wash all the windows they can until they get either to a column of windows that is being washed, or has been washed by another worker, or to the edge of the building. Because the lifts are on the same railing, they cannot cross over each other, or be in the same column at the same time. Not all of your workers need to be used on a job, and not all of them need to be working the entire time.
You will be given three arguments. width is the number of window columns the side of a building has, height is the number of rows of windows the side of a building has, and washTimes is a
Given this information, return the least amount of time in which your crew can wash that side of the buliding.
Definition
- Class:
- WindowWasher
- Method:
- fastest
- Parameters:
- int, int, int[]
- Returns:
- int
- Method signature:
- int fastest(int width, int height, int[] washTimes)
- (be sure your method is public)
Constraints
- width is between 1 and 1000, inclusive.
- height is between 1 and 1000, inclusive.
- washTimes has between 1 and 50 elements, inclusive.
- Each element of washTimes is between 1 and 1000, inclusive.
Examples
10
10
{60}
Returns: 6000
The sole proprieter case. You can wash each window in 60 seconds, and there are 100 windows, which takes you 6000 seconds, or 100 minutes.
10
10
{60, 60}
Returns: 3000
With a partner that works as fast as you can, the windows are washed in half the time.
10
10
{60, 30}
Returns: 2100
After sending your partner to a window washers' conference, he has learned a new technique to cut the washing time in half. If you wash 3 columns, that lets your partner wash 7 columns, and you can get the job done in 35 minutes. Note that if the lifts allowed you to work on the same column, you could both work on the last column at the same time and get done quicker, but this is not allowed.
1000
1000
{1000}
Returns: 1000000000
I would recommend that this guy get out of the window washing business.
421
936
{111,56,931,22,445,90,14,222}
Returns: 2450448
25
25
{1,625}
Returns: 625
In this case, it is better not to use the second worker, as the first can get the job done in the same time it takes the second to wash one window!
526
239
{75, 773, 812, 535, 985}
Returns: 6739800
703
648
{510, 992, 957, 825, 276, 480, 871, 874, 476, 585, 589, 958, 917, 500, 433, 386, 652, 521, 669, 416, 465, 431, 627, 221, 346, 695, 580, 261, 177, 688, 212, 581}
Returns: 6755400
454
801
{705, 446, 393, 176, 403, 733, 950, 181, 755}
Returns: 15507360
529
427
{579, 75, 730, 299, 582, 296, 229, 382, 870, 730, 493, 341, 769, 114, 280, 568, 497, 173}
Returns: 3682875
815
937
{842, 58, 822, 825, 294, 167, 986, 590, 184, 673, 716, 311, 669, 665, 311, 229, 687, 267, 566, 378, 291, 790, 26}
Returns: 7173672
724
5
{842, 405, 598, 845, 813, 85, 146, 887, 612, 818, 760, 204, 350, 982, 273, 737, 889, 562, 572, 390}
Returns: 69615
779
359
{117, 88, 29, 264, 463, 566, 755, 528, 630, 4, 850, 570, 625, 471, 936, 926, 5, 138, 464, 295, 768, 166, 749, 758, 362, 797, 517, 889, 943, 774, 462, 702, 554, 67, 723, 622}
Returns: 495420
427
137
{953, 373, 987, 918, 838, 395, 925, 5, 69, 971, 113, 836, 807, 340, 681, 905, 776, 973}
Returns: 244545
526
885
{283, 965, 820, 893, 538, 97, 835, 226, 550, 130, 625, 913, 990, 110, 47, 527, 846, 122, 376, 112, 1, 384, 487, 191, 236}
Returns: 430995
735
408
{896, 140, 602, 120, 159, 827, 999, 397, 631}
Returns: 9783024
491
85
{181, 626, 330, 990, 634, 232, 87, 610, 172, 999, 721, 619, 28, 531, 815, 217, 778, 235, 88, 899, 50, 761, 594, 348, 293, 98, 581, 253, 964, 217, 98, 822}
Returns: 261800
867
129
{82, 40, 379, 380, 728, 360, 131, 697, 528, 944, 575}
Returns: 1861728
989
387
{943, 48, 831, 74, 267, 6, 915, 549, 860, 461, 477}
Returns: 1784070
426
446
{794, 469, 627, 317, 916, 144, 165, 288, 823, 831, 924, 408, 769, 724, 451, 177, 446, 129, 488, 376, 853, 481, 531, 223, 838, 968, 792, 649, 542, 577, 683, 32, 654, 342, 235, 704}
Returns: 1676960
820
155
{45, 293, 426, 642, 871, 100, 160, 139, 431, 142, 481, 841, 311, 917}
Returns: 1803735
12
754
{728, 734, 147, 464, 6, 703, 254}
Returns: 54288
264
729
{406, 84, 279, 49, 884, 426, 50, 452, 534, 806, 464, 541, 551, 831, 924, 330, 982, 10, 456, 954, 815, 39, 351, 950, 758, 177, 271, 369, 396, 349, 825, 248, 671, 561, 215, 128, 125, 223, 205, 246, 903, 978, 374, 832, 810, 505}
Returns: 729000
418
191
{767, 221, 436, 468, 687, 753, 618, 114, 302, 760, 135, 882, 683, 126, 652, 59, 207, 336, 875, 61, 140, 488, 727, 270, 3, 864, 488, 49, 220, 610, 221, 448, 872, 31, 748, 347, 727, 972, 582, 281, 149, 865, 898, 666}
Returns: 159103
591
642
{406, 582, 467, 714, 864, 241, 481, 57, 391, 189, 542, 452, 299, 756, 469, 691, 46, 859, 596, 807, 555, 899, 597, 301, 449, 520, 839, 242, 279, 677, 724, 639, 326, 84, 146, 815, 612, 942, 393}
Returns: 2964114
173
822
{873, 710, 486, 782, 609, 738, 891, 248, 912, 129, 321, 399, 280}
Returns: 4559634
112
625
{364, 317, 130, 144, 336, 149, 826, 243, 208, 434, 714, 687, 423, 55, 821, 645, 655, 143, 310, 195, 109, 436, 654, 536, 885, 788, 569}
Returns: 756250
823
941
{826, 21, 174, 692, 933, 412, 336, 510, 247, 665, 539, 486, 409, 234, 413, 761, 542, 836, 808, 419, 113, 767, 955, 872, 883, 114, 501, 791, 910, 807, 573, 494, 724, 184, 346, 184, 227, 821, 587, 904, 332, 486, 341}
Returns: 5134096
423
978
{561, 346}
Returns: 88657656
243
538
{43, 283, 560, 721, 975, 349, 28, 567, 643, 721, 896, 699, 750, 164, 7, 690, 619, 502, 159, 82, 872, 45, 715, 205, 604}
Returns: 484200
501
467
{999, 380, 166, 574, 667, 774, 32, 704, 692, 878, 699, 418, 359, 360, 224, 989, 387, 82, 146, 92, 729, 819, 800, 135, 876, 246, 94, 91}
Returns: 1783006
275
738
{556, 918, 207, 282}
Returns: 18106092
878
182
{829, 656, 434, 185, 533, 393, 660, 898}
Returns: 9162608
94
877
{829, 316, 923, 955}
Returns: 12951536
629
658
{397, 545, 697, 783, 981, 106, 484, 759, 543, 902, 710, 535, 429, 77, 18, 697}
Returns: 4204620
962
615
{985, 914, 124, 781, 416, 534, 624, 671, 609, 329, 458, 719, 336, 615, 212, 1000, 648, 773, 296, 255, 111, 561, 32, 694, 779, 214, 849, 186, 703, 611, 256, 722, 702, 995, 500, 338, 764, 672, 559, 301}
Returns: 4753950
412
212
{512, 615, 181, 289, 235, 850, 200, 81, 57, 725, 784, 390, 950, 675, 232, 372, 369, 805, 884, 799, 317, 226, 847, 453, 944, 999, 667, 285, 393, 391, 419, 920, 699, 177, 924, 903, 475, 657, 589, 276, 916, 224, 905, 535, 197, 455, 887}
Returns: 676704
258
462
{980, 297, 276, 775, 259, 42, 803, 335, 322, 283, 201, 578, 447, 258, 24, 315, 175, 819, 209, 158, 260, 129, 206, 604, 199, 599, 470, 16, 462, 575, 449, 710, 379, 26, 333, 474, 177, 45}
Returns: 434280
618
545
{544, 436, 990, 519, 54, 635}
Returns: 12448890
623
671
{515, 425, 636, 264, 632, 49, 223, 514, 649, 376, 553, 100, 488, 529, 160, 710, 857, 294, 13, 636, 198, 751, 387, 674, 353, 49, 239, 796}
Returns: 2268651
586
167
{154, 502, 951, 827, 402, 186, 39, 644, 533, 653, 389, 845, 170, 217, 444, 496, 534, 833, 969, 323, 628, 749, 711, 500, 679}
Returns: 1208412
24
373
{583, 179, 8, 709, 820, 8, 832, 786, 456, 628, 411, 15, 707, 880, 830, 721, 767, 980, 789, 182, 789, 395, 193, 96, 496, 568, 797, 922, 22, 980, 361, 920, 822, 464, 368, 800, 730, 251, 58, 239, 198, 164, 912, 871, 596, 360, 287, 180}
Returns: 24618
294
224
{527, 874}
Returns: 21720832
505
283
{937, 379, 867, 916, 710, 476, 93, 228, 745, 903, 130, 484, 833, 565, 228, 331, 894, 280, 881, 694, 561, 727, 324, 439, 382, 49, 782, 447, 654, 17, 375, 238, 704, 394, 284, 923, 793, 341, 368, 400}
Returns: 845887
655
651
{779, 178, 238, 204, 157, 931, 440, 397, 27, 425, 655, 809, 322, 603, 338, 53, 964, 71, 181, 309, 658, 565, 537, 127, 250, 326}
Returns: 3080532
122
260
{953, 872, 318, 412, 817}
Returns: 3611140
580
36
{983}
Returns: 20525040
230
465
{461, 113, 611, 348, 120, 790, 443, 855, 415, 500}
Returns: 3295920
501
685
{182, 501, 74, 688, 321, 587, 894, 347, 750, 1, 190, 327, 700, 53, 408, 150, 52, 356, 409, 23, 975, 81, 981, 505, 675, 897, 42, 89, 942, 618, 636, 610, 768, 576}
Returns: 295235
977
677
{314, 923, 826, 925, 459, 344, 716, 60, 408, 590, 104, 112, 973, 521, 157, 652, 711, 835, 713, 683, 524, 276, 570, 18, 437, 972, 372, 101, 872}
Returns: 4508820
412
298
{485, 672, 516, 549, 426, 859, 991, 769, 477, 252, 560, 593, 717, 657, 946, 819, 65, 255, 257, 148, 720, 620, 270, 994, 100, 420}
Returns: 1627080
464
220
{609, 882, 866, 608, 268, 646, 488, 189, 401, 689, 582, 428}
Returns: 3950320
794
579
{420}
Returns: 193084920
783
771
{979, 586, 257, 888, 853, 179, 804, 437, 477, 497, 815, 790, 928, 904, 811, 455, 274, 61, 179, 86, 380, 679, 512, 193, 925, 277, 825, 445, 304, 991, 475, 411, 938, 19, 824, 365, 895, 602, 765, 79, 562, 574, 656, 173, 888, 228, 534, 289, 493, 994}
Returns: 3174207
915
624
{858, 913, 460, 842, 926, 555, 342, 220, 292, 190, 38}
Returns: 11263200
901
71
{845, 474, 546, 897, 406, 996, 93, 915, 423, 861, 778, 3, 912, 327, 452, 627, 391, 909, 133, 679, 756, 596, 750, 130, 963, 978, 554, 137, 639, 6, 86, 494, 603, 129, 991, 79, 441, 286, 405, 105, 996, 187, 96, 991, 644, 169, 312, 231, 749}
Returns: 99258
12
754
{ 728, 734, 147, 464, 6, 703, 254 }
Returns: 54288
22
22
{ 728, 34, 147, 464, 66, 703, 254 }
Returns: 9702
421
936
{ 111, 56, 931, 22, 445, 90, 14, 222 }
Returns: 2450448
332
323
{ 728, 34, 147, 464, 66, 703, 254 }
Returns: 1801048
10
10
{ 1, 1000 }
Returns: 100
2
754
{ 728, 734, 147, 464, 6, 703, 254 }
Returns: 9048
12
754
{ 728, 734, 147, 464, 6, 703, 254 }
Returns: 54288
22
22
{ 728, 34, 147, 464, 66, 703, 254 }
Returns: 9702
421
936
{ 111, 56, 931, 22, 445, 90, 14, 222 }
Returns: 2450448
332
323
{ 728, 34, 147, 464, 66, 703, 254 }
Returns: 1801048
10
10
{ 1, 1000 }
Returns: 100
2
754
{ 728, 734, 147, 464, 6, 703, 254 }
Returns: 9048