codeforces-scrape

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

2170C.md (2595B)


      1 Source: https://codeforces.com/problemset/problem/2170/C
      2 
      3 C. Quotient and Remainder
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given two integer arrays: $q_1, q_2, \dots, q_n$ and $r_1, r_2, \dots, r_n$, as well as an integer $k$.
     22 
     23 You can perform the following operation any number of times (possibly zero):
     24 
     25 1. Choose two integers $x$ and $y$ such that
     26    * $1 \le y \lt x \le k$;
     27    * there exists an index $i$ such that $q_i = \left\lfloor \frac{x}{y} \right\rfloor$ (rounded down);
     28    * there exists an index $j$ such that $r_j = x \bmod y$.
     29 2. Remove $q_i$ from the array $q$ and $r_j$ from the array $r$. If there are multiple occurrences of $q_i$ in the array $q$, only one occurrence is removed; same for $r_j$ and the array $r$.
     30 
     31 Calculate the maximum number of operations that you can perform on the given arrays $q$ and $r$.
     32 
     33 Input
     34 
     35 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     36 
     37 The first line of each test case contains two integers $n$ and $k$ ($1 \le n \le 2 \cdot 10^5$; $2 \le k \le 10^{18}$) — the size of the arrays $q$ and $r$ and the upper limit for $x$ and $y$.
     38 
     39 The second line of each test case contains $n$ integers $q_1, q_2, \dots, q_n$ ($1 \le q_i \le 10^9$) — the array $q$.
     40 
     41 The third line contains $n$ integers $r_1, r_2, \dots, r_n$ ($1 \le r_i \le 10^9$) — the array $r$.
     42 
     43 Additional constraints on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     44 
     45 Output
     46 
     47 For each test case, print one integer — the maximum number of operations that you can perform on the given arrays.
     48 
     49 Example
     50 
     51 Input
     52 
     53 ```
     54 3
     55 
     56 1 100
     57 
     58 1
     59 
     60 27
     61 
     62 3 10
     63 
     64 5 6 5
     65 
     66 7 1 7
     67 
     68 5 42
     69 
     70 5 4 2 2 1
     71 
     72 9 8 9 8 100
     73 ```
     74 
     75 Output
     76 
     77 ```
     78 1
     79 
     80 0
     81 
     82 3
     83 ```
     84 
     85 Note
     86 
     87 In the first test case, one operation can be performed: you can choose $x = 69$ and $y = 42$. Then $\left\lfloor \frac{69}{42} \right\rfloor = 1 = q_1$ and $69 \bmod 42 = 27 = r_1$.
     88 
     89 In the second test case, it is impossible to perform any operations, as suitable $x$ and $y$ cannot be found.
     90 
     91 In the third test case, three operations can be performed:
     92 
     93 1. $x = 42$, $y = 17$: $\left\lfloor \frac{42}{17} \right\rfloor = 2 = q_3$ and $42 \bmod 17 = 8 = r_2$;
     94 2. $x = 41$, $y = 16$: $\left\lfloor \frac{41}{16} \right\rfloor = 2 = q_4$ and $41 \bmod 16 = 9 = r_1$;
     95 3. $x = 20$, $y = 12$: $\left\lfloor \frac{20}{12} \right\rfloor = 1 = q_5$ and $20 \bmod 12 = 8 = r_4$;
     96 
     97 After these operations, you'll get arrays $q = [5, 4]$ and $r = [9, 100]$, and there are no more operations you can perform.