LongSeat
2015 TCO Parallel 2C · 2015-04-08 · by rng_58
2015 TCO Parallel 2C · 2015-04-08 · by rng_58 · Brute Force
Problem Statement
Problem Statement
In this problem we are using half-open intervals.
The half-open interval from x (inclusive) to y (exclusive) is denoted [x,y).
Formally, [x,y) is the set of all real numbers z such that x <= z < y.
When cat Snuke last traveled by train, he noticed that there was a long seat. Whenever a passenger boarded the train, if there was enough room for the passenger somewhere on the seat, the passenger sat down somewhere. Otherwise, the passenger had to stand.
Formally, the seat can be represented as the half-open interval [0,L). A person of width w sitting at coordinate x covers the interval [x,x+w). People may sometimes sit on non-integer coordinates. For each sitting passenger the interval covered by the passenger must be a subset of the seat. The intervals covered by different sitting passengers must be disjoint.
You are given theint L and a int[] width.
L is the length of the seat.
The seat is currently empty.
Elements of width are the widths of passengers in the order in which they will board the train.
You are guaranteed that each person who is able to sit down will sit down somewhere.
However, note that sometimes there can be multiple (even infinitely many) places where a person can sit.
In that case, the person may choose any of those places, and you have no information about which place they will choose.
Return aString[] that contains the same number of elements as width.
For each valid i, element i of your return value should be:
When cat Snuke last traveled by train, he noticed that there was a long seat. Whenever a passenger boarded the train, if there was enough room for the passenger somewhere on the seat, the passenger sat down somewhere. Otherwise, the passenger had to stand.
Formally, the seat can be represented as the half-open interval [0,L). A person of width w sitting at coordinate x covers the interval [x,x+w). People may sometimes sit on non-integer coordinates. For each sitting passenger the interval covered by the passenger must be a subset of the seat. The intervals covered by different sitting passengers must be disjoint.
You are given the
Return a
- "Sit" if we are sure that the i-th passenger (0-based index) will have a place to sit.
- "Stand" if we are sure that the i-th passenger will have to stand.
- "Unsure" otherwise (i.e., if it is possible but not certain that this passenger will have a place to sit).
Constraints
- L will be between 1 and 10^9, inclusive.
- width will contain between 1 and 8 elements, inclusive.
- Each element of width will be between 1 and 10^9, inclusive.
Examples
0)
2
{1, 1}
Returns: {"Sit", "Unsure" }
The first passenger will sit down for sure. We are unsure about the second passenger: for example, if the first passenger sits at 0 and fills the interval [0, 1), there is enough room for the second passenger to sit, however, if the first passenger sits at 0.5 and fills the interval [0.5, 1.5), the second passenger has to stand.
1)
10
{100, 2, 4, 2}
Returns: {"Stand", "Sit", "Sit", "Unsure" }
2)
37
{3, 7, 5, 6, 4, 4, 1, 3}
Returns: {"Sit", "Sit", "Sit", "Unsure", "Unsure", "Unsure", "Sit", "Unsure" }
3)
400
{92, 65, 99, 46, 24, 85, 95, 84}
Returns: {"Sit", "Sit", "Unsure", "Unsure", "Unsure", "Unsure", "Stand", "Unsure" }
4)
1000000000
{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000}
Returns: {"Sit", "Stand", "Stand", "Stand", "Stand", "Stand", "Stand", "Stand" }
Submissions are judged against all 260 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LongSeat with a public method vector<string> canSit(int L, vector<int> width) · 260 test cases · 2 s / 256 MB per case