306031: CF1133D. Zero Quantity Maximization

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Zero Quantity Maximization

题意翻译

# 零数最大化 ## 题目描述 给出两个长度为 $n$ 的数组 $a,b$。 你想要创建一个长度为 $n$ 的数组 $c$,且$c_i=d*a_i+b_i,i\in[1, n]$,要求你给 $d$ 赋值,使得数组 $c$ 中的 $0$ 的个数最多并输出最多的 $0$ 的个数。 ## 输入格式 第一行一个整数 $n$, 第二行 $n$ 个整数为数组 $a$, 第二行 $n$ 个整数为数组 $b$, ## 输出格式 一个数为数组 $c$ 中最多的 $0$ 的个数

题目描述

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.

输入输出样例

输入样例 #1

5
1 2 3 4 5
2 4 7 11 3

输出样例 #1

2

输入样例 #2

3
13 37 39
1 2 3

输出样例 #2

2

输入样例 #3

4
0 0 0 0
1 2 3 4

输出样例 #3

0

输入样例 #4

3
1 2 -1
-6 -12 6

输出样例 #4

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 $ .

Input

题意翻译

# 零数最大化 ## 题目描述 给出两个长度为 $n$ 的数组 $a,b$。 你想要创建一个长度为 $n$ 的数组 $c$,且$c_i=d*a_i+b_i,i\in[1, n]$,要求你给 $d$ 赋值,使得数组 $c$ 中的 $0$ 的个数最多并输出最多的 $0$ 的个数。 ## 输入格式 第一行一个整数 $n$, 第二行 $n$ 个整数为数组 $a$, 第二行 $n$ 个整数为数组 $b$, ## 输出格式 一个数为数组 $c$ 中最多的 $0$ 的个数

加入题单

上一题 下一题 算法标签: