Задача 3 (Е %%6.2.7) (ОМ)
Задачу добавил: elena
Успешно сдано решений: 10
Преобразовать одномерный числовой массив по следующему правилу. Массив
просматривается с начала, и каждый элемент анализируется: если он не отличается от
своего соседа слева более чем на K%, он остается на месте. В противном случае
начинается поиск среди следующих за ним элементов массива, удовлетворяющих
описанному выше условию. Если подходящий элемент существует, он ставится на место
анализируемого, а фрагмент массива (начиная с анализируемого элемента) сдвигается
вправо. После этого анализ продолжается со следующего (по номеру) элемента. Если же
подходящего элемента нет, то анализ также начинается заново - и также со следующего
элемента. Подсчитать также
количество фрагментов результирующего массива длиной не менее 2 элементов,
удовлетворяющих «правилу K%» ("подфрагменты" не учитываются).
Ограничения: длина исходного массива 0<=N<=5000
Замечание: отличие в процентах вычисляется так: (<анализируемый элемент>–<соседний
слева элемент>)/<анализируемый элемент> * 100%
Формат входного файла input.txt
Первая строка – целые числа N – длина массива и K – процент «допустимых
расхождений»
Вторая строка – собственно массив – вещественные числа через пробел
Формат выходного файла output.txt
Первая строка – количество фрагментов полученного массива, удовлетворяющих правилу K%
Вторая строка – преобразованный массив – вещественные числа с точностью до 2 знаков
после запятой через пробел
Пример входного файла
10 20
2.5 5.2 4.1 7 -8.2 34.2 7.1 2.4 4.32 4.12
Пример выходного файла
3
2.50 2.40 5.20 4.10 4.32 4.12 7.00 7.10 -8.20 34.20