Codeforces Round 644 (Div. 3) |
---|
Закончено |
Рассмотрим все двоичные строки длины $$$m$$$ ($$$1 \le m \le 60$$$), то есть строки, состоящие из символов 0 и 1. Например, 0110 является двоичной строкой, а 012aba — нет. Очевидно, что всего таких строк ровно $$$2^m$$$.
Строка $$$s$$$ лексикографически меньше строки $$$t$$$ (обе имеют одинаковую длину $$$m$$$), если в первой слева позиции $$$i$$$, в которой они отличаются, верно $$$s[i] < t[i]$$$. Именно такой способ сравнения строк используется в словарях и в большинстве современных языков программирования при их сравнении стандартным способом. Например, строка 01011 лексикографически меньше строки 01100, потому что первые два символа совпадают, а третий символ в первой строке меньше, чем во второй.
Удалим из этого множества $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) различных двоичных строк $$$a_1, a_2, \ldots, a_n$$$, каждая длины $$$m$$$. Таким образом, в множестве останется $$$k=2^m-n$$$ строк. Отсортируем все строки полученного множества в порядке лексикографического возрастания (как в словаре).
Пронумеруем все строки после сортировки от $$$0$$$ до $$$k-1$$$. Выведите строку, номер которой равен $$$\lfloor \frac{k-1}{2} \rfloor$$$ (такой элемент называется медианой), где $$$\lfloor x \rfloor$$$ является округлением числа вниз к ближайшему целому.
Например, если $$$n=3$$$, $$$m=3$$$ и $$$a=[$$$010, 111, 001$$$]$$$, то после удаления строк $$$a_i$$$ и сортировки результат примет вид: $$$[$$$000, 011, 100, 101, 110$$$]$$$. Таким образом, искомая медиана равна 100.
В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных в тесте. Далее следуют $$$t$$$ наборов тестовых данных.
В первой строке каждого набора записаны целые числа $$$n$$$ ($$$1 \le n \le \min(2^m-1, 100)$$$) и $$$m$$$ ($$$1 \le m \le 60$$$), где $$$n$$$ — количество удаляемых строк, $$$m$$$ — длина двоичных строк. Следующие $$$n$$$ строк содержат $$$a_1, a_2, \ldots, a_n$$$ — различные двоичные строки длины $$$m$$$.
Суммарная длина всех заданных двоичных строк во всех наборах тестовых данных в одном тесте не превосходит $$$10^5$$$.
Выведите $$$t$$$ ответов на наборы тестовых данных. Ответом является строка длины $$$m$$$ — медиана оставшихся строк.
5 3 3 010 001 111 4 3 000 111 100 011 1 1 1 1 1 0 3 2 00 01 10
100 010 0 1 11
Первый набор тестовых данных примера разобран в условии.
Во втором наборе результат после удаления строк и сортировки равен $$$[$$$001, 010, 101, 110$$$]$$$. Следовательно, искомая медиана равна 010.
Название |
---|