Главное меню портала
• О портале
• Архив задач
• Карта архива задач
• Результаты тестов
• Ошибки тестирования
• Преподаватели
• Библиотечка
Рейтинг у учителя
• Рейтинг на портале
Начинающему
• Работа с порталом
• Курс для начинающего
• Архив задач начинающего
Олимпиаднику
• Архив задач олимпиадника
Олимпиады
Дистанционные олимпиады
• Положение олимпиады
Новое сообщениеОтправленые
Загрузка...
Время на прохождение теста: 3 секунд(а/ы).
Имя входного файла: in.txt
Имя выходного файла: out.txt

Автор: Бельский Андрей Владимирович

Березки
В одной далекой стране министерство природных ресурсов и охраны окружающей среды заинтересовалось проблемой «неровности» березок в главном национальном заповеднике. 

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

Данные специалисты имеют хорошую математическую подготовку и знают, как решать эту задачу. Им известны все высоты березок в заповеднике: x1, x2, …, xn. Назовем математическим ожиданием M среднее арифметическое всех высот, которое вычисляется по формуле M = (x1 + x2 + … + xn)/n, где n – количество березок. 

Линейным отклонением i-й березки от математического ожидания назовем величину Li, которая вычисляется по формуле Li = |xi – M|. Квадратичным отклонением назовем величину Si, которая вычисляется по формуле Si = Li2. Дисперсией всех березок назовем величину D, которая вычисляется по формуле D = (S1 + S2 + … + Sn) / (n – 1). Средним квадратичным отклонением назовем величину σ = √D. 

Специалисты из комитета по метрологии, стандартизации и сертификации знают, что если линейное отклонение березки не превышает утроенного значения среднего квадратичного отклонения, то такую березку можно не вырубать. Установили, что точность данного критерия составляет 0.001. Поэтому если превышение меньше 0.001, то данным различием можно пренебречь. 

Было решено произвести вырубку всех березок, которые не соответствуют заданному критерию. Ваша задача определить номера березок, которые останутся после вырубки.
Входные данные:
Данные читаются из файла с именем in.txt

Первая строка файла содержит целое число N – количество березок в заповеднике. 

Во второй строке файла через пробел расположено N действительных чисел x1, x2, …, xn.


Ограничения. 2 ≤ N ≤ 100 000, 1 ≤ xi ≤ 1000 – действительные числа.
Выходные данные:
В файл out.txt в единственную строку вывести номера березок, которые останутся после вырубки. Номера березок идут в порядке возрастания и разделяются единственным пробелом.

Примеры:
in.txt out.txt
1 11
2 1 1 1 1 1 1 1 1 1 1
2 3 4 5 6 7 8 9 10 11

Сложность задачи: 15%



Проверку могут осуществлять только зарегистрированные пользователи!


Разбор задачи
Сложность задачи заключается лишь в том, чтобы правильно понять, как определить, что березку следует срубить. 

Опишем этапы решения данной задачи: 

1. Находим среднее арифметическое всех значений высот M = (x1 + x2 + … + xn)/n. 
2. Далее в одном цикле находим линейные и квадратичные отклонения, а так же дисперсию по формулам: 
• Li = |xi – M| 
• Si = Li2 
• D = (S1 + S2 + … + Sn) / (n – 1) 
3. Зная дисперсию, находим среднее квадратичное отклонение σ =√D
4. Далее в цикле сравниваем модуль разности Li и 3σ с величиной 0.001, как сказано в условии. (в статистике это называется правило трех сигм) 
5. В цикле, указанном в пункте 4, необходимо так же выводить номера березок, для которых величина Li - 3σ оказалась меньше 0.001 

Номера березок, выведенные в пункте 5, и будут ответом задачи.
Показать обсуждение


На сайте гостей 22, зарегистрированных 0:
Сейчас онлайн только гости...
[Данные за последние 5 минут]