Dan holds his CSC108 lectures in a rectangular N x M lecture hall. In other words, this lecture hall has N rows of seats, each of them containing exactly M seats. Here’s my attempt at drawing this layout when N = 3 and M = 5: lecture hall layout with 3 rows and 5 seats perrow The rows are numbered from 1 to N starting from the frontrow. Similarly, the columns are numbered from 1 to M starting from the leftmostcolumn. We write (r, c) to denote the c-th seat in the r-th row. When Dan walks into the lecture hall this morning, some of the seats are already taken (this is the initial layout of the lecture hall). Afterthat, the studentscome in one group at a time. From experience, Dan knows that when a group of K students enterthe lecture hall, they look for K consecutive empty seats. That is, they try to find an empty seat (r, c) such that for all integers i in [0, K-1], the seat (r, c + i) exists and is empty. If they can’t find K consecutive empty seats, they leave the lecture hall disappointedly and go play frisbee instead. Otherwise, they try to minimize r (if they have multiple options). If there are still multiple options with the minimum r, they try to minimize c. Note that with this description, one can always uniquely determine the seats they’ll take given the layout of the seats and K. Moreover, Dan observes that sometimes students that are already seated may get up and leave the lecture hall (maybe they were in the wrong class or Dan was putting them to sleep). As you can imagine, it’s distracting and noisy to have students walking around the lecture hall trying to find empty seats. Hence, as usual, Dan seeks to automate the process. Write a program that given the initial layout of the lecture hall and a description of the above-mentioned events in the order they happen, reports where every group entering the lecture hall should take their seats. The first line of the inputcontains two space-separated integers N and M denoting the number of rows and columns of the seat layout. The initial layout of the seats is described in the next N lines. Each line contains a string of length M and describes a single row of seats. The frontrow is described by the first line, the second row is described by the second line, and so on. The j-th seat in the i-th row is initially occupied if the j-th character of the i-th line is 1 and not occupied if the characteris 0. The next line contains a single integer Q, denoting the number of events. The events themselves are described in the following Q lines in chronological order. Each line describes a single event. If the eventcorresponds to K students entering the hall, the line consists of the string in followed by the integer K. Otherwise, the line consists of the string out followed by two integers r and c; this indicates that the studentsitting at (r, c) leaves the lecture hall. It’s guaranteed that there exists a studentsitting there before this event. Output For every group of K students entering the lecture hall, report on a single line which seats they take. If they can’t find K consecutive empty seats, print -1. Otherwise, if they take the seats (r, c + i) for i in [0, K-1], print r c. Report these in the orderthey happen. At the end of the output, print the final layout of the seats in the same format as the input. Sample Input 1 3 4 0110 0001 1010 6 in 3 out 2 2 in 2 in 1 out 2 3 in 2 Sample Output 1 2 1 -1 1 1 2 2 1110 1111 1010 Sample 1 Explanation The first line of the input indicates that the lecture hall has 3 rows of 4 seats each. The initial layout of the lecture hall follows. Initially, five of the seats are taken. The next line indicates that 6 events occur during the lecture. A group of three students walk into the lecture hall. The only three consecutive empty seats are the first three seats in the second row. Hence, the three students take those seats. The layout is now 0110 1111 1010 The studentsitting at (2, 2) leaves. The layout becomes 0110 1011 1010 A group of two students walk in. Since they can’t find any two consecutive empty seats, they leave immediately. A single student walks in. They have multiple options for where to sit, so they try to sit asclose to the front as possible. Row 1 has two empty seats, so the student willsit in row 1. Of the two seats, the studentchooses the leftmost one to minimize c. The layout becomes 1110 1011 1010 Two more events occur(make sure you understand their effect!). Sample Input 2 2 4 1111 0000 11 in 3 out 1 1 in 2 out 2 3 in 2 out 2 1 out 2 2 out 1 2 in 2 in 2 in 10 Sample Output 2 2 1 -1 2 3 1 1 2 1 -1 1111 1111
Help please!
Dan holds his CSC108 lectures in a rectangular N x M lecture hall. In other words,
this lecture hall has N rows of seats, each of them containing exactly M seats.
Here’s my attempt at drawing this layout when N = 3 and M = 5:
lecture hall layout with 3 rows and 5 seats perrow
The rows are numbered from 1 to N starting from the frontrow. Similarly, the
columns are numbered from 1 to M starting from the leftmostcolumn. We write
(r, c) to denote the c-th seat in the r-th row.
When Dan walks into the lecture hall this morning, some of the seats are already
taken (this is the initial layout of the lecture hall). Afterthat, the studentscome in
one group at a time. From experience, Dan knows that when a group of K students
enterthe lecture hall, they look for K consecutive empty seats. That is, they try to
find an empty seat (r, c) such that for all integers i in [0, K-1], the seat (r, c +
i) exists and is empty. If they can’t find K consecutive empty seats, they leave the
lecture hall disappointedly and go play frisbee instead. Otherwise, they try to
minimize r (if they have multiple options). If there are still multiple options with
the minimum r, they try to minimize c. Note that with this description, one can
always uniquely determine the seats they’ll take given the layout of the seats and
K.
Moreover, Dan observes that sometimes students that are already seated may get
up and leave the lecture hall (maybe they were in the wrong class or Dan was
putting them to sleep).
As you can imagine, it’s distracting and noisy to have students walking around the
lecture hall trying to find empty seats. Hence, as usual, Dan seeks to automate
the process.
Write a program that given the initial layout of the lecture hall and a description
of the above-mentioned events in the order they happen, reports where every
group entering the lecture hall should take their seats.
The first line of the inputcontains two space-separated integers N and M denoting
the number of rows and columns of the seat layout.
The initial layout of the seats is described in the next N lines. Each line contains a
string of length M and describes a single row of seats. The frontrow is described by
the first line, the second row is described by the second line, and so on. The j-th
seat in the i-th row is initially occupied if the j-th character of the i-th line is 1
and not occupied if the characteris 0.
The next line contains a single integer Q, denoting the number of events. The
events themselves are described in the following Q lines in chronological order.
Each line describes a single event. If the eventcorresponds to K students entering
the hall, the line consists of the string in followed by the integer K. Otherwise, the
line consists of the string out followed by two integers r and c; this indicates that
the studentsitting at (r, c) leaves the lecture hall. It’s guaranteed that there
exists a studentsitting there before this event.
Output
For every group of K students entering the lecture hall, report on a single line
which seats they take. If they can’t find K consecutive empty seats, print -1.
Otherwise, if they take the seats (r, c + i) for i in [0, K-1], print r c. Report
these in the orderthey happen.
At the end of the output, print the final layout of the seats in the same format as
the input.
Sample Input 1
3 4
0110
0001
1010
6
in 3
out 2 2
in 2
in 1
out 2 3
in 2
Sample Output 1
2 1
-1
1 1
2 2
1110
1111
1010
Sample 1 Explanation
The first line of the input indicates that the lecture hall has 3 rows of 4 seats
each.
The initial layout of the lecture hall follows. Initially, five of the seats are
taken.
The next line indicates that 6 events occur during the lecture.
A group of three students walk into the lecture hall. The only three
consecutive empty seats are the first three seats in the second row. Hence, the
three students take those seats. The layout is now
0110
1111
1010
The studentsitting at (2, 2) leaves. The layout becomes
0110
1011
1010
A group of two students walk in. Since they can’t find any two consecutive
empty seats, they leave immediately.
A single student walks in. They have multiple options for where to sit, so they
try to sit asclose to the front as possible. Row 1 has two empty seats, so the
student willsit in row 1. Of the two seats, the studentchooses the leftmost
one to minimize c. The layout becomes
1110
1011
1010
Two more events occur(make sure you understand their effect!).
Sample Input 2
2 4
1111
0000
11
in 3
out 1 1
in 2
out 2 3
in 2
out 2 1
out 2 2
out 1 2
in 2
in 2
in 10
Sample Output 2
2 1
-1
2 3
1 1
2 1
-1
1111
1111
Step by step
Solved in 4 steps with 3 images
