ЕГЭ - вычислительные задачи

От цифровых датчиков в компьютер поступает информация о характеристиках физического процесса. Результатом каждого измерения является целое число.

Вам предлагается написать эффективную, в том числе по используемой памяти, программу, которая будет выводить третье по величине (считая от минимума) значение измерения. Если несколько измерений имеют одинаковые значения, то они учитываются как одно измерение. Если искомого значения не существует (например, когда все значения измерений равны), то нужно вывести символ "#". Следует учитывать, что количество измерений может быть очень велико.

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

 

Примеры

№	Входные данные	Выходные данные
1	5 100 10 100 10 100	#

 

Дано N пар чисел. Из каждой пары нужно выбрать одно так, чтобы сумма выбранных чисел была наименьшей из возможных и не делилась на 4. В первой строке вводится число N, не превышающее 100 000.
Если таких чисел нет, вывести "no".
На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
 

 

Примеры

№	Входные данные	Выходные данные
1	6 10 10 1 7 2 5 4 5 6 9 13 13	37

Дано N пар чисел. Из каждой пары нужно выбрать одно число так, чтобы сумма выбранных чисел была наибольшей из возможных и не делилась на 4. В первой строке вводится число N, не превышает 100 000.
Если таких чисел нет, вывести "NO".

На вход подается сначала количество пар, затем сами пары.

Входные данные
В первой строке задается количество пар. В последующих строках - сами пары. Числа по модулю не превышают 30 000.

Выходные данные
Выведите ответ на задачу.

 

Примеры

№	Входные данные	Выходные данные
1	6 1 2 4 9 3 5 7 2 4 4 2 2	29

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

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

 

Выходные данные
Программа должна вывести одно число – описанное в условии произведение.

Примеры

№	Входные данные	Выходные данные
1	11 12 45 5 3 17 23 21 20 19 12 26	1170

 

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

Входные данные
На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно вещественное число с точностью до 1 знака после десятичной точки. Все числа различны.

Выходные данные
Программа должна вывести в порядке возрастания номера сигналов, произведение которых будет характеризовать данную серию. Нумерация сигналов ведется с единицы.
 

 

Примеры

№	Входные данные	Выходные данные
1	5  12.3 0.1 100.2  0.3 1.4	1 3 5

 

По каналу связи передаются данные в виде последовательности положительных целых чисел. Количество чисел заранее неизвестно, но не менее двух. Признаком конца данных считается число 0. После данных передаётся контрольное значение. Оно равно такому максимально возможному произведению двух чисел из переданного набора, которое делится на 7, но не делится на 49. Если такое произведение получить нельзя, контрольное значение считается равным 1.
Напишите эффективную, в том числе по памяти, программу, которая будет моделировать процесс приёма данных. Программа должна ввести все числа и контрольное значение, и напечатать краткий отчёт, включающий количество принятых чисел, принятое контрольное значение, вычисленное контрольное значение и вывод о совпадении значений.
Перед текстом программы кратко опишите алгоритм решения задачи, укажите используемый язык программирования и его версию.

Входные данные
В каждой строке исходных данных содержится одно целое число. Сначала идут строки с основными данными – положительными числами, затем число 0 (признак окончания данных), в последней строке – контрольное значение.

Выходные данные
Программа должна вывести отчёт по форме, приведённой ниже в примере.
 

 

Примеры

№	Входные данные	Выходные данные
1	6 7 8 9 0 64	input: 4 reference value: 64 calculated value: 63 values false

В последней строке в зависимости от результата может быть values true