Codeforces Round 661 (Div. 3) |
---|
Закончено |
Есть $$$n$$$ людей, желающих принять участие в лодочном соревновании. Вес $$$i$$$-го участника равен $$$w_i$$$. Принять участие могут только команды, состоящие из двух человек. Как организатор вы считаете честным допустить к соревнованию только команды с одинаковым суммарным весом.
Таким образом, для $$$k$$$ команд $$$(a_1, b_1)$$$, $$$(a_2, b_2)$$$, $$$\dots$$$, $$$(a_k, b_k)$$$, где $$$a_i$$$ — вес первого участника $$$i$$$-й команды, а $$$b_i$$$ — вес второго участника $$$i$$$-й команды, должно выполняться условие $$$a_1 + b_1 = a_2 + b_2 = \dots = a_k + b_k = s$$$, где $$$s$$$ — суммарный вес для каждой команды.
Ваша задача — выбрать такое число $$$s$$$, что количество команд, которые могут быть созданы, максимально возможное. Обратите внимание: каждый участник может состоять не более чем в одной команде.
Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.
Первая строка теста содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов тестовых данных. Затем следуют $$$t$$$ наборов тестовых данных.
Первая строка набора тестовых данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество участников. Вторая строка набора тестовых данных содержит $$$n$$$ целых чисел $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le n$$$), где $$$w_i$$$ — вес $$$i$$$-го участника.
Для каждого набора тестовых данных выведите одно целое число $$$k$$$: максимальное число команд, которые могут быть составлены при суммарном весе участников в команде, равном $$$s$$$, если выбирать $$$s$$$ оптимально.
5 5 1 2 3 4 5 8 6 6 6 6 6 6 8 8 8 1 2 2 1 2 1 1 2 3 1 3 3 6 1 1 3 4 2 2
2 3 4 1 2
В первом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=6$$$. Тогда первая лодка будет использоваться участниками $$$1$$$ и $$$5$$$, а вторая лодка — участниками $$$2$$$ и $$$4$$$ (индексы совпадают с весами).
Во втором наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=12$$$. Тогда первые $$$6$$$ участников смогут образовать $$$3$$$ пары.
В третьем наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=3$$$. Ответ равен $$$4$$$, потому что у нас есть $$$4$$$ участника с весом $$$1$$$ и $$$4$$$ участника с весом $$$2$$$.
В четвертом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=4$$$ или $$$s=6$$$.
В пятом наборе тестовых данных примера мы можем достичь оптимального ответа для $$$s=3$$$. Заметьте, что участник с весом $$$3$$$ не может использовать лодку, потому что для него в списке нет подходящей пары.
Название |
---|