CF1914E1.Game with Marbles (Easy Version)

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

The easy and hard versions of this problem differ only in the constraints on the number of test cases and nn . In the easy version, the number of test cases does not exceed 10310^3 , and nn does not exceed 66 .

Recently, Alice and Bob were given marbles of nn different colors by their parents. Alice has received a1a_1 marbles of color 11 , a2a_2 marbles of color 22 ,..., ana_n marbles of color nn . Bob has received b1b_1 marbles of color 11 , b2b_2 marbles of color 22 , ..., bnb_n marbles of color nn . All aia_i and bib_i are between 11 and 10910^9 .

After some discussion, Alice and Bob came up with the following game: players take turns, starting with Alice. On their turn, a player chooses a color ii such that both players have at least one marble of that color. The player then discards one marble of color ii , and their opponent discards all marbles of color ii . The game ends when there is no color ii such that both players have at least one marble of that color.

The score in the game is the difference between the number of remaining marbles that Alice has and the number of remaining marbles that Bob has at the end of the game. In other words, the score in the game is equal to (AB)(A-B) , where AA is the number of marbles Alice has and BB is the number of marbles Bob has at the end of the game. Alice wants to maximize the score, while Bob wants to minimize it.

Calculate the score at the end of the game if both players play optimally.

输入格式

The first line contains a single integer tt ( 1t1031 \le t \le 10^3 ) — the number of test cases.

Each test case consists of three lines:

  • the first line contains a single integer nn ( 2n62 \le n \le 6 ) — the number of colors;
  • the second line contains nn integers a1,a2,,ana_1, a_2, \dots, a_n ( 1ai1091 \le a_i \le 10^9 ), where aia_i is the number of marbles of the ii -th color that Alice has;
  • the third line contains nn integers b1,b2,,bnb_1, b_2, \dots, b_n ( 1bi1091 \le b_i \le 10^9 ), where bib_i is the number of marbles of the ii -th color that Bob has.

输出格式

For each test case, output a single integer — the score at the end of the game if both Alice and Bob act optimally.

输入输出样例

  • 输入#1

    5
    3
    4 2 1
    1 2 4
    4
    1 20 1 20
    100 15 10 20
    5
    1000000000 1000000000 1000000000 1000000000 1000000000
    1 1 1 1 1
    3
    5 6 5
    2 1 7
    6
    3 2 4 2 5 5
    9 4 7 9 2 5

    输出#1

    1
    -9
    2999999997
    8
    -6

说明/提示

In the first example, one way to achieve a score of 11 is as follows:

  1. Alice chooses color 11 , discards 11 marble. Bob also discards 11 marble;
  2. Bob chooses color 33 , discards 11 marble. Alice also discards 11 marble;
  3. Alice chooses color 22 , discards 11 marble, and Bob discards 22 marble.

As a result, Alice has a=[3,1,0]a = [3, 1, 0] remaining, and Bob has b=[0,0,3]b = [0, 0, 3] remaining. The score is 3+13=13 + 1 - 3 = 1 .

It can be shown that neither Alice nor Bob can achieve a better score if both play optimally.

In the second example, Alice can first choose color 11 , then Bob will choose color 44 , after which Alice will choose color 22 , and Bob will choose color 33 . It can be shown that this is the optimal game.

首页