Подготовка к ЕГЭ и олимпиадам по информатике 2019 / Тренировочные варианты ЕГЭ

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант № EGE_INF_1801

Добавлен 13 октября 2017 в 1:51. Изменён 15 июня 2018 в 1:20.Скачать PDF
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Задание

Дан набор из \(N\) неотрицательных целых чисел. Необходимо определить, какое количество единиц в двоичной записи этих чисел встречается чаще всего (если разное количество единиц встречается одинаково часто, укажите наибольшее из них). В ответе через пробел укажите найденное количество единиц и число из исходного набора, содержащее соответствующее количество единиц (если таких чисел несколько, то укажите наименьшее из них).

Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел \(N\) в \(k\) раз время работы программы увеличивается не более чем в \(k\) раз. Программа считается эффективной по памяти, если память, необходимая для хранения переменных программы, не превышает одного килобайта и не увеличивается с ростом \(N\).

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел \(N\) (\(1\leq N\leq10000\)). В каждой из последующих \(N\) строк записано одно неотрицательное целое число, не превышающее 1000.

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

	5
	11
	7
	5
	9
	8

Пример выходных данных для приведённого выше примера входных данных:

	3 7

В приведённом наборе из 5 чисел имеется один элемент — 8, который имеет одну единицу в двоичной записи; два элемента, которые имеют две единицы в двоичной записи — 5, 9; два элемента — 11 и 7, которые имеют три единицы в двоичной записи. Чаще всего встречаются числа, содержащие в двоичной записи две или три единицы. Наибольшее количество единиц — 3, наименьшее из соответствующих чисел — 7.