Codeforces Round 916 (Div. 3) |
---|
Закончено |
Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на количество наборов входных данных и $$$n$$$. В простой версии количество наборов входных данных не превосходит $$$10^3$$$, а $$$n$$$ не превосходит $$$6$$$.
Недавно Алисе и Бобу родители подарили шарики $$$n$$$ различных цветов: получилось, что у Алисы $$$a_1$$$ шариков цвета $$$1$$$, $$$a_2$$$ шариков цвета $$$2$$$,..., $$$a_n$$$ шариков цвета $$$n$$$. У Боба: $$$b_1$$$ шариков цвета $$$1$$$, $$$b_2$$$ шариков цвета $$$2$$$, ..., $$$b_n$$$ шариков цвета $$$n$$$. Все $$$a_i$$$ и $$$b_i$$$ от $$$1$$$ до $$$10^9$$$.
Посовещавшись, Алиса и Боб придумали следующую игру: игроки ходят по очереди, начиная с Алисы. На своём ходу игрок выбирает такой цвет $$$i$$$, что у обоих игроков есть хотя бы по одному шарику этого цвета. Он выбрасывает один шарик цвета $$$i$$$, а его противник — все шарики цвета $$$i$$$. Игра заканчивается, когда не существует такого цвета $$$i$$$, что у обоих игроков есть хотя бы по одному шарику этого цвета.
Счёт в игре — это количество оставшихся шариков у Алисы минус количество оставшихся шариков у Боба по окончании игры. То есть счёт равен $$$(A-B)$$$, где $$$A$$$ — количество шариков у Алисы, а $$$B$$$ — количество шариков у Боба в конце игры. Алиса хочет максимизировать счёт, а Боб — минимизировать.
Посчитайте, какой счёт будет в конце игры, если оба игрока играют оптимально.
В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^3$$$) — количество наборов входных данных.
Каждый набор входных данных состоит из трех строк:
Для каждого набора входных данных выведите одно целое число — счёт в конце игры, если и Алиса и Боб будут действовать оптимально.
534 2 11 2 441 20 1 20100 15 10 2051000000000 1000000000 1000000000 1000000000 10000000001 1 1 1 135 6 52 1 763 2 4 2 5 59 4 7 9 2 5
1 -9 2999999997 8 -6
В первом примере один из способов получить счёт $$$1$$$ — следующий:
В результате у Алисы остается $$$a = [3, 1, 0]$$$, а у Боба — $$$b = [0, 0, 3]$$$. Счёт равен $$$3 + 1 - 3 = 1$$$.
Можно показать, что ни Алиса ни Боб не могут получить лучший счёт, если оба играют оптимально.
Во втором примере Алиса может сначала выбрать цвет $$$1$$$, далее Боб выберет цвет $$$4$$$, после этого Алиса выберет цвет $$$2$$$, и Боб — цвет $$$3$$$. Можно показать, что это оптимальная игра.
Название |
---|