1133D.md (1459B)
1 Source: https://codeforces.com/problemset/problem/1133/D 2 3 D. Zero Quantity Maximization 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 arrays $a$ and $b$, each contains $n$ integers. 22 23 You want to create a new array $c$ as follows: choose some real (i.e. not necessarily integer) number $d$, and then for every $i \in [1, n]$ let $c_i := d \cdot a_i + b_i$. 24 25 Your goal is to maximize the number of zeroes in array $c$. What is the largest possible answer, if you choose $d$ optimally? 26 27 Input 28 29 The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of elements in both arrays. 30 31 The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($-10^9 \le a_i \le 10^9$). 32 33 The third line contains $n$ integers $b_1$, $b_2$, ..., $b_n$ ($-10^9 \le b_i \le 10^9$). 34 35 Output 36 37 Print one integer — the maximum number of zeroes in array $c$, if you choose $d$ optimally. 38 39 Examples 40 41 Input 42 43 ``` 44 5 45 1 2 3 4 5 46 2 4 7 11 3 47 ``` 48 49 Output 50 51 ``` 52 2 53 ``` 54 55 Input 56 57 ``` 58 3 59 13 37 39 60 1 2 3 61 ``` 62 63 Output 64 65 ``` 66 2 67 ``` 68 69 Input 70 71 ``` 72 4 73 0 0 0 0 74 1 2 3 4 75 ``` 76 77 Output 78 79 ``` 80 0 81 ``` 82 83 Input 84 85 ``` 86 3 87 1 2 -1 88 -6 -12 6 89 ``` 90 91 Output 92 93 ``` 94 3 95 ``` 96 97 Note 98 99 In the first example, we may choose $d = -2$. 100 101 In the second example, we may choose $d = -\frac{1}{13}$. 102 103 In the third example, we cannot obtain any zero in array $c$, no matter which $d$ we choose. 104 105 In the fourth example, we may choose $d = 6$.