WindowWasher
SRM 168 · 2003-10-21 · by schveiguy
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.
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.
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!
Submissions are judged against all 68 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class WindowWasher with a public method int fastest(int width, int height, vector<int> washTimes) · 68 test cases · 2 s / 256 MB per case