Connection Status:
Competition Arena > MovieSeating

MovieSeating

SRM 483 · 2010-03-12 · by espr1t

SRM 483 · 2010-03-12 · by espr1t · Simple Math
Class Name: MovieSeating
Return Type: long
Method Name: getSeatings
Arg Types: (int, vector<string>)
Problem Statement

Problem Statement

Elly and some of her friends (possibly none) are going to the movies. Their company consists of numFriends people, including Elly. Since they don't want to be spread across the entire hall, they decided to sit either in the same row or in the same column (though not necessarily next to one another).

Your are given a String[] hall representing the layout of seats in the theater that are already taken. The j-th character of the i-th element of hall will be '#' if the seat at row i, column j is already taken and '.' if it is empty.

Return the number of different ways for Elly and her friends to choose numFriends different empty seats so that their seating requirement is fulfilled. Two ways are considered different if there exists a person in their company that will sit in different seats in these two ways.

Constraints

  • numFriends will be between 1 and 8, inclusive.
  • hall will contain between 1 and 50 elements, inclusive.
  • Each element of hall will contain between 1 and 50 characters, inclusive.
  • All elements of hall will contain the same number of characters.
  • Each character in hall will be either '.' or '#'.
Examples
0)
2
{ ".#..",
  ".##.",
  "...." }
Returns: 34

Here the movie hall has 3 rows and 4 columns. The second seat in the first row is taken, as well as the seats in the middle of the second row.

1)
2
{ "..#",
  ".##",
  "..." }
Returns: 16

Elly and her friend can sit in two ways in the first row, they cannot sit in the second row, and they can sit in six ways in the third row. If they choose to sit in the same column, they can do it in six ways in the leftmost column, two ways in the middle column, and not in the rightmost column because there is only one seat.

2)
5
{ "..####..", 
  ".###.##.",
  ".######.",
  "#.#.#.#." }
Returns: 0

There are enough places for the company, but since they want to sit in the same row or same column, none of the possible seatings satisfies them.

3)
8
{ "........" }
Returns: 40320

Just enough seats for all of them.

4)
1
{ "." }
Returns: 1

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

Coding Area

Language: C++17 · define a public class MovieSeating with a public method long long getSeatings(int numFriends, vector<string> hall) · 139 test cases · 2 s / 256 MB per case

Submitting as anonymous