PROBLEM STATEMENT
You've just qualified for the on-site round of a major coding tournament! You now need to sort out
a visa to allow you to travel to the event. You know that this is likely to be a long process, but
are determined to sort it out as quickly as possible, even if it means working day and night. The
process involves filling out a series of forms, which then have to be approved by the embassy.
When the last form is approved your visa is granted. The approval process is very quick
(instantaneous for the purpose of this problem), but there is a catch: each form has to be
approved by the embassy before they will give you the next form to fill out. The embassy opens at
exactly the same time each day and remains open for openTime time units. By the non-standard
embassy clocks, a day is dayLength time units long, so the embassy then remains closed for
dayLength - openTime time units before it opens the next day. Forms can be approved at any point
in time between the time that the embassy opens and the time it closes, inclusive. However, if you
finish filling in a form when the embassy is closed, you have to wait until it opens again before
the form can be approved. The length of time it takes you to fill out form i is forms[i] units and
the forms must be completed in the order they are given in forms. You already have the first form
in your possession and can start filling it out at any time. Return the minimum length of time
between starting to fill out the first form and getting your visa granted.
DEFINITION
Class:Embassy
Method:visaApplication
Parameters:vector , int, int
Returns:int
Method signature:int visaApplication(vector forms, int dayLength, int openTime)
CONSTRAINTS
-forms will contain between 1 and 50 elements, inclusive.
-Each element of forms will be between 1 and 1,000,000 (10^6), inclusive.
-dayLength will be between 1 and 1,000,000 (10^6), inclusive.
-openTime will be between 1 and dayLength, inclusive.
EXAMPLES
0)
{4,4,4}
24
8
Returns: 12
The embassy is open for 8 hours out of a 24 hour day. Each of the three forms takes 4 hours to
fill in. If you start filling in the first form 4 hours before the embassy opens, you can get it
approved just as the embassy opens. The embassy will still be open 4 hours later to approve the
second form and the third form can be approved just as the embassy shuts. Since you never have to
wait, the total time is 12 hours.
1)
{4,4,4,4}
24
8
Returns: 28
Now there is an additional form to fill in. You can't complete the process in a single day.
2)
{2,2,2,2}
24
1
Returns: 73
The embassy is only open for one hour each day, so you can only get one form approved per day.
3)
{25,500,630,2500,1000,350,22,58,100,400,500,5000}
1440
360
Returns: 16945
Time is now measured in minutes. It's optimal to start filling in the first form 335 minutes after
the embassy first opens.
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)2010, TopCoder, Inc. All rights reserved.