codeforces-scrape

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

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