TopCoder problem "AirlinerSeats" used in SRM 277 (Division I Level Two)



Problem Statement

    

Note: this problem statement contains an image that may not display properly if viewed outside the applet.

When on a long flight, it is often helpful to be in an aisle seat (a seat adjacent to an aisle). This way you don't need to bother another passenger when you need to go to the restroom or take a walk. However, because large airliners are built to hold as many passengers as possible, only a limited number of seats can be aisle seats.

A typical arrangement of 10 seats in a single row with 2 aisles is as follows:

Aisle seats are colored green in the above example (there are four such seats), while center and window seats are colored orange.

All of the seats are equally wide and each aisle has the same width as a single seat. If an airplane's row is wide enough to fit width seats or aisles, and the airline wants exactly seats seats to be fitted in a row, find the arrangement which maximizes the number of aisle seats. A row should be formatted as a string of characters so that seats and aisles are represented by 'S' and '.' (dot) characters, respectively. If there are multiple arrangements which maximize the number of aisle seats, find the lexicographically smallest one (the dot character comes before 'S' in the lexicographical order).

You are to return the required arrangement (or part of it) as a String[] containing no more than 2 Strings:

  • If width is 50 or less, return the entire arrangement as a single String inside the String[].
  • If width is between 51 and 100 (inclusive), return the entire arrangement as two Strings, split after the first 50 characters.
  • If width is more than 100, return two Strings containing the first and last 50 characters of the arrangement, respectively.

 

Definition

    
Class:AirlinerSeats
Method:mostAisleSeats
Parameters:int, int
Returns:String[]
Method signature:String[] mostAisleSeats(int width, int seats)
(be sure your method is public)
    
 

Constraints

-width will be between 1 and 100000, inclusive.
-seats will be between 0 and width, inclusive.
 

Examples

0)
    
6
3
Returns: {"..SS.S" }
All three seats can be made aisle seats and this is the lexicographically smallest such arrangement.
1)
    
6
4
Returns: {"S.SS.S" }
This is the only arrangement where all four seats are aisle seats.
2)
    
12
10
Returns: {"S.SS.SSSSSSS" }
The picture in the problem statement shows another arrangement with the maximum number of aisle seats, but this one is lexicographically smaller.
3)
    
11
7
Returns: {".SS.SS.SS.S" }
4)
    
52
52
Returns: {"SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS", "SS" }
5)
    
200
2
Returns: 
{"..................................................",
"...............................................S.S" }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=4828

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8074&pm=4828

Writer:

lovro

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Greedy