codeforces-scrape

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

1850F.md (2493B)


      1 Source: https://codeforces.com/problemset/problem/1850/F
      2 
      3 F. We Were Both Children
      4 
      5 time limit per test
      6 
      7 3 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 Mihai and Slavic were looking at a group of $n$ frogs, numbered from $1$ to $n$, all initially located at point $0$. Frog $i$ has a hop length of $a_i$.
     22 
     23 Each second, frog $i$ hops $a_i$ units forward. Before any frogs start hopping, Slavic and Mihai can place exactly one trap in a coordinate in order to catch all frogs that will ever pass through the corresponding coordinate.
     24 
     25 However, the children can't go far away from their home so they can only place a trap in the first $n$ points (that is, in a point with a coordinate between $1$ and $n$) and the children can't place a trap in point $0$ since they are scared of frogs.
     26 
     27 Can you help Slavic and Mihai find out what is the maximum number of frogs they can catch using a trap?
     28 
     29 Input
     30 
     31 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of frogs, which equals the distance Slavic and Mihai can travel to place a trap.
     34 
     35 The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the lengths of the hops of the corresponding frogs.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     38 
     39 Output
     40 
     41 For each test case output a single integer — the maximum number of frogs Slavic and Mihai can catch using a trap.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 7
     49 
     50 5
     51 
     52 1 2 3 4 5
     53 
     54 3
     55 
     56 2 2 2
     57 
     58 6
     59 
     60 3 1 3 4 9 10
     61 
     62 9
     63 
     64 1 3 2 4 2 3 7 8 5
     65 
     66 1
     67 
     68 10
     69 
     70 8
     71 
     72 7 11 6 8 12 4 4 8
     73 
     74 10
     75 
     76 9 11 9 12 1 7 2 5 8 10
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 3
     83 3
     84 3
     85 5
     86 0
     87 4
     88 4
     89 ```
     90 
     91 Note
     92 
     93 In the first test case, the frogs will hop as follows:
     94 
     95 * Frog 1: $0 \to 1 \to 2 \to 3 \to \mathbf{\color{red}{4}} \to \cdots$
     96 * Frog 2: $0 \to 2 \to \mathbf{\color{red}{4}} \to 6 \to 8 \to \cdots$
     97 * Frog 3: $0 \to 3 \to 6 \to 9 \to 12 \to \cdots$
     98 * Frog 4: $0 \to \mathbf{\color{red}{4}} \to 8 \to 12 \to 16 \to \cdots$
     99 * Frog 5: $0 \to 5 \to 10 \to 15 \to 20 \to \cdots$
    100 
    101 Therefore, if Slavic and Mihai put a trap at coordinate $4$, they can catch three frogs: frogs 1, 2, and 4. It can be proven that they can't catch any more frogs.
    102 
    103 In the second test case, Slavic and Mihai can put a trap at coordinate $2$ and catch all three frogs instantly.