Connection Status:
Competition Arena > Embassy

Embassy

SRM 414 · 2008-08-16 · by StevieT

SRM 414 · 2008-08-16 · by StevieT · Brute Force, Search, Simulation
Class Name: Embassy
Return Type: int
Method Name: visaApplication
Arg Types: (vector<int>, int, int)
Problem Statement

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.

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.

4)
{567213,494175,41987,510822,279719,889559,572483,117704,641618,110895,259588,721431,930617,438350,184363,37908,784347,842509,563146,965103,966945,204978,136741,308997,814758,672822,774768,279015,303415,142975,980557,678292,354894,539685,246801,649725,110680,480112,286912,941249,157936,208727,608459,283950,983841,505666,684633,863492,84134,478601}
389114
349228
Returns: 24712086

Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Embassy with a public method int visaApplication(vector<int> forms, int dayLength, int openTime) · 136 test cases · 2 s / 256 MB per case

Submitting as anonymous