codeforces-scrape

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

2122B.md (1946B)


      1 Source: https://codeforces.com/problemset/problem/2122/B
      2 
      3 B. Pile Shuffling
      4 
      5 time limit per test
      6 
      7 1 second
      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 $n$ binary piles, the $i$-th of which consists of $a_i$ zeros on the top and $b_i$ ones on the bottom.
     22 
     23 In one operation, you can take the top element of any pile and move it to any position in any pile, including the pile it was taken from.
     24 
     25  ![](https://espresso.codeforces.com/0db537ae486941d1359d90287005ddee63578545.png) Solution of the first example test case.  Calculate the minimum number of operations required to make it so that the $i$-th pile consists of $c_i$ zeros on the top and $d_i$ ones on the bottom.
     26 
     27 Input
     28 
     29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     30 
     31 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of piles.
     32 
     33 Then $n$ lines follow, the $i$-th containing four integers $a_i$, $b_i$, $c_i$, $d_i$ ($0 \leq a_i, b_i, c_i, d_i \leq 10^9$) — the original and target state of the $i$-th pile.
     34 
     35 It is guaranteed that there exists a sequence of operations that transforms the piles into the target state.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case, output one integer — the minimum number of operations required to achieve the target state.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 3
     49 
     50 2
     51 
     52 1 3 1 2
     53 
     54 1 1 1 2
     55 
     56 3
     57 
     58 2 0 2 2
     59 
     60 0 1 1 0
     61 
     62 1 1 0 0
     63 
     64 3
     65 
     66 1 2 1 2
     67 
     68 3 4 3 4
     69 
     70 0 0 0 0
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 2
     77 3
     78 0
     79 ```
     80 
     81 Note
     82 
     83 The solution of the first test case is shown in the statement.
     84 
     85 In the second test case, an optimal solution is to do the following:
     86 
     87  ![](https://espresso.codeforces.com/cd402da4da4d022bd71d8e9811598affac4deadd.png)
     88 
     89 In the third test case, all piles are already in their target state.