Матч 398, Наименьшее расстояние (MinDifference)

Дивизион 2, Уровень 1

Заданы числа a0, x, y, m и n. Построим последовательность чисел А согласно следующим рекуррентным соотношениям:

a[0] = a0,

a[i] = (a[i – 1] * x + y) mod m, 0 < i < n

Вычислим все возможные неотрицательные разности между любыми двумя элементами А Найти наименьшее значение среди них.

Класс: MinDifference

Метод: int closestElements(int a0, int x, int y, int m, int n)

Ограничения: 1 £ a0, x, y, m £ 10000, 2 £ n £ 10000.

Вход. Числа a0, x, y, m и n.

Выход. Наименьшее абсолютное значение среди всевозможных разностей двух элементов из последовательности А.

Пример входа

a0	x	y	m	n
3	7	1	101	5
3	9	8	32	8
67	13	17	4003	23

Пример выхода

6

0

14

РЕШЕНИЕ

сортировка

Сгенерируем в массиве mas элементы последовательности А и отсортируем их. Наименьшая разница между последовательными элементами отсортированного массива является искомой. Ищем ее при помощи функции min_element.

ПРОГРАММА

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

int i,mas[10000];

class MinDifference

{

public:

int closestElements(int a0, int x, int y, int m, int n)

{

mas[0] = a0;

for(i = 1; i < n; i++) mas[i] = (mas[i-1]*x+y)%m;

sort(mas,mas+n);

for(i = 0; i < n; i++) mas[i] = abs(mas[i+1] - mas[i]);

return *min_element(mas,mas+n-1);

}

};