## DMOPC '18 Contest 2 P6 - Standing Ovation

View as PDF

Points: 30 (partial)
Time limit: 15.0s
Memory limit: 1G

Author:
Problem type

At the Nova Theatre, the balcony seats can be seen as a grid with rows and columns. The theatre is packed and the seats are all filled. At the end of the play, people in the balcony stand to give their applause. The of these people is sitting in row , column . The rest of the people will only stand if at least two people adjacent to them are standing. How many people will end up standing?

for all
for all

#### Input Specification

The first line will contain three space-separated integers, .
The next lines each contain two space-separated integers, and , representing the person initially standing.

#### Sample Input 1

3 4 5
1 1
1 2
1 3
2 1
3 1

#### Sample Output 1

9

#### Explanation for Sample 1

Initially, the grid appears as:

S S S O
S O O O
S O O O

where S denotes someone standing and O denotes someone sitting.
Then it becomes:

S S S O
S S O O
S O O O

Then:

S S S O
S S S O
S S O O

Finally:

S S S O
S S S O
S S S O

No more people stand, so the people end up standing.

#### Sample Input 2

3 5 4
1 1
3 1
1 4
2 5

#### Sample Output 2

7

#### Sample Input 3

3 5 4
1 1
3 1
1 3
2 4

#### Sample Output 3

12