Матч 236, Числа Хемминга (HammingNumbers)

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

Числами Хемминга называются числа, простые делители которых лежат в заданном множестве. Например, если factors = {2, 3, 5}, то 90 = 2*3*3*5 является числом Хемминга, а число 70 = 2*5*7 нет, так как оно делится на 7. Число 1 всегда является первым числом Хемминга независимо от содержимого factors. Имея множество простых делителей factors, требуется найти n - ое число Хемминга. Если результат больше 2147483647, то вернуть -1.

Класс: HammingNumbers

Метод: int getNumber(vector<int> factors, int n)

Ограничения: factors содержит от 1 до 50 элементов, 2 £ factors[i] £ 300, 1 £ n £ 100000.

Вход. Массив factors, содержащий множество простых делителей числа n и само число n.

Выход. n - ое число Хемминга. Если результат больше 2147483647, то вернуть -1.

Пример входа

factors	n
{2,3,5}	15
{2,2,2,4,4,4,8,8,8}	11
{4,11,15,21,29,28}	2841

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

24

1024

2146636800

РЕШЕНИЕ

структуры данных + перебор

Будем генерировать числа Хемминга, начиная с единицы, используя структуру данных set. Занесем в нее 1. Далее совершаем n – 1 итерацию: берем наименьший элемент множества, умножаем его на все элементы массива factors и заносим полученные произведения во множество. После чего наименьший элемент удаляем. Таким образом удаляться будут числа Хемминга в возрастающем порядке пока не дойдем до очередного, n - ого числа. Если удаляемое число больше 2147483647, то можно сразу вернуть -1. Если множество на текущем шаге содержит более чем n элементов (значение n в цикле каждый раз уменьшается на 1, так что на каждой итерации n обозначает количество чисел, которое еще следует пройти), то последний элемент множества можно удалить. Это делается для того, чтобы множество не разрасталось и не было проблем с памятью. Результатом будет наименьшее значение множества. Если оно больше 2147483647, то возвращаем -1.

ПРОГРАММА

#include <cstdio>

#include <vector>

#include <set>

using namespace std;

set<long long> s;

class HammingNumbers

{

public:

int getNumber(vector<int> factors, int n)

{

s.insert(1);

while(--n)

{

long long x = *s.begin(); s.erase(s.begin());

if (x > (long long)2147483647) return -1;

for(int i = 0; i < factors.size(); i++)

{

s.insert(x * factors[i]);

if (s.size() > n) s.erase(--s.end());

}

}

return (*s.begin() > (long long)2147483647) ? -1 : *s.begin();

}

};