P3325 [SDOI2015] Analog Circuit

A well-known chip company asks you to help install components that stabilize voltage on some of their latest products. Each chip is designed as an $N \times N$ grid of slots; a slot can hold a single component. Your task is to insert as many new components as possible. Modern processors are complex. To keep the voltage stable, you must obey several restrictions: some slots are unusable; some slots are already occupied by other components and thus cannot be used for new ones; memory buses attach to the horizontal and vertical boundaries of the chip, and their load voltages must be safe. Specifically, the company provides $N$ sets of constraints, one per row. For row $i$ (and its constraint set $i$), you are given a nonnegative integer $T_i$ and $T_i$ column indices $r_{i,j}$ ($1 \le j \le T_i$). The requirement is: the number of components in row $i$ must not exceed the sum of the numbers of components in the specified $T_i$ columns (i.e., at most “the number of components in column $r_{i,1}$ + the number of components in column $r_{i,2}$ + $\cdots$”). To avoid slot overheating, you are given a real number $s_i$ ($1 \le i \le N$) with $0 \le s_i \le 1$, and you must ensure that the number of components in row $i$ does not exceed $s_i$ times the total number of components. Similarly, you are given a real number $t_i$ ($1 \le i \le N$) with $0 \le t_i \le 1$, and you must ensure that the number of components in column $i$ does not exceed $t_i$ times the total number of components. Note that slots already occupied by components are counted when computing the number of components in any row or column. They are also counted in the total number of components on the chip. The chip is described by an $N$-row, $N$-column character matrix, where `.` denotes an open slot, `/` denotes an unusable slot, and `C` denotes a slot already occupied by a component.

- The first line contains a positive integer $N$ ($1 \le N \le 40$), the size of the chip. - Then follow $N$ lines, each containing $N$ characters describing the slots, each character being one of `.`, `/`, or `C`, as defined above. - Then follow $N$ lines describing the constraint sets. On the $i$-th of these lines, first a nonnegative integer $T_i$ is given, followed by $T_i$ distinct integers (each between $1$ and $N$) specifying the related columns. - The next line contains $N$ real numbers, in order, corresponding to $s_i$. Each number has at most three digits after the decimal point. - The next line contains $N$ real numbers, in order, corresponding to $t_i$. Each number has at most three digits after the decimal point.

If there exists a valid placement strategy, output the maximum number of additional components that can be installed on the chip. Otherwise, output `impossible`.

Translated by ChatGPT 5