1401B.md (2008B)
1 Source: https://codeforces.com/problemset/problem/1401/B 2 3 B. Ternary Sequence 4 5 time limit per test 6 7 2 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 You are given two sequences $a_1, a_2, \dots, a_n$ and $b_1, b_2, \dots, b_n$. Each element of both sequences is either $0$, $1$ or $2$. The number of elements $0$, $1$, $2$ in the sequence $a$ is $x_1$, $y_1$, $z_1$ respectively, and the number of elements $0$, $1$, $2$ in the sequence $b$ is $x_2$, $y_2$, $z_2$ respectively. 22 23 You can rearrange the elements in both sequences $a$ and $b$ however you like. After that, let's define a sequence $c$ as follows: 24 25 $c_i = \begin{cases} a_i b_i & \mbox{if }a_i \gt b_i \\ 0 & \mbox{if }a_i = b_i \\ -a_i b_i & \mbox{if }a_i \lt b_i \end{cases}$ 26 27 You'd like to make $\sum_{i=1}^n c_i$ (the sum of all elements of the sequence $c$) as large as possible. What is the maximum possible sum? 28 29 Input 30 31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 Each test case consists of two lines. The first line of each test case contains three integers $x_1$, $y_1$, $z_1$ ($0 \le x_1, y_1, z_1 \le 10^8$) — the number of $0$-s, $1$-s and $2$-s in the sequence $a$. 34 35 The second line of each test case also contains three integers $x_2$, $y_2$, $z_2$ ($0 \le x_2, y_2, z_2 \le 10^8$; $x_1 + y_1 + z_1 = x_2 + y_2 + z_2 \gt 0$) — the number of $0$-s, $1$-s and $2$-s in the sequence $b$. 36 37 Output 38 39 For each test case, print the maximum possible sum of the sequence $c$. 40 41 Example 42 43 Input 44 45 ``` 46 3 47 2 3 2 48 3 3 1 49 4 0 1 50 2 3 0 51 0 0 1 52 0 0 1 53 ``` 54 55 Output 56 57 ``` 58 4 59 2 60 0 61 ``` 62 63 Note 64 65 In the first sample, one of the optimal solutions is: 66 67 $a = \{2, 0, 1, 1, 0, 2, 1\}$ 68 69 $b = \{1, 0, 1, 0, 2, 1, 0\}$ 70 71 $c = \{2, 0, 0, 0, 0, 2, 0\}$ 72 73 In the second sample, one of the optimal solutions is: 74 75 $a = \{0, 2, 0, 0, 0\}$ 76 77 $b = \{1, 1, 0, 1, 0\}$ 78 79 $c = \{0, 2, 0, 0, 0\}$ 80 81 In the third sample, the only possible solution is: 82 83 $a = \{2\}$ 84 85 $b = \{2\}$ 86 87 $c = \{0\}$