TheCoffeeTimeDivTwo
SRM 479 · 2009-11-12 · by Vasyl[alphacom]
SRM 479 · 2009-11-12 · by Vasyl[alphacom] · Simulation
Problem Statement
Problem Statement
John and Brus are flying on an airplane and now it's coffee time.
There are n seats in the plane numbered from 1 to n, one seat in each row. All seats are occupied, thus there are n passengers overall (including John and Brus). A stewardess will serve a cup of coffee or tea to each passenger. She needs to serve tea to all passengers whose seat numbers are listed inint[] tea, and she needs to serve coffee to all other passengers.
A coffee and tea machine is located just before the first seat of the plane. The stewardess has a flask that can contain enough coffee or tea to serve at most 7 passengers. Initially, the stewardess is located near the coffee and tea machine and the flask is empty.
The stewardess can perform the following kinds of actions:
Givenint n and int[] tea, return the minimal time needed for the stewardess to serve all passengers with proper drinks and return to the coffee and tea machine.
There are n seats in the plane numbered from 1 to n, one seat in each row. All seats are occupied, thus there are n passengers overall (including John and Brus). A stewardess will serve a cup of coffee or tea to each passenger. She needs to serve tea to all passengers whose seat numbers are listed in
A coffee and tea machine is located just before the first seat of the plane. The stewardess has a flask that can contain enough coffee or tea to serve at most 7 passengers. Initially, the stewardess is located near the coffee and tea machine and the flask is empty.
The stewardess can perform the following kinds of actions:
- Move from the coffee and tea machine to seat 1 or move from seat 1 to the coffee and tea machine. Each of these two actions takes 1 second.
- Move from seat i, i > 1, to seat i-1. It takes 1 second.
- Move from seat i, i < n, to seat i+1. It takes 1 second.
- If she is near seat i, the passenger at this seat has not yet been served and the current type of drink in the flask is the same as the drink this passenger wants, she can serve this passenger with a cup of drink he/she wants. It takes 4 seconds.
- If she is near the coffee and tea machine and the flask is empty, she can fill the flask with either tea or coffee (but not both simultaneously). It takes 47 seconds. Note that she can fill the flask partially (to serve less than 7 passengers), but it still takes 47 seconds.
Given
Constraints
- n will be between 2 and 1000, inclusive.
- tea will contain between 1 and 47 elements, inclusive.
- Each element of tea will be between 1 and n, inclusive.
- All elements of tea will be distinct.
Examples
0)
2
{1}
Returns: 108
The stewardess will serve coffee in 47+2+4+2=55 seconds and tea in 47+1+4+1=53 seconds.
1)
2
{2, 1}
Returns: 59
Here she only needs to serve tea.
2)
15
{1, 2, 3, 4, 5, 6, 7}
Returns: 261
The stewardess will fill the flask three times overall: once with tea and two times with coffee.
3)
47
{1, 10, 6, 2, 4}
Returns: 891
4)
9
{3, 1}
Returns: 154
Submissions are judged against all 78 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheCoffeeTimeDivTwo with a public method int find(int n, vector<int> tea) · 78 test cases · 2 s / 256 MB per case