Codeforces Round 766 (Div. 2) |
---|
Закончено |
У вас есть квадрат $$$k \times k$$$, причем $$$k$$$ четно. Клетка в строке $$$r$$$ и столбце $$$c$$$ обозначается $$$(r,c)$$$. Две клетки $$$(r_1, c_1)$$$ и $$$(r_2, c_2)$$$ называются соседними, если $$$\lvert r_1 - r_2 \rvert + \lvert c_1 - c_2 \rvert = 1$$$.
Массив пар соседних клеток называется прочным, если существует способ разрезать квадрат на две связных конгруэнтных части таким образом, что в каждой данной паре клеток обе клетки принадлежат одной части. Две части конгруэнтны, если одну можно наложить на другую с помощью переноса, вращения и/или зеркального отражения, а также их комбинаций.
Вам дан массив $$$a$$$ из $$$n$$$ пар соседних клеток. Найдите размер наибольшей прочной подпоследовательности $$$a$$$. Массив $$$p$$$ является подпоследовательностью $$$q$$$, если $$$p$$$ может быть получен из $$$q$$$ удалением нескольких (возможно, ни одного или всех) элементов.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leq n \leq 10^5$$$; $$$2 \leq k \leq 500$$$, $$$k$$$ четно) — размер $$$a$$$ и размер квадрата, соответственно.
Далее следуют $$$n$$$ строк. $$$i$$$-я из этих строк содержит четыре целых числа $$$r_{i,1}$$$, $$$c_{i,1}$$$, $$$r_{i,2}$$$ и $$$c_{i,2}$$$ ($$$1 \leq r_{i,1}, c_{i,1}, r_{i,2}, c_{i,2} \leq k$$$) — $$$i$$$-й элемент $$$a$$$, где $$$(r_{i,1}, c_{i,1})$$$ — строка и столбец первой клетки, а $$$(r_{i,2}, c_{i,2})$$$ — строка и столбец второй. Эти квадраты соседние.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, и что сумма значений $$$k$$$ по всем наборам входных данных не превосходит $$$500$$$.
Для каждого набора входных данных выведите одно целое число — размер наибольшей прочной подподпоследовательности $$$a$$$.
38 41 2 1 32 2 2 33 2 3 34 2 4 31 4 2 42 1 3 12 2 3 24 1 4 27 21 1 1 22 1 2 21 1 1 21 1 2 11 2 2 21 1 2 11 2 2 21 63 3 3 4
7 4 1
В первом примере $$$a$$$ не является прочным, но подпоследовательность $$$[a_1, a_2, a_3, a_4, a_5, a_6, a_8]$$$ является, т. к. квадрат может быть разрезан способом, показанным в условии.
Во втором примере подпоследовательность из четырех последних элементов $$$a$$$ является прочным, т. к. квадрат можно разрезать с помощью горизонтальной прямой через центр.
Название |
---|