codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1914E1.md (3328B)


      1 Source: https://codeforces.com/problemset/problem/1914/E1
      2 
      3 E1. Game with Marbles (Easy Version)
      4 
      5 time limit per test
      6 
      7 3.5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 The easy and hard versions of this problem differ only in the constraints on the number of test cases and $n$. In the easy version, the number of test cases does not exceed $10^3$, and $n$ does not exceed $6$.
     22 
     23 Recently, Alice and Bob were given marbles of $n$ different colors by their parents. Alice has received $a_1$ marbles of color $1$, $a_2$ marbles of color $2$,..., $a_n$ marbles of color $n$. Bob has received $b_1$ marbles of color $1$, $b_2$ marbles of color $2$, ..., $b_n$ marbles of color $n$. All $a_i$ and $b_i$ are between $1$ and $10^9$.
     24 
     25 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 $i$ such that both players have at least one marble of that color. The player then discards one marble of color $i$, and their opponent discards all marbles of color $i$. The game ends when there is no color $i$ such that both players have at least one marble of that color.
     26 
     27 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 $(A-B)$, where $A$ is the number of marbles Alice has and $B$ 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.
     28 
     29 Calculate the score at the end of the game if both players play optimally.
     30 
     31 Input
     32 
     33 The first line contains a single integer $t$ ($1 \le t \le 10^3$) — the number of test cases.
     34 
     35 Each test case consists of three lines:
     36 
     37 * the first line contains a single integer $n$ ($2 \le n \le 6$) — the number of colors;
     38 * the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of marbles of the $i$-th color that Alice has;
     39 * the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$), where $b_i$ is the number of marbles of the $i$-th color that Bob has.
     40 
     41 Output
     42 
     43 For each test case, output a single integer — the score at the end of the game if both Alice and Bob act optimally.
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 5
     51 
     52 3
     53 
     54 4 2 1
     55 
     56 1 2 4
     57 
     58 4
     59 
     60 1 20 1 20
     61 
     62 100 15 10 20
     63 
     64 5
     65 
     66 1000000000 1000000000 1000000000 1000000000 1000000000
     67 
     68 1 1 1 1 1
     69 
     70 3
     71 
     72 5 6 5
     73 
     74 2 1 7
     75 
     76 6
     77 
     78 3 2 4 2 5 5
     79 
     80 9 4 7 9 2 5
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 1
     87 -9
     88 2999999997
     89 8
     90 -6
     91 ```
     92 
     93 Note
     94 
     95 In the first example, one way to achieve a score of $1$ is as follows:
     96 
     97 1. Alice chooses color $1$, discards $1$ marble. Bob also discards $1$ marble;
     98 2. Bob chooses color $3$, discards $1$ marble. Alice also discards $1$ marble;
     99 3. Alice chooses color $2$, discards $1$ marble, and Bob discards $2$ marble.
    100 
    101 As a result, Alice has $a = [3, 1, 0]$ remaining, and Bob has $b = [0, 0, 3]$ remaining. The score is $3 + 1 - 3 = 1$.
    102 
    103 It can be shown that neither Alice nor Bob can achieve a better score if both play optimally.
    104 
    105 In the second example, Alice can first choose color $1$, then Bob will choose color $4$, after which Alice will choose color $2$, and Bob will choose color $3$. It can be shown that this is the optimal game.