codeforces-scrape

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

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\}$