DMOPC '15 Contest 4 P6 - Alarms - Olympiads Online Judge

DMOPC '15 Contest 4 P6 - Alarms

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

Library and Archives Canada recently decided to install an alarm system to safeguard the English essays of past generations, and they've hired you to help them.

The Archives may be represented by an $N \times N$ $N \times N$ matrix, with a cell containing 1 representing an empty room, and 0 representing a wall. Your task is to place exactly $A$ $A$ alarms in the building so that the essays are maximally safeguarded. Each alarm $i$ $i$ has a square range of $R_i$ $R_{i}$ units around its radius, and you're interested in covering a maximum number of rooms.

There are a couple of restrictions:

no alarm may be placed in a wall
you may only place one alarm per column or row
an alarm's range cannot overlap with the outside of the building
alarm ranges can overlap

Knowing this, what is the maximum number of rooms you can hope to secure?

Input Specification

The first line of input will contain the integer $N$ $N$ $(1 \le N \le 6)$ $(1 \leq N \leq 6)$ .
The next $N$ $N$ lines will each contain $N$ $N$ space-separated integers, representing one row of the Archives.
The next line of input will contain the integer $A$ $A$ $(1 \le A \le 6)$ $(1 \leq A \leq 6)$ .
The final line of input will contain $A$ $A$ space-separated integers, with the $i$ $i$ -th integer denoting $R_i$ $R_{i}$ $(1 \le R_i \le 3)$ $(1 \leq R_{i} \leq 3)$ .

Output Specification

A single integer; the maximum number of rooms that may be covered by alarms.

Sample Input

Copy

Sample Output

Copy

Explanation

You can place the radius $2$ $2$ alarm at $(1, 2)$ $(1, 2)$ , and two radius $1$ $1$ alarms at $(2, 0)$ $(2, 0)$ and $(3, 1)$ $(3, 1)$ for a coverage of $10$ $10$ . You are left with one more alarm, but you cannot cover any more rooms without placing multiple alarms on the same row or column.

Comments

0

aeternalis1 commented on Aug. 23, 2017, 8:26 a.m. ← edit 3 →

Clarification

The problem statement states that you need to place exactly $A$ $A$ alarms; along with the row/column restriction, isn't it possible for certain test cases to be impossible to fulfill? Such as any test case with $A>N$ $A > N$ , or less rooms than alarms.

-1

jimgao commented on Jan. 12, 2016, 11:46 p.m. ← edited →

What does it mean exactly by

has a square range of $R_i$ $R_{i}$ units around its radius

5

d commented on Jan. 12, 2016, 11:11 p.m. ← edited →

4
FatalEagle commented on Jan. 12, 2016, 11:44 p.m. ← edited →
For example, a square range of radius 2 covers

Copy
1 1 1 1 1 1 1 1 1

1

StouffvilleTeam commented on Jan. 12, 2016, 7:53 p.m. ← edited →

what does it mean:

an alarm's range cannot overlap with the outside of the building

Does it mean the alarm range cannot include wall or go outside the $N \times N$ $N \times N$ square?

Thx

1
Xyene commented on Jan. 12, 2016, 7:55 p.m.
It cannot go outside the $N\times N$ $N \times N$ area. For example, in

Copy
1 1 0 0 1 0 1 1 1

you may only place an alarm with $R=2$ $R = 2$ in the center.