Codeforces Round 544 (Div. 3) |
---|
Finished |
You are given two arrays $$$a$$$ and $$$b$$$, each contains $$$n$$$ integers.
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$$$.
Your goal is to maximize the number of zeroes in array $$$c$$$. What is the largest possible answer, if you choose $$$d$$$ optimally?
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of elements in both arrays.
The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$).
The third line contains $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ ($$$-10^9 \le b_i \le 10^9$$$).
Print one integer — the maximum number of zeroes in array $$$c$$$, if you choose $$$d$$$ optimally.
5 1 2 3 4 5 2 4 7 11 3
2
3 13 37 39 1 2 3
2
4 0 0 0 0 1 2 3 4
0
3 1 2 -1 -6 -12 6
3
In the first example, we may choose $$$d = -2$$$.
In the second example, we may choose $$$d = -\frac{1}{13}$$$.
In the third example, we cannot obtain any zero in array $$$c$$$, no matter which $$$d$$$ we choose.
In the fourth example, we may choose $$$d = 6$$$.
Name |
---|