Модуль: Жадные алгоритмы


7. Ризотто Нэро и магнитный конструктор

Ризотто Нэро любит собирать домики из магнитного конструктора.
У него есть n деталей, размер i-ой равен si
Для того, чтобы построить домик, необходимо ровно a деталей какого-то одинакового размера и ровно b деталей другого одинакового размера, который в k раз больше.

Определите максимальное количество домиков, которое сможет построить Ризотто Нэро.

Входные данные:
В первой строке записаны целые числа n, a, b и k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
Вторая строка содержит последовательность размеров деталей — целые числа s1, s2, …, sn (1 ≤ si ≤ 106).

Выходные данные:
Выведите единственное целое число — максимальное количество домиков, которое можно построить из n заданных деталей.

Примеры:
 
Входные данные Выходные данные
12 1 2 2
1 1 2 2 2 2 2 3 3 4 6 6
3
14 1 1 3
3 3 1 1 9 9 2 3 6 6 3 18 3 18
6
1 2 3 10
1000000
0

Пояснение:
В первом примере оптимальным вариантом является построить два домика из деталей с размерами [1, 2, 2] и один домик из деталей с размерами [3, 6, 6].
 

Напишите программу
Auto
       

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Комментарий учителя

Foxford Lectarium.ru