Олимпиадная задачка.

[ZARATUSTRA]

Дана числовая последовательность из N (1<N<1000) элементов A (1<A<1000000). Известно, что в ней есть доминирующий элемент (т.е. значение, которому равны больше чем половина элементов последовательности). Нужно найти это значение за минимальное время(линейное) за один проход последовательности.
Например(В первой строке натуральное число N, а во второй последовательность из N):
Входные данные:
4
2 4 2 2
Выходные:
2

Смог сделать только при A<10, а вот при большом A не знаю.

[ewert]

Ну если нет ограничения на память, то всё банально. Создаём массив из миллиона счётчиков, инициализируем его нулями и потом на каждом шаге проверяем, не превысило ли значение счётчика для вновь поступившего числа значения того счётчика, который перед этим считался максимальным.

[Alexu007]

Проверяем, не превысило ли значение счётчика половину N - это и будет доминирующий элемент. Дальше можно не считать.

[Zealint]

Если немного порассуждать, то придумаете алгоритм, требующий дополнительной памяти на стек из N элементов. Размеры самих чисел A при этом не играют роли. Вам нужно придумать, как при проходе по массиву с помощью стека добиться того, чтобы в конце там остался как раз доминирующий элемент. Как бы рассказывать полную идею тут нельзя...

[ZARATUSTRA]

Спасибо. Я программирование увлёкся только пару месяцев назад вдабавок к математике, поэтому, если можно, покажите реализацию на языке программирования самого простого варианта решения.

[ZARATUSTRA]

Может покажет кто хоть часть кода, где реализован простейший(!) алгоритм для этой задачи? Интересует тот момент, когда последовательность задана и программа начала проход. Не знаю, как записывать такое огромное кол-во элементов для последующего сравнения.

[Zealint]

Тов. ZARATUSTRA, если у Вас такие сложности с программированием, то я бы советовал начать его изучение с более простых задач. То, о чем Вы спрашиваете, описывается в литературе для школьников. А здесь учебные программы за Вас пишут только при добром расположении духа, да и то это не совсем по правилам.

[ZARATUSTRA]

Zealint в сообщении #541008 писал(а):

Тов. ZARATUSTRA, если у Вас такие сложности с программированием, то я бы советовал начать его изучение с более простых задач. То, о чем Вы спрашиваете, описывается в литературе для школьников. А здесь учебные программы за Вас пишут только при добром расположении духа, да и то это не совсем по правилам.

Простые задачи я изучил. Это не учебная программа), это задача по олимпиаде за прошлый год. Я и не прошу писать решение этой задачи. Смысл тогда мне готовое решение получить? Мне нужно разобраться с кусочком кода.

[wolf.ram]

ewert
олололо, массив из миллиона элементов.

Чего-нибудь вроде хеш-таблицы хватит. Нафига считать элементы, которые не встречались.

[Хорхе]

А я вот придумал, надо всего 16 чисел хранить. Подсказка: по условию, на кодирование элементов последовательности хватит 16 битов.

(решение)

$k$-й элемент массива numofbits -- количество чисел в последовательности, у которых $k$-й двоичный бит равен единичке. Иными словами, очередной член последовательности надо преобразовать в массив битов и прибавить поэлементно к numofbits. После того, как все члены последовательности перебраны, выдать число, у которого в двоичной записи на $m$-м месте единичка тогда и только тогда, когда numofbits[m]>N/2.