Информатика · тема кодификатора ФИПИ Программирование
задание 27: обработка больших данных
Два файла: маленький тестовый и большой рабочий. Нужен алгоритм, который справится с большим объёмом за разумное время. Полный балл берут около 14% сдающих.
- Первичных баллов
- 2
- Тема кодификатора
- Программирование
- Доля варианта
- 7%
Разбор на примере
Почему решение перебором всех пар не подходит для файла из миллиона чисел?
Ответ квадратичная сложность
Перебор пар даёт порядка 10¹² операций. Задание построено так, что наивное решение проходит на тестовом файле и не проходит на рабочем.
Где здесь теряют балл
Мы размечаем каждую ошибку не только темой, но и причиной. В этом задании встречаются такие:
-
не узнал правило в задании
Пишут рабочий перебор и сдают ответ по маленькому файлу для обоих. Алгоритм верный, но на большом файле не отрабатывает, и второй балл теряется.
-
слишком долго решал
Задание последнее и самое объёмное, около 40 минут по нормативу. Начинают его с остатком в четверть часа и не успевают отладить.
Проверь себя
Решить это задание в настоящем варианте
Задание 27 встречается в тренировочном варианте по информатике. Решишь целиком - увидишь, какие темы просели и по какой причине.
Решить вариант бесплатно Бесплатно · без карты