CINECOVI - Cinema seating, covid 19 version

This challenge involves writing a simple cinema seat booking system.  Cinemas are opening up post lockdown, but they have to seat customers differently. No longer is it OK to try and fill all seats, or allow customers to choose their own.  

Each group who book through the booking office need to sit together, and there needs to be an empty seat between groups on all sides (left, right, infront and behind). The seats in the cinema are filled from the bottom left, in order of booking. If a row fills up, we start filling on the left hand side of the next row back.

(For the purposes of illustration, imagine that the screen is at the base of the grid and that we fill the front row first).

So, if we have a cinema with just three rows, with 10 seats per row, and the following group sizes in our booking

5 4 3 2 1

we will be able to seat the first group of 5 at bottom left, then the group of 4 next to them after a gap of one seat. We'll leave a row behind, then the back row will fit the 3, 2 and 1. The seats would look like this:

Seats:
1110110100
0000000000
1111101111

If there were more bookings and instead we had the group sizes

5 4 3 2 1 1 2 3 4 5

we would have to turn away some groups. In this case, the seats would look like this:

Seats:
1110110101
0000000000
1111101111
Failed to seat:
2
3
4
5

Input

The first line of your input contains two integers, which specify the size of the cinema in terms of number of rows and number of seats per row.

Output

Your output  should be the word "Seats:" on a line of its own, followed by an array of 1s and 0s represented the seats in the cinema (1=full, 0=empty). If you find that there are groups who cannot be seated in the cinema because it is too full, output the phrase "Failed to seat:" on the next line, followed by the sizes of the unseated groups in order, one per line.

Example

Input:
5 20
7 9 8 7 6 5 4 3 2 1 9 2 11 4 8 Output: Seats:
11111101111101111000
00000000000000000000
11111111011111110000
00000000000000000000
11111110111111111000
Failed to seat:
3
2
1
9
2
11
4
8

Added by:handee
Date:2021-06-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2021-07-04 21:31:42
The problem could be more realistic and interesting while remaing basic if we had to seat groups in order, but only reject ones that we can't fit, with the start-from-leftmost constraint modifed to start-from-leftmost-free. This means for cases like this:

3 5
2 2 1 3 1 2

The answer would be:

Seats:
10011
00100
11011
Failed to seat:
3

Please consider modifying the statement and testcases while there are still no solvers apart of myself. Also, ideally a problem would have multiple cases per file and use few files to avoid runtime distortion for languages with startup lag.

Please always state constraints, in this case for cinema dimensions and amount of groups.

Last edit: 2021-07-04 21:34:16
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.