Задача B. 27-2 ≡

Входной файл:	Стандартный вход		Ограничение времени:	1 сек
Выходной файл:	Стандартный выход		Ограничение памяти:	256 Мб

Условие

По каналу связи передаётся последовательность положительных целых чисел Х₁, Х₂, ... все числа не превышают 1000, их количество заранее неизвестно. Каждое число передаётся в виде отдельной текстовой строки, содержащей десятичную запись числа. Признаком конца передаваемой последовательности является число 0.

 

Участок последовательности от элемента Х_T до элемента X_T+N называется подъёмом, если на этом участке каждое следующее число больше или равно предыдущему, причем участок нельзя расширить, т.е.

1) Т = 1 или Х_T-1 > Х_T

2) X_T+N — последний элемент последовательности или X_T+N > X_T+N+1. Высотой подъёма называется разность X_T+N − Х_T. Подъём считается значительным, если высота подъёма больше величины минимального элемента этого подъема.

 

Напишите программу, которая вычисляет количество значительных подъемов в заданной последовательности.

 

Программа должна вывести результаты в следующей форме:

 

Получено чисел: ...

Найдено значительных подъемов: ...

 

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

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов.

Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе. Перед программой укажите версию языка программирования.

 

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

Обязательно укажите, что программа является решением задания А.

Максимальная оценка за выполнение задания А – 2 балла.

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Обязательно укажите, что программа является решением задания Б.

 

Перед текстом программы кратко опишите алгоритм решения задачи.

 

Пример входных данных:

 

144

17

21

27

3

7

9

11

25

0

э

 

Пример выходных данных для приведённого выше примера входных данных:

Получено чисел: 9

Найдено значительных подъемов: 1

---