Радиотелескоп пытается получать и анализировать сигналы, поступающие из различных участков космоса, при этом различные шумы переводятся в последовательность вещественных неотрицательных чисел, заданных с точностью до одного знака после десятичной точки. Чисел может быть очень много, но не может быть меньше трёх. Все числа не превосходят 1000000.
В последовательности чисел, полученных из одного участка, выделяется основное подмножество элементов. Это такое непустое подмножество элементов, для которого произведение соответствующих чисел является максимально возможным. Если таких подмножеств несколько, то из них выбирается подмножество, которое содержит наименьшее количество элементов. Основное подмножество может содержать, например, как все элементы последовательности чисел, так и ровно один элемент. Если множество чисел содержит только одно число х, то произведением элементов этого множества считается число х.
Напишите программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет обрабатывать результаты, приходящие из одного участка, находя количество элементов в основном множестве и значение минимального элемента в этом множестве. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество сигналов N. В каждой из последующих N строк записано одно неотрицательное вещественное число с точностью до одного знака после десятичной точки.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание — 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве. Перед программой укажите версию языка программирования.
Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А — 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т. е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, — 3 балла.
Напоминаем! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Пример входных данных:
6
123.4
0.2
200.2
0.0
6.7
218.0
Программа должна вывести в одной строке сначала количество элементов в основном множестве, а затем — его минимальный элемент.
Пример выходных данных для приведённого выше примера входных данных: 4 6.7.
Включим во множество все числа, большие единицы. С добавлением каждого нового такого числа произведение будет лишь увеличиваться. Добавлять числа, меньшие единицы, не следует, потому что из-за них произведение будет уменьшаться. Добавлять числа, равные единице, не стоит, потому что на произведение такие числа никак не повлияют, а количество чисел во множестве увеличат, что по условию нам совсем не нужно. Таким образом, выведем количество чисел, больших единицы, и минимальное из таких чисел.
Требуется отдельно рассмотреть случай, когда в исходных данных нет чисел, превышающих единицу. В этом случае нужно включить во множество одно число – самое большое из данных. Больше к нему чисел брать нельзя, потому что от добавления новых чисел произведение будет лишь уменьшаться.
Ниже приведён код решения на языке Pascal версии 2.6.2.
var n, i, cntBig : longint;
cur, minBig, maxLit : real;
begin
maxLit:=0;
cntBig:=0;
minBig := high(longint);
readln(n);
for i := 1 to n do
begin
readln(cur);
if cur > 1 then
begin
inc(cntBig);
if cur < minBig then
minBig := cur;
end else if cur > maxLit then
maxLit := cur;
end;
if cntBig > 0 then
write(cntBig, ' ', minBig :1:1) else
write('1 ', maxLit :1:1);
end.
Пример решения задачи А на языке Паскаль.
vara: array[1..10000] of real; {исходные данные}
N: integer; {количество элементов}
min: real; {минимальный элемент подмножества}
count: integer; {количество элементов в подмножестве}
i: integer;
begin
readln(N);
min := 1000001;
count := 0;
for i := 1 to N do readln(a[i]);
for i := 1 to N do begin
if a[i] > 1 then count := count + 1;
if (a[i] < min) and (a[i]>1) then min := a[i];
end;
write(count, ' ', min);
end.
Приводим эффективное решение Николая Артюхина на C++.
#include <iostream>
using namespace std;
int main()
{
int i, n, k=0;
double x,max=-1, min=1000001;
cin >> n;
for(i=0;i < n;i++){
cin >> x;
if ((x<=1)&&(x>max)) max=x;
if (x>1){
if(x< min) {
min=x;
}
k++;
}
}
if (k>0) cout << k << " " << min;
if (k==0) cout << "1" << " " << max;
return 0;
}