Connection Status:
Competition Arena > PartySeats

PartySeats

SRM 164 · 2003-09-20 · by dgoodman

SRM 164 · 2003-09-20 · by dgoodman · Simple Search, Iteration, Simulation
Class Name: PartySeats
Return Type: String[]
Method Name: seating
Arg Types: (vector<string>)
Problem Statement

Problem Statement

It is time to arrange the seating around a circular table for a party. We want to alternate boys and girls around the table. We have a list of all the attendees and their genders. Each attendee is specified by a String that consists of the name, followed by one space, followed by either "boy" or "girl".

In addition to the attendees, we need to seat the HOST (a boy) and the HOSTESS (a girl) with the HOSTESS directly across from the HOST. That means that half the attendees should be on the HOST's left, and half on his right.

Create a class PartySeats that contains a method seating that is given a String[] attendees that lists all the attendees and their genders. The method returns a String[] that gives the seating plan, starting with "HOST" and proceeding clockwise around the table, including all the attendees and the HOSTESS.

If there is more than one possible seating plan, return the one that comes first lexicographically. "First lexicographically" means that each successive element in the return should be chosen to be the earliest alphabetically that is consistent with a legal seating plan. If there is no legal seating plan, the return should contain 0 elements.

Constraints

  • attendees will contain between 1 and 50 elements inclusive
  • each element of attendees will consists of a name followed by a single space followed by either "boy" or "girl". There will be no leading or trailing spaces.
  • each name will contain between 1 and 20 characters inclusive
  • each name will contain only uppercase letters 'A'-'Z'
  • no name will be "HOST" or "HOSTESS"
Examples
0)
{"BOB boy","SAM girl","DAVE boy","JO girl"}
Returns: { "HOST",  "JO",  "BOB",  "HOSTESS",  "DAVE",  "SAM" }

A girl must follow the HOST, and JO comes earliest lexicographically. Then comes a boy, and BOB is the earliest lexicographically. HOSTESS must come next so she can be opposite the HOST and then DAVE and SAM must follow in that order to honor the alternating gender requirement.

1)
{"JOHN boy"}
Returns: { }

There are more boys than girls so we cannot alternate.

2)
{"JOHN boy","CARLA girl"}
Returns: { }

There is no way to alternate gender and also have the HOST sit directly across from the HOSTESS

3)
{"BOB boy","SUZIE girl","DAVE boy","JO girl",
"AL boy","BOB boy","CARLA girl","DEBBIE girl"}
Returns: { "HOST",  "CARLA",  "AL",  "DEBBIE",  "BOB",  "HOSTESS",  "BOB",  "JO",  "DAVE",  "SUZIE" }
4)
{"X girl","T boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy","J girl","G boy"}
Returns: { "HOST",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "HOSTESS",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "G",  "J",  "T",  "X" }

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

Coding Area

Language: C++17 · define a public class PartySeats with a public method vector<string> seating(vector<string> attendees) · 36 test cases · 2 s / 256 MB per case

Submitting as anonymous