eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

F. Козак Вус та цукерки

F. Козак Вус та цукерки

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Козак Вус дуже любить стрибати, а також любить цукерки. Одного разу його занесло на числову пряму, у деяких цiлочисельних точках якої лежали цукерки (у кожнiй точцi не бiльше одної цукерки). Вус нечувано зрадiв та вирiшив зiбрати якомога бiльше цукерок. Для цього вiн може вибрати будь-яке цiле число x > 1 i початкову позицiю s (s — цiле число), пiсля чого вiн стрибками довжини x побуває у всiх точках вигляду s+kx, де k —невiд’ємне цiле число. Коли Вус потрапляє в точку, у якiй є цукерка, то вiн пiдбирає її з землi (хоча так робити не можна!).Допоможiть Вусу зiбрати якомога бiльшу кiлькiсть цукерок.

####Протокол взаємодiї

Вам потрiбно реалiзувати одну функцiю:

integer solve(integer n, integer g, array of integers m)

  • n—кiлькiсть цукерок;

  • g —номер блока;

  • m—масив iз позицiй цукерок;

  • ця функцiя має повертати одне цiле число—максимальну кiлькiсть цукерок, яку може зiбрати Вус.

Вхідні дані

Перший рядок мiстить два цiлi числа n та g (1 ⩽ n ⩽ 10^5; 0 ⩽ g ⩽ 6) — кiлькiсть цукерок та номер блоку, вiдповiдно.

Другий рядок мiстить n цiлих чисел a[1]; a[2]; : : : ; a[n] (1 ⩽ a[i]10^9) — позицiї, у яких знаходяться цукерки. Гарантується, що всi ai попарно рiзнi.

Вихідні дані

У єдиному рядку буде виведена максимальна кiлькiсть цукерок, що зможе зiбрати Вус.

####Примiтка

У першому прикладi Козак може вибрати x = 2 та пiдiбрати цукерки на позицiях 1; 3; 7.У другому прикладi Козак може вибрати x = 3 та пiдiбрати цукерки на позицiях 1; 4; 7; 10; 13.

####Оцiнювання

  1. (4 бали) n ⩽ 2; a[i] ⩽ 10;

  2. (5 балiв) n ⩽ 3; a[i]10^2;

  3. (12 балiв) n ⩽ 10; a[i]10^2;

  4. (20 балiв) n ⩽ 10^3; a[i]10^4;

  5. (25 балiв) n ⩽ 10^4; a[i]10^6;

  6. (34 бали) без додаткових обмежень.

Приклад

Вхідні дані #1
5 0
1 2 3 4 7
Вихідні дані #1
3
14528486
Вхідні дані #2
7 0
1 2 10 4 7 3 13
Вихідні дані #2
5
14528486
Джерело XXXII Всеукраїнська олiмпiада з iнформатики, Одеса, 25-29 березня 2019 року