Connection Status:
Competition Arena > BusSeating

BusSeating

SRM 319 · 2006-09-18 · by NeverMore

SRM 319 · 2006-09-18 · by NeverMore · Brute Force, Geometry, Simple Math
Class Name: BusSeating
Return Type: double
Method Name: getArrangement
Arg Types: (string, string)
Problem Statement

Problem Statement

Three friends enter a bus. There are two rows of seats with 10 seats in each row along the left and right side of the bus. For this problem, consider the seats to be points. Each seat in the same row is separated from the one in front of it and the one behind it by exactly 1 meter, and from the one directly opposite it (i.e., in the other row) by exactly 2 meters. Some of the seats are occupied by passengers. The friends want to know which seats they should occupy so as to minimize the sum of the Euclidean distances between each pair of friends. Recall that the Euclidean distance is simply the length of the line segment joining two points.

Create a class BusSeating that contains a method getArrangement. The method takes two Strings as arguments, leftRow and rightRow. Each string is composed of the characters '-' and 'X' only, with '-' denoting an empty seat, and 'X' denoting an occupied seat. The seats are given in order from the front to the back of the bus in each row. The method should return a double corresponding to the sum of the Euclidean distances between friends in the optimal arrangment.

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • leftRow and rightRow will each contain exactly 10 characters.
  • leftRow and rightRow will contain only the characters '-' and uppercase 'X'.
  • There will be at least 3 empty seats among the 2 rows of seats.
Examples
0)
"----------"
"----------"
Returns: 4.0

The minimum sum of distances in this situation is achieved when the three friends sit behind each other in the same row of seats, giving a minimum distance of 4.0.

1)
"XXX-X-XX-X"
"-XXXX---XX"
Returns: 4.0

Once again, the friends can minimize the sum of distances by sitting behind each other in a row. This time, however, there is only one way to seat themselves in this manner.

2)
"----------"
"-XXXX---XX"
Returns: 4.0
3)
"-X-X-X-X-X"
"X-X-X-X-X-"
Returns: 6.47213595499958
4)
"XXXXXXXXXX"
"-XX-XX-X--"
Returns: 6.0

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

Coding Area

Language: C++17 · define a public class BusSeating with a public method double getArrangement(string leftRow, string rightRow) · 84 test cases · 2 s / 256 MB per case

Submitting as anonymous