Космическое агентство производит эксперимент, в котором участвуют спутники «Птолемей-1» и «Птолемей-2». На спутнике «Птолемей-1» установлен прибор для измерения расстояния между спутниками. Каждую минуту прибор передаёт по каналу связи неотрицательное целое число – расстояние между спутниками в текущий момент в километрах.
Необходимо найти в заданной серии показаний прибора минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 8 минут. Если получить такое произведение не удаётся, ответ считается равным –1. Расстояние между спутниками не превышает 1000 км. Общее количество показаний прибора в серии не превышает 10 000.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 8. В каждой из следующих N строк задаётся одно неотрицательное целое число – очередное показание прибора.
Пример входных данных:
13
12
45
5
3
14
31
17
23
21
20
19
18
17
Программа должна вывести одно число – описанное в условии произведение, либо –1, если получить такое произведение не удаётся.
Пример выходных данных для приведённого выше примера входных данных:
54
Объяснение
Произведение будет четным, если хотя бы один из элементов четный. Пары, где оба элемента нечетные рассматривать не будем. Первые 8 элементов запишем в массив (mas). Теперь при вводе очередного значения мы будем рассматривать число, полученное 8 минут назад. Сравниваем его с минимальным элементом (min_number) и, если оно четное, то сравниваем его с минимальным четным элементом (min_even). Далее, если очередное значение (a) четное, то в переменную Multiplication записываем произведение a и min_number. Если же оно нечетное, то узнаем: были ли четные элементы раньше (сравниваем min_even с его начальным значением). Если были, то в переменную Multiplication записываем произведение a и min_even, в противном случае ничего не делаем. Теперь сравниваем Multiplication и минимальное произведение (min_comp) и заменяем рассматриваемое число в массиве на a. После выполнения цикла осталось только вывести результат (min_comp).
Решение на языке Pascal
Показать решение|
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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
const k = 8; valid_value = 1001; var mas: array [0..k - 1] of word; N: word; min_even: word; min_number: word; min_comp: longword; Multiplication: longword; a: word; c: word; begin min_even := valid_value; min_number := valid_value; Multiplication := valid_value * valid_value; min_comp := valid_value * valid_value; readln(N); for var i := 0 to k - 1 do readln(mas[i]); for var i := k to N - 1 do begin c := i mod k; readln(a); if mas[c] < min_number then min_number := mas[c]; if (mas[c] mod 2 = 0) and (mas[c] < min_even) then min_even := mas[c]; if a mod 2 = 0 then Multiplication := a * min_number else if min_even <> valid_value then Multiplication := a * min_even; if Multiplication < min_comp then min_comp := Multiplication; mas[c] := a; end; if min_comp = valid_value * valid_value then writeln(-1) else writeln(min_comp); end. |
Решение на языке Python
Показать решение|
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 28 29 30 31 32 33 34 35 36 37 |
k = 8 valid_value = 1001 c = 0 min_number = valid_value min_even = valid_value min_comp = valid_value * valid_value Multiplication = valid_value * valid_value N = int(input()) mas = [int(input()) for i in range(k)] for i in range(k, N): c = i % k a = int(input()) if mas[c] < min_number: min_number = mas[c] if mas[c] % 2 == 0 and mas[c] < min_even: min_even = mas[c] if a % 2 == 0: Multiplication = a * min_number elif min_even != valid_value: Multiplication = a * min_even if Multiplication < min_comp: min_comp = Multiplication mas[c] = a if min_comp == valid_value * valid_value: print(-1) else: print(min_comp) |
Похожие задачи: 8217