На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы — это вещественное неотрицательное число, записанное с точностью до одного знака после десятичной точки. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Все значения скоростей не превосходят 100000. При обработке результатов в каждой серии эксперимента отбирается основное множество частиц. Это такое непустое подмножество частиц, для которого произведение скоростей является максимально возможным. Если таких подмножеств несколько, то из них выбирается множество, которое содержит наименьшее количество элементов. В основное множество могут войти, например, как все частицы, так и ровно одна частица. Если числовое множество содержит только одно число х, то произведением элементов этого множества является число х.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя количество элементов в основном множестве и значение минимального элемента в этом множестве. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи.
На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно неотрицательное вещественное число с точностью до 1 знака после десятичной точки. Пример входных данных:
5
123.4
0.2
7.2
0.0
314 .1
Программа должна вывести сначала размер основного множества, а затем его минимальный элемент.
Пример выходных данных для приведённого выше примера входных данных:
3 7.2
(допускаются иные формулировки ответа не искажающие его смысла)
Основное множество состоит из всех скоростей, больших 1. Если же все скорости не превосходят 1. то множество состоит из одной частицы, имеющей максимальную скорость.
Программа читает все входные данные один раз. не запоминая все входные данные в массиве, размер которого равен N. При этом подсчитываются следующие величины:
- текущее количество В значений, которые превосходят 1;
- текущий минимум С среди этих значений;
- текущее максимальное значение M среди всех прочитанных чисел. Если в итоге количество чисел больших 1 положительно, то B выводится в качестве размера основного множества, затем выводится минимальное значение С. В противном случае в качестве размера основного множества выводится 1, в качестве значения минимума — число M.
Пример правильной и эффективной программы на языке Паскаль:
var n, i, В: longint;
а, М, С: real;
begin
readl.n(n) ;
В := 0;
М := 0;
С := 200000;
for i := 1 to n do begin
readln(a);
if a > M then
M := a;
if a > 1 then begin
В := В + 1;
if a < С then С := a;
end;
end;
if В = 0 then
writeln(1,' ', M)
else
writeln(B, ' ', C);
end.
Пример правильной н эффективной программы на языке Бейсик:
INPUT n
M = 0
B = 0
C = 100001
FOR i = 1 ТО n
INPUT А
IF а > M
THEN M = а
IF А > 1
THEN В = В + 1
IF А < С THEN С = a
ENDIF
NEXT i
IF В = 0 THEN
PRINT 1, М
ELSE
PRINT В, С
END IF
END