P7315 [COCI 2018/2019 #3] Sajam

The original time limit is 5 s, and it is set to 1 s here. Tests show that the correct algorithm can pass normally. Milo organized a Christmas fair. After it ended, he wanted to use LEET to turn off the lights.

Each area consists of $N$ rows, and each row has $N$ stalls. There are $3$ types of operations to change the lighting state (changing a lit lamp to unlit, and vice versa): 1. LEET selects an entire row and automatically toggles the lighting state of all lamps in that row. 2. LEET selects an entire column and automatically toggles the lighting state of all lamps in that column. 3. Milo selects one stall and manually toggles the lighting state of the lamp at that stall. Is there a way for Milo to turn off all lamps, using operation 3 at most $K$ times?

The first line contains integers $N, K$. The next $N$ lines each contain $N$ characters `x` or `o`, representing the lighting state of the lamps at the corresponding stalls in the Christmas fair. Here, `x` means unlit, and `o` means lit.

If there is a plan that satisfies the requirement, output `DA`; otherwise output `NE`.

#### Explanation for Sample 3 One feasible plan is: - Perform operation $2$, selecting column $1$. - Perform operation $3$, selecting $(2,2)$. - Perform operation $1$, selecting row $2$. - Perform operation $2$, selecting column $4$. - Perform operation $3$, selecting $(3,3)$. #### Constraints For $15$ points, $K = 0$. For another $15$ points, $N \le 100$. For another $30$ points, $K \lt \dfrac{N}{2}$. For $100\%$ of the testdata, $1 \le N \le 1000$, $0 \le K \le N$. #### Notes **The scoring of this problem follows the original COCI settings, with a full score of $90$. Only $18$ test points with different difficulties are selected for evaluation here.** **Translated from [COCI2018-2019](https://hsin.hr/coci/archive/2018_2019/) [CONTEST #3](https://hsin.hr/coci/archive/2018_2019/contest3_tasks.pdf) _T3 Sajam_.** Translated by ChatGPT 5