Элективный курс
«Олимпиадная информатика»
Программа 1. «Олимпиадная информатика» для учащихся 5-6 классов
Программа 2. «Олимпиадная информатика» для учащихся 7-8 классов
Программа 3. «Олимпиадная информатика» для учащихся 9-11 классов
Разработчик: Ярошевская Вера Ивановна
г. Москва 2016 г.
Программа содержат:
Пояснительную записку;
Методических указания по изучению тем;
Учебно-тематический план и программы подготовки к олимпиадам по информатике.
Электронные учебные материалы
Пояснительная записка.
Важной задачей образования является работа с одаренными учащимися, их подготовка к предметным олимпиадам. Олимпиада по информатике занимает одно из ведущих мест, в связи с интенсивным развитием информационных технологий как в нашей стране, так и за рубежом.
Участие в олимпиадах позволяет развивать творческие способности школьников и обеспечивает высокую мотивацию к образовательной деятельности.
Классическая олимпиада по информатике - это олимпиада по программированию, которая предполагает наличие обширных познаний в математике и языках программирования.
Решение олимпиадных задач позволяет раскрыть творческий потенциал школьника во время подготовки к олимпиаде, учитывая возрастные особенности ребенка и перспективу его развития. Использование многоуровневых олимпиадных задач, позволяет школьникам применить свой творческий потенциал, независимо от уровня подготовки.
Курс занятий по Олимпиадной информатике (решение олимпиадных задач по информатике) ориентирован на учащихся 5-11х классов, обладающих повышенной мотивацией к изучению информатики и имеющих начальные знания в области алгоритмизации на уровне понимания простейших алгоритмов.
Данный элективный курс позволяет провести непрерывную подготовку к олимпиадам по информатике начиная с 5-го класса, используя методическую коллекцию олимпиадных задач. В курсе использован системный подход при разработке модулей непрерывной подготовки одаренных детей к олимпиадам по информатике.
Основная цель курса: раскрыть значение программирования и суть профессии программиста, ознакомление учащихся со средой и основами программирования на языке PascalABC.NET, подготовить учащихся к практическому использованию полученных знаний при решении учебных задач, а затем профессиональной деятельности, вовлечение учащихся в участие в олимпиадах по программированию разного уровня.
Основные задачи курса: развитие навыков программирования алгоритмических структур; развитие логического мышления учащихся; развитие интеллекта учащихся.
Данная программа представляет большую практическую значимость с точки зрения совершенствования непрерывной работы с одаренными школьниками в рамках олимпиадного движения по информатике и школьного образования.
Методические указания по изучению тем
Олимпиадные задачи по информатике охватывают следующие ключевые разделы:
1. Математические основы информатики.
Этот раздел является фундаментальной основой информатики. В олимпиадах по информатике это особенно важно, так как школьникам сложно достичь успешности на олимпиадных состязаниях без хорошей подготовки в области теории множеств, логики, теории графов и комбинаторики.
Для успешного выступления на олимпиаде по информатике школьники должны
знать/понимать:
основы терминологии функций, отношений и множеств;
перестановки, размещения и сочетания множества;
формальные методы символической логики высказываний
основы построения рекуррентных соотношений;
основные методы доказательств;
основы теории чисел;
уметь:
выполнять операции, связанные с множествами, функциями и отношениями;
вычислять перестановки, размещения и сочетания множества, а также интерпретировать их значения в контексте конкретной задачи;
решать типичные рекуррентные соотношения;
осуществлять формальные логические доказательства и логическое рассуждение для моделирования алгоритмов;
определять, какой вид доказательства лучше подходит для решения конкретной задачи;
использовать основные алгоритмы теории чисел;
1. Отношения, функции и множества.
2. Основные геометрические понятия.
3. Основы логики.
4. Основы вычислений.
5. Методы доказательства.
6. Основы теории чисел.
7. Основы алгебры.
8. Основы комбинаторики.
9. Теорию графов.
10. Основы теории вероятностей.
11. Основы теории игр.
2. Разработка и анализ алгоритмов.
В этом разделе определяется основная способность учащихся знать классы алгоритмов, которые предназначены для решения определенного набора известных задач, понимать их сильных и слабых сторон, применять различные алгоритмы в заданном контексте с оценкой его эффективности.
элементы теории алгоритмов;
основные структуры данных;
основные понятия теории графов, а также их свойства и некоторые специальные случаи;
связь графов и деревьев со структурами данных, алгоритмами и вычислениями;
свойства, присущие «хорошим» алгоритмам;
вычислительную сложность основных алгоритмов сортировки, поиска;
понятие рекурсии и общую постановку рекурсивно-определенной задачи;
простые численные алгоритмы;
основные комбинаторные алгоритмы;
основные алгоритмы вычислительной геометрии;
наиболее распространенные алгоритмы сортировки;
наиболее важные алгоритмы на строках;
фундаментальные алгоритмы на графах: поиск в глубину и в ширину, нахождение кратчайших путей от одного источника и
основы динамического программирования;
основные положения теории игр;
уметь:
выбирать подходящие структуры данных для решения задач;
использовать вышеназванные алгоритмы в процессе решения задач;
определять сложность по времени и памяти алгоритмов;
определять вычислительную сложность основных алгоритмов сортировки, поиска;
реализовывать рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Алгоритмы и их свойства.
2. Структуры данных
3. Основы анализа алгоритмов.
4. Алгоритмические стратегии.
5. Рекурсия.
6. Фундаментальные вычислительные алгоритмы.
7. Числовые алгоритмы.
8. Алгоритмы на строках.
9. Алгоритмы на графах.
10. Динамическое программирование.
11. Алгоритмы теории игр.
3. Основы программирования.
В этом разделе закладывается условие успешного выступления учащихся на олимпиадах по информатике. Данный раздел включает в себя материал по фундаментальным концепциям программирования, основным структурам данных и алгоритмам, а также собственно языки программирования.
В рамках этого раздела школьники должны знать/понимать:
основные конструкции программирования;
концепцию типа данных как множества значений и операций над ними;
основные типы данных;
основные структуры данных: массивы, записи, строки, связные списки, стек;
представление данных в памяти;
альтернативные представления структур данных с точки зрения производительности;
основы ввода/вывода;
операторы, функции и передача параметров;
статическое, автоматическое и динамическое выделение памяти;
управление памятью во время исполнения программы;
методы реализации стеков, очередей;
методы реализации графов и деревьев;
механизм передачи параметров;
особенности реализации рекурсивных решений;
стратегии, полезные при отладке программ;
уметь:
анализировать и объяснить поведение простых программ, включающих фундаментальные конструкции;
модифицировать и расширить короткие программы, использующие стандартные условные и итеративные операторы и функции;
разработать, реализовать, протестировать и отладить программу, которая использовать все наиболее важные конструкции программирования;
применять методы структурной (функциональной) декомпозиции для разделения программы на части;
реализовать основные структуры данных на языке высокого уровня;
реализовать, протестировать и отладить рекурсивные функции и процедуры;
использовать при решении практических задач вышеназванные знания и умения и уверенно программировать на олимпиадах по информатике на языке программирования Pascal.
Основными темами этого раздела являются:
1. Язык программирования Pascal.
2. Основные конструкции программирования.
3. Переменные и типы данных.
4. Типы структур данных.
4. Методы вычислений и моделирование.
Раздел «Методы вычислений и моделирование» представляет область информатики, тесно связанную с вычислительной математикой и численными методами.
В рамках этого раздела школьники должны знать/понимать:
понятия ошибки, устойчивости, машинной точности и погрешности приближенных вычислений;
источники погрешности в приближенных вычислениях;
основные алгоритмы решения задач вычислительной математики: вычисление значения и корней функции; вычисление периметра, площади и объема, вычисление точки пересечения двух отрезков и др.;
понятия модели и моделирования, основные типы моделей;
компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени;
основные этапы и особенности построения и использования компьютерных моделей;
уметь:
вычислять оценку погрешности приближенных вычислений;
использовать при решении задач основные методы вычислительной математики;
формализовывать объекты моделирования;
разрабатывать компьютерные модели простейших объектов;
использовать при решении практических задач компьютерные модели в виде «черного ящика»;
использовать при решении практических задач вышеназванные знания и умения.
Основными темами этого раздела являются:
1. Основы вычислительной математики.
2. Введение в моделирование.
Учебно-тематическое планирование к программе «Олимпиадная информатика»
На основании выше сказанного составлены программы 1, 2 и 3, которые учитывают возрастные особенности учащихся.
Программа 1. Для учащихся 5-6 классов
| Тема | Количество часов |
| 1 |
|
| Типы олимпиадных задач по информатике для 5-6 классов. | 2 |
| Отношения (рефлексивность, симметричность, транзитивность, эквивалентность, лексикографический порядок) Точка, прямая, отрезок, вектор, угол Декартовы координаты в евклидовом пространстве Треугольник, прямоугольник, многоугольник Выпуклые многоугольники Основы логики Логические переменные, операции Таблицы истинности Булевы функции Основы вычислений Основы вычислений: Правила суммы и произведения Рекуррентные соотношения Методы доказательства Прямые доказательства Доказательство через контрпример Доказательство через противопоставление Основы теории чисел Простые числа. Деление с остатком Наибольший общий делитель Основы комбинаторики Перестановки, размещения и сочетания: Основные определения Теория графов Типы графов Маршруты и связность Деревья Остовные деревья Основы теории вероятностей Понятие вероятности Основы теории игр Понятие игры и результата игры Простейшие игры и стратегии | 20 |
| Этапы решения олимпиадной задачи: формализация условия задачи, выбор метода решения задачи. План разбора олимпиадной задачи по информатике. | 5 |
| Алгоритмы Алгоритмы и их свойства Понятие алгоритма Концепции и свойства алгоритмов Запись алгоритма на неформальном языке Структуры данных Простые базовые структуры Множества Последовательности Списки Неориентированные графы Алгоритмические стратегии Алгоритмы полного перебора Рекурсия Понятие рекурсии Простые численные алгоритмы Классические комбинаторные алгоритмы Алгоритмы с подмножествами: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего (прибавление и вычитание единицы) Алгоритмы с сочетаниями и перестановками: генерация, восстановление по номеру и построение номера, генерация следующего и предыдущего. Алгоритмы последовательного и бинарного поиска Числовые алгоритмы Разложение числа на простые множители Решето Эратосфена Алгоритм Евклида Алгоритмы на строках Поиск подстроки в строке. Наивный метод Алгоритмы на графах Вычисление длин кратчайших путей в дереве Обход графа в ширину и в глубину Способы реализации поиска в ширину (“наивный” и с очередью) Геометрические алгоритмы Алгоритмы определения совпадения точек, лучей, прямых и отрезков Решение / моделирование алгоритмических задач в среде Исполнителя | 20 |
| Введение в реальную среду программирования как инструмент реализации алгоритмов на компьютере Типовые инструменты среды программирования (режим помощь, режим редактирования, режим отладки) Среда программирования. Начало программирования. Языки программирования Переменные и типы данных Типы структур данных Особенности программирования фундаментальных алгоритмов. Введение в моделирование. Классификация языков программирования Процедурные языки Переменные, типы, выражения и присваивания Основы ввода/вывода Операторы проверки условия и цикла Концепция типа данных как множества значений и операций над ними Примитивные типы Массивы Стратегии решения задач Роль алгоритмов в процессе решения задач Среды программирования Понятия модели и моделирования Основные типы моделей www.olympiads.ru . | 20 |
Программа 2. Для учащихся 7-8 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 7-8 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Обратная функция, композиция Множества (дополнения, декартовы произведения) Основные геометрические понятия Евклидово расстояние Векторное и скалярное произведение на плоскости Основы логики Логические выражения Формы задания и синтез логических функций Преобразование логических выражений Основы вычислений Основы вычислений: Арифметические и геометрические прогрессии Числа Фибоначчи Методы доказательства Доказательство через противоречие Математическая индукция Основы теории чисел Основная теорема арифметики Взаимно простые числа Основы алгебры Многочлены и операции над ними. Решение квадратных уравнений. Теорема Виета Основы комбинаторики Тождество Паскаля Биномиальная теорема Теория графов Операции над графами Раскраска графов Эйлеровы и гамильтоновы графы Основы теории вероятностей Понятие математического ожидания. | 20 |
| Алгоритмы Алгоритмы и их свойства Ориентированные графы Деревья Основы анализа алгоритмов Стандартные классы сложности Асимптотический анализ поведения алгоритмов в среднем и крайних случаях Алгоритмические стратегии "Жадные" алгоритмы Рекурсия Рекурсивные математические функции Простые рекурсивные процедуры Реализация рекурсии Фундаментальные вычислительные алгоритмы Квадратичные методы сортировки (сортировка методом выбора, сортировка вставками) Сортировка подсчетом за линейное время. Алгоритмы сортировки за время (быстрая сортировка, пирамидальная сортировка Алгоритмы на строках Проверка графа на связность Алгоритмы поиска кратчайшего пути во взвешенных графах Основная идея динамического программирования. Рекурсивная реализация и развертывание в цикл. Задачи с монотонным направлением движения в таблице Задача о рюкзаке - решение методом динамического программирования Геометрические алгоритмы Представление точек, прямых и отрезков на плоскости | 20 |
| Среда программирования . Языки программирования Переменные и типы данных Типы структур данных Механизмы абстракции. Особенности программирования фундаментальных алгоритмов. Основы синтаксиса и семантики языков высокого уровня
Функции и передача параметров Свойства объявлений (связывание, область видимости, блоки и время жизни) Обзор проверки типов Записи Стратегии выбора подходящей структуры данных Процедуры, функции и итераторы как механизмы абстракции Модули в языках программирования Стратегии реализации алгоритмов Реализация рекурсии Введение в моделирование. Компоненты компьютерной модели и способы их описания: входные и выходные переменные, переменные состояния, функции перехода и выхода, функция продвижения времени Основные этапы и особенности построения компьютерных моделей Основные этапы использования компьютерных моделей при решении практических задач Типовые примеры решения задач по разделам из коллекции www.olympiads.ru | 25 |
Программа 3. Для учащихся 9-11 классов
| Тема | Количество часов |
| Положение о Всероссийской олимпиаде школьников. Методические рекомендации по проведению школьного, муниципального и регионального этапов Всероссийской олимпиады школьников по информатике. | 1 |
| Типы олимпиадных задач по информатике для 9-11 классов. | 2 |
| Основные разделы математической информатики. Функции, отношения и множества Вполне упорядоченные множества Мощность и счетность Основы логики Минимизация булевых функций Основные законы логики суждений Логика предикатов Основы вычислений Основы вычислений: Принцип включения-выключения Матрицы и действия над ними Методы доказательства Структура формальных доказательств Основы теории чисел Кольцо вычетов по модулю Основы алгебры Симметрические многочлены Понятие группы Свойства групп Теоремы о гомоморфизме и изоморфизме Основы комбинаторики Коды Грея: подмножества, сочетания, перестановки Таблицы инверсий перестановок Разбиения на подмножества. Числа Стирлинга Скобочные последовательности Теория графов Покрытия и независимость Укладка графов. Плоские (планарные) графы Двусвязность графа. Мосты, блоки, точки сочленения Связь ориентированных ациклических графов и отношений порядка. Транзитивное замыкание Двудольные графы Потоки и сети Основы теории вероятностей Аксиомы теории вероятностей Формула полной вероятности и формула Байеса. Условное математическое ожидание Основы теории игр Игры на матрицах | 20 |
| Алгоритмы Алгоритмы и их свойства Пирамида и дерево отрезков Сбалансированные деревья Хэш-таблицы и ассоциативные массивы Бор Основы анализа алгоритмов Компромисс между временем и объемом памяти в алгоритмах Использование рекуррентных отношений для анализа рекурсивных алгоритмов NP-полнота Алгоритмические стратегии Алгоритмы "разделяй и властвуй" Перебор с возвратом Эвристики Рекурсия Стратегия "разделяй и властвуй" Рекурсивный перебор с возвратами Фундаментальные вычислительные алгоритмы Алгоритмы сортировки ( сортировка слиянием) Цифровая сортировка Алгоритм вычисления номера слова в лексикографически упорядоченном множестве перестановок его символов Арифметика многоразрядных целых чисел Числовые алгоритмы Расширенный алгоритм Евклида. Способы реализации алгоритма без деления Решение линейных сравнений с помощью алгоритма Евклида Эффективная проверка числа на простоту Быстрые алгоритмы разложения чисел на простые множители. Алгоритмы на строках Алгоритмы поиска подстроки в строке за Периодические и циклические строки Алгоритм поиска нескольких подстрок за линейное время Алгоритмы на графах Топологическая сортировка графа, нахождение компонент сильной связности и построение диаграммы порядка Циклы отрицательной длины - критерий наличия, поиск Задача о синхронизации времени и задача о системе неравенств Алгоритм поиска эйлерова цикла (в том числе лексикографически минимального) Нахождение транзитивного замыкания графа Алгоритмы нахождения взвешенных остовных деревьев Алгоритмы отыскания компонент двусвязности, точек сочленения, мостов с помощью поиска в глубину Алгоритм нахождения максимального паросочетания и минимального вершинного покрытия в двудольном графе Поиск максимального потока в сети Динамическое программирование Оптимизация решения задачи динамического программирования на примере задачи о рюкзаке (исключение лишних параметров) Восстановление решения в задачах динамического программирования Общая схема решения задач динамического Алгоритмы теории игр Динамическое программирование и полный перебор как методы решения игровых задач. Игры на ациклическом графе Оценка позиций. Альфа-бета отсечение Геометрические алгоритмы Нахождение расстояний между объектами на плоскости Алгоритмы определения пересечения отрезков на плоскости Алгоритмы вычисления площади многоугольника с заданными координатами вершин. Случай целочисленной решетки (формула Пика) Алгоритмы построения выпуклой оболочки (алгоритмы Грэхема и Джарвиса) Окружности на плоскости, пересечение их с другими геометрическими объектами Эффективный алгоритм нахождения пары ближайших точек на плоскости | 20 |
| Среда программирования. Языки программирования Основные конструкции программирования Типы структур данных Особенности программирования фундаментальных алгоритмов. Программные средства и окружения. Проверка соответствия программного обеспечения. Формальные методы описания синтаксиса: Объектно-ориентированные языки Структурная декомпозиция Представление данных в памяти Статическое, автоматическое и динамическое выделение памяти Связанные структуры Методы реализации стеков, очередей и хэш-таблиц Методы реализации графов и деревьев Стратегии отладки Инструментальные средства тестирования Основы тестирования, включая создание тестового плана и генерацию тестов Тестирование методом "черного ящика" и "белого ящика" Тестирование элементов, интеграционное, системное тестирование и проверка соответствия Основы вычислительной математики. Основные методы вычислительной математики
Вычисление функций с шагом. Метод сеток Арифметика с плавающей точкой Ошибка, устойчивость, сходимость Типовые примеры решения задач по разделам из коллекции www.olympiads.ru . | 25 |
Диагностические задания
В качестве диагностических заданий используются представленные ниже типы олимпиадных задач и требуется провести их методический разбор.
Анализ всех задач, предлагавшихся на олимпиадах по информатике, позволил выделить следующие темы, тесно связанные с соответствующими разделами информатики и прикладной математики:
1) комбинаторика;
2) сортировка и поиск;
3) обработка последовательностей;
4) перебор вариантов и методы его сокращения;
5) алгоритмы на графах;
6) динамическое программирование;
7) элементы вычислительной геометрии;
8) задачи на технику программирования;
9) задачи на идею.
Методические указание для изучения
Алгоритмическая компьютерная среда
Набор задач по нескольким уровням сложности
Разные типы алгоритмических заданий (перестановки, переливания, взвешивания, переправы, переезды, работа с числами) (Виртуальные Лаборатории по информатике)
Алгоритмы на координатной плоскости (управление перемещением с условиями)
система автоматической проверки решений и оценивания
/ video / kuris . php
Адрес ресурса: http://school-collection.edu.ru , раздел «Информатика», 2-6 классы, выбрать «Интерактивный задачник по информатике для 2-6 классов»
Методическое пособие и 100 алгоритмических задач http :// lbz . ru / books /264/5211
Виртуальные лаборатории по информатике в начальной школе: методическое пособие Авторы: Цветкова М. С., Курис Г. Э.
Коллекции олимпиадных задач с 1989 по 2016 год и методические материалы к ним представлены на сайтах:
http://old.info.rosolymp.ru/
Представлены интернет-ресурсы олимпиадной информатики:
1. Интернет-ресурсы для теоретической подготовки к олимпиадам:
http://www.intuit.ru/courses.html (сайт Интернет-университета информационных технологий);
http://www.olympiads.ru/sng/index.shtml (сайт МИОО, МЦНМО, и оргкомитета Московской олимпиады по информатике для проведения дистанционных семинаров по подготовке к олимпиадам по информатике);
http://vzshit.net.ru/ (сайт Всесибирской заочной школы информационных технологий).
2. Интернет-ресурсы с коллекциями олимпиадных задач:
http://old.info.rosolymp.ru (сайт с самой большой в России коллекцией задач международных и всероссийских олимпиад по информатике с методическими рекомендациями по их решению);
http://www.olympiads.ru/moscow/index.shtml (сайт московских олимпиад по информатике);
http://neerc.ifmo.ru/school/russia-team/archive.html (сайт с архивом задач Всероссийских командных олимпиад школьников по программированию);
http://contest.ur.ru (сайт Уральских олимпиад по информатике );
http://www.olympiads.ru/ (сайт по олимпиадной информатике);
http://olimpic.nsu.ru/nsu/ (сайт открытой Всесибирской олимпиады по программированию им. И.В. Поттосина).
3. Интернет-ресурсы с коллекциями олимпиадных задач и возможностью их тестирования в реальном масштабе времени:
http://acm.timus.ru/ (сайт Уральского государственного университета, содержащий большой архив задач с различных соревнований по спортивному программированию);
http://acm.sgu.ru (сайт Саратовского государственного университета, содержащий архив задач с системой онлайн-проверки).
4. Сайты интернет-олимпиад для школьников:
http://info-online.rusolimp.ru/ (сайт интернет-туров заключительного этапа Всероссийской олимпиады школьников по информатике);
http://olymp.ifmo.ru/ (сайт городских интернет - олимпиад школьников Санкт-Петербурга);
http://neerc.ifmo.ru/school/io/index.html (сайт интернет-олимпиад по информатике, проводимых жюри Всероссийской командной олимпиады школьников по программированию);
http://www.olympiads.ru/online/index.shtml (сайт московских онлайн-олимпиад);
http://olimpic.nsu.ru/acmSchool/archive/2006-2007/train2006/index.shtml (сайт тренировочных олимпиад школьников, поддерживаемый Новосибирским государственным университетом).
Список литературы
1. Алексеев А. В., Беляев С. Н. Подготовка школьников к олимпиадам по информатике с использованием веб-сайта: учеб.-метод. пособие для учащихся 7-11 классов. Ханты-Мансийск: РИО ИРО, 2008. 284 с.
2. Волчёнков С. Г., Корнилов П. А., Белов Ю. А. и др. Ярославские олимпиады по информатике. Сборник задач с решениями. М.: БИНОМ. Лаборатория знаний. 2010. 405 с.
3. Долинский М. С. Алгоритмизация и программирование на TurboPascal: от простых до олимпиадных задач: учеб.пособие. СПб.: Питер Принт, 2004. 240 с.
4. Иванов С. Ю., Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике: от простого к сложному // Информатика и образование. 2006. № 10. С. 21-32.
5. Кирюхин В. М. Всероссийская олимпиада школьников по информатике. М.: АПК и ППРО, 2005. 212 с.
6. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 2. М.: Просвещение, 2009. 222 с. (Пять колец).
7. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 3. М.: Просвещение, 2011. 222 с. (Пять колец).
8. Кирюхин В. М. Информатика. Международные олимпиады. Вып. 1. М.: Просвещение, 2009. 239 с. (Пять колец).
9. Кирюхин В. М., Лапунов А. В., Окулов С. М. Задачи по информатике. Международные олимпиады 1989-1996 гг. М.: ABF, 1996. 272 с.
10. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 4. С. 42-54.
11. Кирюхин В. М., Окулов С. М. Методика анализа сложных задач по информатике // Информатика и образование. 2006. № 5. С. 29-41.
12. Кирюхин В. М., Окулов С. М. Методика решения задач по информатике. Международные олимпиады. М.: БИНОМ. Лаборатория знаний, 2007. 600 с.
13. Кирюхин В. М., Цветкова М. С. Всероссийская олимпиада школьников по информатике в 2006 году. М.: АПК и ППРО, 2006. 152 с.
14. Кирюхин В. М., Цветкова М. С. Методическое обеспечение олимпиадной информатики в школе / Сб. трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 193-195
15. Кирюхин В. М. Информатика. Всероссийские олимпиады. Вып. 1. М.: Просвещение, 2008. 220 с. (Пять колец).
16. Меньшиков Ф. В. Олимпиадные задачи по программированию. СПб.: Питер, 2006. 315 с.
17. Московские олимпиады по информатике. 2002-2009 / под ред. Е. В. Андреевой, В. М. Гуровица и В. А. Матюхина. М.: МЦНМО, 2009. 414 с.
18. Нижегородские городские олимпиады школьников по информатике / под ред. В. Д. Лелюха. Нижний Новгород: ИПФ РАН, 2010. 130 с.
19. Никулин Е. А. Компьютерная геометрия и алгоритмы машинной графики. СПб.: БХВ-Петербург, 2003. 560 с.
20. Окулов С. М. Основы программирования. М.: БИНОМ. Лаборатория знаний, 2005. 440 с.
21. Окулов С. М. Программирование в алгоритмах. М.: БИНОМ. Лаборатория знаний. 2002. 341 с.
22. Окулов С. М. Дискретная математика. Теория и практика решения задач по информатике: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 422 с.
23. Окулов С. М. Алгоритмы обработки строк: учеб.пособие. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.
24. Окулов С. М., Пестов А. А. 100 задач по информатике. Киров: Изд-во ВГПУ, 2000. 272 с.
25. Окулов С. М., Лялин А. В. Ханойские башни. М.: БИНОМ. Лаборатория знаний. 2008. 245 с. (Развитие интеллекта школьников).
26. Просветов Г. И. Дискретная математика: задачи и решения: учеб.пособие. М.: БИНОМ. Лаборатория знаний. 2008. 222 с.
27. Скиена С. С., Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям. М.: Кудиц-образ, 2005. 416 с.
28. Сулейманов Р. Р. Организация внеклассной работы в школьном клубе программистов: методическое пособие. М.: БИНОМ. Лаборатория знаний. 2010. 255 с.
29. Цветкова М. С. Система развивающего обучения как основа олимпиадного движения / Сборник трудов XVII конференции-выставки «Информационные технологии в образовании». Ч. III. М.: БИТ про, 2007. С. 205-207
30. Кирюхин В.М., Цветкова М.С. Образовательные программы по развитию одаренности у детей и подростков, составленные с учетом уровня подготовленности, направлений интересов, по направлению информационных технологий, 2012 .
Сайт Методического центра олимпиадной информатики:
http://metodist.lbz.ru/lections/6/
Портал Всероссийской олимпиады школьников:
http://www.rosolymp.ru/
Сайт с архивом олимпиадных задач:
http://old.rosolymp.ru/
Модуль поддержан видеолекциями членов Центральной предметно-методической комиссии на сайте
Олимпиады по информатике являются по сути своей олимпиадами по программированию. Решение олимпиадных задач представляет собой вполне самостоятельный учебный раздел с обширными теоретической и практической частями.
Шесть лет на базе школы-лицея №8 г.Сосновый Бор ведется подготовка школьников к олимпиадам различного уровня. В течение пяти лет учащиеся лицея являются победителями областных олимпиад по программированию, участниками и призерами Всероссийских олимпиад.
Решения олимпиадных задач практически всех этапов олимпиад, начиная с районного и заканчивая международным уровнем, базируются на вполне определенных алгоритмах, широко известных в математике и информатике. И чтобы успешно решать олимпиадные задачи, необходимо прежде всего освоить эти алгоритмы, увидеть их и умело применить в предлагаемых заданиях, а уж коли не знаешь, то суметь их придумать, изобрести. Но знакомство с этими алгоритмами чаще всего происходит только в вузе, и это вполне объяснимо, так как освоение этих алгоритмов требует знания некоторых разделов высшей математики.
Вопрос 1 . Так можно ли подготовить школьников к олимпиадам?
Можно, но только не в рамках базовой программы.
Притом, почти необходимое условие, чтобы эти школьники занимались дополнительно математикой (лучше, если это классы с углубленным изучением математики). Неслучайно наши Российские выдающиеся школьники в области информатики занимались столь же успешно и математикой:
Виктор Баргачев, 2-кратный абсолютный чемпион мира по информатике среди школьников, является призером Международной олимпиады по математике (серебряная медаль);
Николай Дуров, 4-кратный призер Международных олимпиад по информатике (3 серебряных и одна золотая медаль), является обладателем двух золотых медалей Международных олимпиад по математике;
Владимир Мартьянов из Нижнего Новгорода (2-кратный абсолютный чемпион мира по информатике) являлся победителем зональных Российских олимпиад по математике и физике.
По Ленинградской области можно привести для примера Стратонникова Алексея, Потапова Алексея, Ананьева Артема, Паньгина Андрея.
Вопрос 2 . С какого же возраста необходимо начинать готовить школьников?
Чем раньше, тем лучше, но в разумных пределах.
Для уровня
областных олимпиад достаточно начинать с 7 – 8 класса;
Российских олимпиад желательно начинать с 5 – 6 класса.
Пример: чемпион г.Москвы по программированию среди школьников 1998 года Петр Митричев – ученик 7 класса, он же явился самым молодым участником 9 Всероссийской олимпиады школьников по информатике и участником тренировочных сборов по подготовке команды России к Международной олимпиаде.
Вопрос 3 . В какой форме проводить занятия по подготовке к олимпиадам?
В виде факультативов или спецкурсов.
Для хорошей подготовки ученика, говоря известной фразой, важно, в первую очередь, ”не только наполнить чашу знаний, но и зажечь факел”. Иными словами – привить интерес!
По опыту нашего лицея этому способствует следующее:
Большую роль играют межпредметные связи.
В лицее ведется уже пять лет спецкурс «Математика на компьютерах» для 5–6 классов. Учащиеся знакомятся в наглядной форме с математическими понятиями (например, анимационной разверткой куба, координатной плоскостью с целочисленной сеткой), учатся творчески подходить к решению стандартных задач (например, с помощью графического представления на компьютере задач переливания и взвешивания).
Развитию интереса способствуют уроки по теме ”Моделирование движения” от простейшего движения бильярдного шара до сложной картины линий напряженности электрического поля двух зарядов. Особенно производит впечатление моделирование на компьютере «полета бумажного самолетика» и демонстрация этого полета наяву. Также интересна задача моделирования движения спутника и определение первой, второй космической скорости, времени полета ракеты “Восток” с Юрием Гагариным вокруг Земли (это событие должен знать каждый!).
Такие уроки проводятся дифференцированно по степени подготовленности учащихся.
Для 7 – 8 классов организуется в течение первых двух-трех недель летних каникул школьный лагерь «Интеллект», где ребята занимаются информатикой по специальной программе.
Например, программа «Лабиринт» включает темы:
построение лабиринта (интересный алгоритм генерации случайного лабиринта различной сложности);
передвижение по лабиринту с помощью управляющих клавиш;
поиск выхода из лабиринта, начиная с простейшего по правилу левой руки (придерживаясь одной стороны лабиринта);
поиск кратчайшего пути в лабиринте.
Эта программа дает толчок учащимся для разработки собственных игр «ходилок» и «стрелялок». Главное – осознание того, что они сами могут это создавать!
Для 10 классов организуется летняя производственная практика на различных предприятиях г.Сосновый Бор в течение одного месяца. Учащиеся приобретают навыки решения практических задач, закрепляют знания по работе с базами данных, бухгалтерскими офисными приложениями, самостоятельно создают программы по заданиям кураторов, приобретают дополнительные знания (например, при работе с компьютерными сетями, операционной системой Unix). Похвальный отзыв с предприятия – обычный результат такой работы.
Собственные программы ребята демонстрируют на традиционной школьной конференции по информатике «Мы и компьютер», в этом году была уже шестая конференция. Лучшие из программных разработок ребята ежегодно представляют на Международной конференции «Школьная информатика и проблемы устойчивого развития», проходящей в Санкт-Петербурге, где работы ребят оцениваются дипломами I и II степени.
Отдельные программы используются как учебный материал.
Для группы «компьютерных фанатов» в хорошем смысле, а не в смысле, например, компьютерных игр, ведутся специально направленные факультативы и спецкурсы по темам: изучение дополнительного языка программирования, алгоритмизация нестандартных задач, олимпиадные задачи, теория графов и т.п.
Вопрос 4 . Сколько человек должно быть на занятиях специально ориентированных факультативов?
Группы по 6 – 12 человек .
При работе на конкретный результат, (то есть подготовка к городской, областной или Российской олимпиаде), должна быть группа от 3 до 6 человек. Эти занятия уже представляют собой тренировки, и тут преподаватель больше выступает в роли тренера, а не учителя. Как проходит занятие?
Называется тема.
Перечисляются задачи на данную тему.
Выбирается одна из наиболее популярных или интересных задач.
Устно совместно с ребятами обсуждается алгоритм решения.
Ребята пишут программу, преподаватель фиксирует время, оценивает реализацию решений, помогает искать ошибки, указывает на недочеты по эффективности (количество операций, использование оперативной памяти, время решения).
Вопрос 5 . Какие темы необходимо изучать на занятиях по подготовке к олимпиадам?
Всего не предусмотреть, но можно выделить следующие группы алгоритмов:
Алгоритмы над целыми числами.
Рекурсия.
Сортировка.
Переборные задачи.
Геометрические задачи.
Численные методы.
Статистическое моделирование.
Графы и деревья.
Текстовые преобразования.
Рассмотрим более подробно темы, необходимые для изучения при подготовке к олимпиадам. Теоретические занятия должны включать в себя определения, утверждения (в некоторых случаях обязательно с доказательствами).
Алгоритмы над целыми числами
Делимость
При изучении этой темы необходимо дать определения делителя, кратного, простых и взаимно простых чисел, привести утверждения с доказательствами о делимости суммы и разности двух чисел, о делимости произведения.
Первая модификация алгоритма Евклида (с вычитанием)
Последовательно уменьшая числа (большее заменяя разностью чисел) до тех пор, пока они не станут равны, придем к наибольшему общему делителю этих чисел.
Задачи, которые необходимо разобрать при изучении данной темы:
Определить, являются ли несколько чисел взаимно простыми
Сократить дробь (числитель и знаменатель дроби вводятся)
Написать программу «Калькулятор» в простых дробях
Вторая модификация алгоритма Евклида, использующая деление с остатком
где r – остаток от деления большего числа на меньшее.
Таким образом, уменьшая числа, получим наибольший общий делитель как последний не равный нулю остаток.
Задача для решения : прямоугольник с длинами сторон a и b, где a и b – натуральные числа, разрезать на квадраты максимальной площади. Определить размер квадратов и их общее количество.
Диофантовы уравнения
Используя утверждение о представлении наибольшего общего делителя двух чисел в виде линейной комбинации этих чисел, приходим к утверждению о разрешимости в целых числах уравнения вида ax + by = c (диофантово уравнение).
Задачи , которые необходимо разобрать при изучении данной темы:
Задачи на размен денег монетами определенного достоинства.
Задачи на переливание.
При изучении алгоритма решения задачи на переливание представляется полезным использование вспомогательной демонстрационно-обучающей программы «Переливайка», с помощью которой учащиеся могут на практике применить изученный алгоритм. Необходимым является закрепление этого алгоритма для нахождения хотя бы одного решения диофантова уравнения. Затем дается общий алгоритм решения диофантова уравнения с формулами для нахождения всего множества решений.
Простые числа
С простыми числами связано множество олимпиадных задач разных уровней. Классический метод для нахождения простых чисел - решето Эратосфена. С этим алгоритмом связаны решения следующих задач :
Числа-близнецы;
Совершенные числа;
Скатерть Улама;
Дружественные числа и т.п.
«Длинная» арифметика
Задачи на «длинную» арифметику возникают тогда, когда в стандартных типах данных (целые или длинные целые) не представляется возможным хранить результат, настолько он велик. В этом случае используется прием хранения длинных чисел в виде массива цифр, а чтобы выполнять арифметические действия с такими числами, необходимо написать специальные процедуры сложения, умножения, деления длинных чисел.
Типовые задачи: найти число N! (N-факториал), определить период дроби.
Рекурсия
Почти в любой книге по программированию касаются рекурсии и рекурсивных процедур и функций. Но очень мало книг, где тема рекурсии разбиралась бы подробно. Традиционно начинается рассмотрение рекурсивной функции с нахождения факториала числа. Короткая функция в одну строчку, но непонятно, зачем считать факториал рекурсивно, если он и так считается элементарно просто в одном цикле с параметром.
Чем младше ученики, тем важнее для них принципы наглядности и простоты. Введение в рекурсию можно начинать с известной считалки про «10 негритят».
Следующий этап – рекурсивные рисунки. Начинаем с простейших рисунков, например, рисования упрощенной «матрешки».
снежинки, падающие по всему экрану;
веточки разного цвета, разной пушистости и разного размера (в длину ветки вносится случайная составляющая).
Большой интерес представляют для ребят фрактальные множества: салфетка и скатерть Серпинского, модель Мандельброта человеческого легкого, фрактал Хартера-Хейтуэя (известен нам как ломаная Дракона), кривые Гильберта, снежинка Коха. Рекурсия здесь настолько естественна, что ни у кого не возникает вопроса, можно ли без нее обойтись. И лишь теперь, когда прелесть и красота рекурсии не вызывает ни у кого сомнений, можно переходить к задачам, которые по своему определению являются рекурсивными. Это следующие задачи: факториал числа, N-я степень числа, НОД(a , b ), функция Аккермана, числа Фибоначчи, перевод чисел из 10-й системы счисления в 2-ю, нахождение максимума и минимума в массиве. Многие задачи, оказывается, можно делать с помощью рекурсии. Главное, что появляется видение рекурсии в задачах, ранее решенных не рекурсивно. С целью новизны, например, в задаче о разрезании прямоугольника на квадраты максимальной площади предлагается сделать наглядное графическое сопровождение с помощью рекурсии. И уж совсем «плохо» без рекурсии при решении таких задач, как «Ханойская башня». В данном случае осознать это и на практике освоить рекурсивный алгоритм решения данной задачи помогает демонстрационно-обучающая программа «Ханойская башня».
Сортировка
Без знаний алгоритмов сортировки никак нельзя спокойно чувствовать себя на олимпиадах различного уровня. Задачи могут формулироваться как явно с упоминанием алгоритма сортировки, так и подразумевая внутри решения использование алгоритма сортировки. Два простейших алгоритма, которые необходимо знать, - это «пузырек» и сортировка обменом (с помощью поиска последовательных минимумов). При небольших объемах данных вполне хватает этих двух методов, но при работе с данными, измеряемыми десятками и сотнями Кбайт, необходимо знание какой-нибудь из быстрых сортировок. Предпочтение можно отдать быстрой сортировке Хоара, которая реализуется рекурсивно. Необходимо также знать некоторые приемы при упорядочивании данных в больших файлах. Весь файл разбивается на некоторое количество кусков, которые можно отсортировать с помощью QSORT, а затем произвести слияние отсортированных файлов уже без программы сортировки (кстати, это очень полезная с технической точки зрения задача, требующая аккуратности и хорошей техники программирования).
Перебор вариантов
Задачи перебора составляют огромный класс олимпиадных задач. Начинается перебор с простейшего поиска минимума и максимума в одномерном массиве или поиска элемента с заданными свойствами. Далее идет перебор пар элементов, использующий вложенный цикл, затем перебор троек элементов, использующий тройной цикл (как, например, в задаче о поиске трех точек на плоскости среди заданных N точек, которые образуют треугольник с максимальной площадью). А если перебирать сочетания из 4, 5, 6 и т.д. элементов? Сколько же необходимо циклов? Оказывается, существуют алгоритмы, существенно сокращающие перебор.
Довольно длинный по времени выполнения, но один из самых универсальных алгоритмов перебора, - перебор с возвратом или «бектрекинг». Программируется рекурсивно. Лучше всего объясняется на следующих задачах:
Ходом коня обойти шахматную доску N*M;
Расставить 8 ферзей на шахматной доске размера 8*8 так, чтобы они не угрожали друг другу;
Найти выход из лабиринта и т.п.
Необходимо также объяснять учащимся, что в случае слишком долгого времени выполнения программы, необходимо ограничивать «бектрекинг». Например, в задаче про шахматы при размере доски 8*8 выполняется программа уже довольно долго. Можно и даже нужно применять симметрию, зеркальное отображение, выполняя задание для половины или четверти шахматной доски.
Классической задачей на «бектрекинг» является задача о «рюкзаке», затем можно рассматривать производные от этой задачи:
Разбить N чисел на два подмножества, наиболее близких по сумме;
Из заданного множества слов выбрать максимальную подпоследовательность слов в словарном порядке.
С перебором связаны и комбинаторные задачи. Следует освоить алгоритмы создания лексикографического упорядочения.
Задачи на геометрию
Обязательный минимум, который необходимо знать при решении задач на геометрию, включает в себя следующее:
Уметь привести уравнение прямой, проходящей через две точки к виду
Ax + By + C = 0;
Уметь определить, принадлежит ли точка прямой или отрезку;
Уметь определить, пересекаются ли две прямые, и, если пересекаются, то определить их точку пересечения (для этого вычислять определитель 2-го порядка);
Уметь написать уравнение перпендикулярной прямой или определить, перпендикулярна ли одна прямая другой (использование свойства о равенстве нулю скалярного произведения перпендикулярных векторов);
Уметь вычислять расстояние от точки до прямой.
В дополнение к этому для решения задач областного и Всероссийского уровня необходимы знания начального курса аналитической геометрии: скалярное и векторное произведение векторов, выражение их через координаты. Скалярное произведение используется для нахождения угла (или косинуса угла) при построении, например, выпуклой оболочки заданных точек. Векторное произведение двух векторов используется, во-первых, для вычисления площадей многоугольников, а во-вторых, для определения направления в соответствующих задачах. Эти знания необходимы также для того, чтобы решать такую классическую олимпиадную задачу, как содержится ли точка внутри произвольного многоугольника.
Необходимо обратить внимание учащихся на многозначность понятий, которые можно использовать в различных задачах. Например, для понятия векторное произведение
модуль численного значения определяет площадь параллелограмма, построенного на заданных векторах;
нулевое значение - параллельность векторов;
знак означает, что один вектор расположен «слева» или «справа» относительно другого;
результирующий вектор определяет нормаль к плоскости заданных векторов.
Численные методы
Метод дихотомии
Для поиска данных в упорядоченном множестве используется метод дихотомии (или деления пополам) с последующей проверкой искомых свойств. Этот метод, который более привычен для нахождения приближенных значений корней нелинейных уравнений, можно использовать для поиска среди «огромного» количества данных. В этом случае более употребим термин «бинарный поиск». Типовая задача – найти заданное слово в словаре.
В общем случае, данный метод является оптимальным.
Решение систем линейных уравнений: метод Крамера, метод Гаусса.
Классические методы. Обычно в задачах число уравнений не более трех. Но знание общего случая, вероятно, пригодится.
Задача с областной олимпиады 94 года.
Вводится в виде строчки уравнение химической реакции: необходимо уравнять, т.е. расставить коэффициенты.
Статистическое моделирование (метод Монте-Карло).
Очень полезным является знание данного метода:
для моделирования игровых вероятностных ситуаций (бросание монеты, кубика, блуждания). Именно «игровая» или связанная с чем-то знакомым (известным, «бытовым») формулировка задачи помогает в понимании метода, понятия вероятности. Можно предложить учащимся интересные задачи:
чего больше, сократимых или несократимых дробей? (Математическая формулировка: оценить вероятность того, что наудачу взятая дробь несократима);
лучшее пари для простаков («Квант» №5,1987);
комбинаторные задачи.
Для определения площадей фигур, когда затруднены аналитические решения.
Так, в задаче (областная олимпиада 99 года) по нахождению площади пересечения трех окружностей метод Монте-Карло можно использовать в качестве альтернативного прямому аналитическому методу, так как очень трудно вывести решение, используя тригонометрические соотношения. Наилучший путь - это «использовать геометрию» для анализа частных случаев (когда нет пересечения, когда пересечение в одной точке, одна окружность внутри другой), а метод Монте-Карло для общего случая.
Динамическое программирование.
Бывают случаи, когда невозможно решить задачу полным перебором вариантов из-за их огромного количества. Но если на каждом шаге задачу можно разбить на более простые и найти оптимальное решение для них, не рассматривая всех решений общей задачи, а затем найденные решения применить для следующих шагов, то это и означает, что в данном случае применим принцип динамического программирования.
Данный принцип легче всего воспринимается на конкретных задачах. Но объяснение его можно начать с занимательной истории про золотую лестницу Фараона (изложенную в журнале «Квант» №10, 1991 г.), а затем перейти к следующим задачам:
Классическая задача о нахождении такого кратчайшего пути в числовой матрице A размерности NхN из A(1,1) в A(n,n), в котором сумма цифр в клетках была минимальной или максимальной.
Нахождение общей подстроки максимальной длины (задача, возникшая из современной реальной задачи молекулярной биологии об общей генетической информации в молекулах ДНК).
Графы и деревья.
Очень важная тема. Практически ни одна олимпиада Российского уровня не обходится без использования какого-либо алгоритма на графах. Необходимо ввести понятие графа через вершины и ребра, понятие ориентированных или неориентированных графов, разобрать методы представления графов в виде матрицы, смежности, матрицы инциденций, списка связей.
Разобрать основные алгоритмы на графах:
поиск в глубину (иными словами “бектрекинг” или перебор с возвратом);
поиск в ширину (или метод заливки);
Алгоритм Дейкстра для поиска кратчайших путей в графе из заданной вершины во все остальные;
алгоритм Флойда для поиска кратчайших путей в графе между всеми парами вершин.
Текстовые преобразования
Задачи, в которых необходимо проводить разбор строки, порой дополнительно предполагают работу с файлами, графическими построениями (подобие команд текстового или графического редактора) или использование каких-либо приемов программирования (например, представление “стека” в виде символьной строки в задаче о правильном скобочном выражении для нескольких типов скобок).
Представлен широкий, но далеко не полный набор тем, охватываемых олимпиадными задачами. Во многом это зависит от пристрастий организаторов олимпиад различных уровней (теоретические туры, задачи с использованием игровых стратегий, прикладного «офисного» характера).
Вопрос 6 . Что можно посоветовать при решении задач на олимпиаде?
Предполагая, что теория алгоритмов «проштудирована» и основы программирования освоены, участнику соревнования можно посоветовать следующее:
Обеспечьте «про запас» определенный «гарантированный» (по вашему мнению) набор баллов на простых задачах. Это не означает, что сложные задачи оставлять на последний момент. При обдумывании их решения может быть найден «хороший» алгоритм, и успехом послужит соответственно большая доля баллов.
Если задача трудна для вас или дефицит времени для решения, запрограммируйте простые частные случаи (авось некоторые тесты пройдут), либо используйте какой-нибудь неоптимальный, например, переборный алгоритм.
Если для задачи указано ограничение по времени решения, а ваш переборный алгоритм не укладывается в это время, то вставьте в алгоритм таймер, который при приближении к критическому времени заканчивает задачу и выводит наилучший найденный переборный вариант (возможно, он будет правильным).
Немаловажен выбор алгоритмического языка, например, в Basic-программе легче работать с графикой, а у Pascal-программы - преимущество быстродействия.
Строго соблюдайте указанные в условии задачи форматы ввода-вывода: «автотестировщик» может неправильно воспринять лишний пробел, или исходные тесты содержат запятую там, где вы предусматривали во вводе своей задачи пробел (особенности операторов ввода Pascal и Basic).
В основном, любая программа имеет структуру:
Ввод данных
Расчетный блок
Вывод результата
Оформите и убедитесь, что ввод-вывод правильный (с возможным анализом ошибочных данных) прежде, чем программировать расчетный блок.
Поставьте ключи компилятора для обработки всевозможных ошибок (полезно при отладке), а перед сдачей задачи отключите эти опции (для игнорирования компилятором возможных ошибок тестирования, которые не сказываются на решении).
Проверьте задачу для заданных максимальных ограничений (например, если дано n 1000, проверьте для n = 1000). Следите за типом объявляемых переменных (предпочтительно для описания целочисленных переменных использовать тип «длинное целое»).
Разумно используйте апелляцию. Возможна двусмысленность понимания задачи. В жюри тоже люди, и вы можете отстоять свою позицию, убедить их добавить вам желанные баллы.
В крайнем случае, если вы «cool hacker» (крутой специалист по системной части), запустите программу «соседа», как свою (небось, никто не заметит).
Разрешается иметь свои шпаргалки (не в электронном виде) или воспользоваться «свободным» временем для изучения справочной литературы.
Некоторые из перечисленных советов являются «вредными», соответствуют принципам «авось, небось и как-нибудь». Просьба воспринимать их критически, но они жизненны.
Вопрос 7 . Какой литературой необходимо пользоваться при подготовке к олимпиадам?
А.Шень. Программирование: теоремы и задачи, М. МЦНМО,1995.
А.Л.Брудно, Л.И.Каплан. Московские олимпиады по программированию, М: наука, 1990.
В.А.Дагене, Г.К.Григас. 100 задач по программированию, М: Просвещение, 1993.
В.М.Бондарев, В.И.Рублинецкий, Е.Г.Качко. Основы программирования, Харьков: Фолио, 1997.
В.М.Кирюхин, А.В.Лапунов, С.М.Окулов. Задачи по информатике. Международные олимпиады. М: ABF, 1996.
Н.М.Бадин, С.Г.Волченков, Н.Л.Дашниц. Ярославские олимпиады по информатике. Ярославль, 1995.
С.М.Окулов. Конспекты занятий по информатике (алгоритмы на графах). Киров,1996.
А.В.Алексеев. Олимпиады школьников по информатике. Красноярское книжное иэдательство,1995.
А.С.Сипин, А.И.Дунаев. Областные олимпиады по информатике. Вологда, 1994.
В.Пинаев. Городская олимпиада по программированию. Рыбинск, 1998.
С.А.Абрамов. Математические построения и программирование. 1987.
ПОДГОТОВКА ШКОЛЬНИКОВ К ОЛИМПИАДАМ ПО ИНФОРМАТИКЕ С ИСПОЛЬЗОВАНИЕМ ВЕБ-САЙТА
Образование, дистанционное обучение, олимпиада школьников, Красноярский край, Интернет-
Предметные олимпиады школьников занимают заметное место среди различного рода интеллектуальных конкурсов и состязаний, направленных на выявление, развитие и социальную поддержку одаренных школьников. Потребность в высококвалифицированных, творчески одаренных специалистах в различных областях знаний возрастает во всех промышленно развитых странах, поэтому наличие эффективной системы работы с одаренными детьми, позволяющей каждому учащемуся в полной мере развить свои таланты, является ключевым фактором интеллектуального и экономического развития каждого региона и страны в целом. По мнению экспертов, в ближайшем будущем Россия столкнется с нехваткой специалистов в области высоких технологий. Уже на сегодняшний день в стране наблюдается высокий спрос на профессионалов во всех сферах информационных технологий, а профессия программиста - разработчика компьютерного аппаратного обеспечения вошла в десятку самых востребованных, по мнению экспертов, профессий ближайшего десятилетия [Топ-10 самых востребованных профессий..., 2008].
В 2010 году перечень общеобразовательных предметов, по которым проводится Всероссийская олимпиада школьников, насчитывал 19 предметов. Со временем перечень только увеличивается, что расширяет возможности учащихся в проявлении своих талантов в различных предметных областях. Первая олимпиада по информатике была проведена с 13 по 20 апреля 1988 года в Свердловске и носила название еще не Всероссийской, а Всесоюзной, в ней приняли участие 80 школьников из всех союзных республик. За всю историю своего развития олимпиадное движение по информатике испытывало определенные взлеты и падения, обусловленные разными факторами. На сегодняшний день бурное развитие ИКТ послужило причиной тому, что содержание школьного предмета «информатика» свелось к изучению информационных технологий при незначительном количестве времени, отводимого на изучение основ программирования. В связи с этим одаренные школьники, интересующиеся программированием, не имеют возможности получить должного уровня знаний, необходимого для успешного выступления на олимпиадах по информатике, которые фактически являются олимпиадами по программированию и имеют специфические особенности [Беляев, 2005, с. 129]. Для успешного выступления на олимпиадах высокого уровня (муниципальный, региональный и всероссийский) учащийся должен не только знать и применять при решении задач определенный набор алгоритмов, но и отлично владеть техникой программирования, то есть уметь быстро реализовать и отладить любой алгоритм в виде программного кода, владеть специальными приемами программирования.
Безусловно, развитая система дополнительного образования, направленная на подготовку учащихся к олимпиадам по информатике, позволила бы решить многие проблемы, однако и здесь мы сталкиваемся с рядом объективных причин, не позволяющих это сделать, а именно: недостаточное количество специалистов высокого уровня, способных подготовить учащихся к решению олимпиадных задач, низкий уровень методического сопровождения подготовки учащихся к олимпиадам и, как следствие, непроведение школьных олимпиад по информатике во многих муниципальных образованиях края. Непроведение же первого
(школьного) этапа всероссийской олимпиады по информатике приводит к тому, что многие учащиеся не имеют возможности раскрыть свой талант в области олимпиадного программирования, а сама олимпиада не решает возложенных на нее задач.
Все это привело к тому, что на уровне региона возникла острая необходимость поиска новых форм и методов подготовки учащихся к олимпиадам по информатике, отвечающих современному содержанию олимпиад и учитывающих существующие особенности развития олимпиадного движения.
Отправной точкой для активизации процесса разработки и апробации новых методик подготовки школьников к олимпиадам по информатике можно считать начало реализации на территории Красноярского края в период 2005-2010 годов проекта «Информатизация системы образования», направленного на содействие в обеспечении доступности, качества и эффективности общего и начального профессионального образования. Основная миссия проекта заключалась в создании условий для системного внедрения и активного использования ИКТ в работе учебных заведений. Для реализации задач проекта начиная с 2005 года в крае было организовано проведение нескольких конкурсов, цель которых заключалась в поддержке педагогических инициатив, связанных с активным использованием ИКТ педагогами и учащимися в образовательном процессе, внеурочной деятельности, дополнительном образовании учащихся и др.
Именно реализация данных проектов послужила началом нового витка развития информатики в школе и олимпиадного движения по информатике в Красноярском крае. С 2007 года в организационную модель олимпиадной подготовки школьников Красноярского края активно встраиваются коммуникационные технологии. Одним из наиболее значимых проектов, реализованным в рамках данной программы, является проект отдела информационных технологий и телекоммуникаций КГБОУ ДОД «Красноярский краевой Дворец пионеров и школьников». В рамках данного проекта был разработан образовательный Интернет-ресурс «Школа программиста», расположенный в сети Интернет по адресу: http://acpm.ru. Главной целью данного ресурса являлось повышение у школьников Красноярского края уровня программирования и способностей, направленных на решение олимпиадных задач, посредством реализации технологии дистанционной подготовки школьников к олимпиадам по информатике.
Данный Интернет-ресурс содержит следующие разделы (рис.):
Архив задач по олимпиадному программированию;
Система автоматической проверки решений;
Раздел для проведения личных и командных олимпиад;
Дистанционный курс олимпиадного программирования;
Система общения участников с администратором и между собой;
Разбор задач;
Архив олимпиад.
[новости] [гостевая книга] [форум] [чат] [регистрация] Логин: | Пароль: |С(|
<# О школе <# Олимпиады > Фотоальбом > Архив 16 апреля 2010 г. в 7:30 (по москве) состоится Сибирский тур Всероссийской і олимпиады по информатике среди студентов педагогических ВУЗов. [Список і заявок] [Подать заявку] і Опубликован Протокол заседания жюри 11 (муниципального) этапа:Всероссийской олимпиады школьников Красноярского края по информатике, і Скачать: ргоІосоЮ 1 .рсіґ (220 Кб) II этап (районный) Всероссийской олимпиады школьников Красноярского края по информатике состоится 27-30 ноября 2009 года, который пройдет в 2 этапа і согласно расписанию, опубликованному в разделе "Олимпиады". Издано новое методическое пособие "Региональные олимпиады по: информатике - 2008/2009", содержащее описания, результаты, разбор и решения ізадач региональных олимпиад по информатике, проводимых на различных этапах в Красноярском крае в прошлом году. Подробнее... : Объявляется набор на курс Т"С++ для начинащих" в КДПиШ (г. Красноярск, іул. Конституции, 1). Предположительное время проведения занятий: вт., чт. 16:30- іУкажите лучший портал олимпиадного программирования neerc.ifino.ru/school/ і ^ olympiads.ru і г acm.timus.ru і г acm.sgu.ru і с programming-cMlenges.com і topcoder.com і
ЗАДАЧНИК ~~Ш
Архив задач + Состояние системы:<# Работа в системе Рейтинг * Разбор задач # Добавить задачу
Ш МЕТОДИЧКА Ш
#Новичкам:+ Алгоритмы I * Курсы КДПиШ > Курс олимлиадника # Дистрибутивы # Ссылки 1 Голосовать | ! Результаты Архив
■ поиск по сайту ш|
■ СЕЙЧАС В ONLINE ^™l|
1 СТАТИСТИКА ш
Педагогика
На сегодняшний день архив задач по олимпиадному программированию содержит 650 задач, 500 из которых доступны для самостоятельного решения с использованием встроенной проверяющей системы. Сложность задач определяется числом от 1 до 100, из этих значений сложности формируется рейтинг, отражаемый в соответствующем разделе. Деление задач по уровню сложности позволяет учащемуся самостоятельно выстраивать свою образовательную траекторию по принципу от простого к сложному. Все задачи представлены на русском языке и доступны через веб-интерфейс, также здесь есть возможность просмотра всех задач целиком.
Уровень представленных на сайте задач значительно легче тех, которые можно найти на подобных Интернет-ресурсах, например acm.timus.ru. Сложность многих задач ниже сложности задач, используемых при проведении муниципального этапа Всероссийской олимпиады школьников по информатике, что позволяет успешно готовиться к ним начинающим программистам. Интернет-ресурс ориентирован преимущественно на школьный уровень.
Часть используемых в системе задач составлены разработчиками самостоятельно, остальные взяты из различных источников: муниципальные и региональные олимпиады по программированию; сайт Интер нет-олимпи ад по программированию г. Санкт-Петер бург [Олимпиады по информатике].
Все задачи требуют работы с файлами input.txt и output.txt, предназначенными для чтения входных данных и вывода результата соответственно. Отправлять решения можно только зарегистрированным пользователям в виде исходного кода в файлах с расширениями *.pas, *.dpr, *.c, *.cpp, *.java, *.bas. Проверяющая система обрабатывает только программы, реализованные на языках Pascal, С++, Java и Basic, используя следующие компиляторы:
Borland Delphi 7.0;
Microsoft Visual C++ 7.1;
Java 2 SDK 1.5;
Microsoft QBasic 4.5.
Каждое отправленное решение проходит на сервере проверку не менее чем на 10 тестах, специально составленных для анализа решений участников. Задача считается решенной только в случае прохождения всех тестов. В случае неверного решения процесс тестирования прерывается на тесте, определившем ошибку. Результаты тестирования задач можно видеть в разделе «Состояние систе мы», также там отображаются результаты других пользователей. Итогом проверки является сообщение системы и номера теста, вызвавшего ошибку (если таковая имела место). В разделе «Состояние систе мы» пользователи могут просматривать тексты своих отправленных программ, а также видеть ошибки компиляции в случае вердикта «Compilation Error». В этом же разделе представлена статистика прохождения данной программы детально по каждому тесту.
Типы сообщений в системе соответствуют общему стандарту: «Accepted»; «Wrong an-swer»;«Time limit exceeded»; «Presentation error»; «Compilation error»; «Memory limit exce-eded»; «Runtime error»; «Compiling»; «Running» и «Waiting».
Каждая представленная на сайте задача имеет раздел «Обсуждение», в котором участники могут общаться и обсуждать возможные алгоритмы решения конкретной задачи. Некоторые задачи имеют раздел «Решение», в котором находится разбор решения конкретной задачи для тех, кто не может самостоятельно ее решить. По каждой задаче ведется рейтинг лучших попыток.
Помимо раздела для тренировок в разделе «Олимпиады» проводятся как личные, так и командные олимпиады различной сложности, являющиеся важной составляющей подготовки учащихся [Беляев, Лалетин, 2009]. Личные олимпиады предназначены для индивидуального участия, и в рейтинге здесь учитываются частичные решения, а время решения имеет меньший приоритет. В командных соревнованиях, как правило, принимают участие 3 человека и действуют правила АСМ-олимпиад, где зачет идет по числу абсолютно верно решенных задач и штрафным баллам по времени.
В настоящее время созданная система развивается и постоянно дорабатывается. За три первые года работы ресурса можно отметить следующие статистические результаты:
В базе задач имеется более 650 задач различного уровня сложности;
Зарегистрировано более 10 000 пользователей;
Проведено более 150 личных и командных олимпиад;
Посещаемость ресурса составляет 400 посетителей в сутки;
Автоматическая тестирующая система проверила более 500 000 решений участников.
В заключение изложим основные результаты работы.
1. Разработан образовательный Интернет-ресурс «Школа программиста», расположенный в сети Интернет по адресу: http://acmp.ru. Ресурс содержит архив из 650 задач и встроенную систему автоматической проверки решений. Интернет-ресурс активно используется не только для проведения командных и личных олимпиад по программированию, но и для подготовки школьников. Деление задач по уровню сложности обеспечивает соблюдение принципа доступности учебного материала и позволяет учащемуся самостоятельно выстраивать свою образовательную траекторию по принципу от простого к сложному.
2. Представлена технология дистанционной подготовки школьника к олимпиадам по информатике с использованием веб-сайта. В основу подготовки заложены современные ИТ-технологии с элементами дистанционного обучения - новой, развивающейся формой организации учебного процесса, отличающейся от общепринятой формы обучения тем, что она ориентирована главным образом на самостоятельную работу обучаемого.
Библиографический список
1. Беляев С.Н. Подготовка школьников к олимпиадам по информатике // Международный проект «Космос и одаренность»: разработки, доклады, информация. Красноярск: РИО КГПУ, 2005. Вып. 12. С. 129-131.
2. Беляев С.Н., Лалетин Н.В. Методика проведения олимпиад по информатике с помощью вебсайта // Перспектива-2008: сб. ст. II Международной научно-практической Интернет-конференции. Железногорск, 2009. Вып. 2. С. 28-30.
3. Олимпиады по информатике. Санкт-Петербург, Россия [Электронный ресурс] иЯЪ: http://ne-erc.ifmo.ru/school/, свободный. Загл. с экрана. Яз. рус.
В настоящее особую актуальность приобретает проблема подготовки школьников к олимпиадам по информатике различного уровня. Главной отличительной особенностью этих олимпиад является то, что фактически это олимпиады по программированию и уровень задач мало соответствует содержанию школьного курса информатики и ИКТ.
В лицее города Фрязино эта проблема решается комплексно :
· В профильных математических 8-х классах выделяется дополнительно к программе один час в неделю на предмет информатика
· В профильных классах старшей школы Программирование выделено как отдельный предмет
· С 2007 года у нас действует учреждение дополнительного образования Школа «Юный программист», которая не заменяет, а дополняет школьный курс информатики
На практике знакомство с правилами проведения олимпиад и «борьба» с типичными ошибками при отладке программ проводится практически при сдаче задач в автоматизированную тестирующую систему. В практической работе с учащимися по подготовке к олимпиадам, для закрепления навыков, требуется многократное решение задач определенного типа. Поэтому каждый «олимпиадник» получает свое, индивидуальное домашнее задание на сайте дистанционного обучения, разбор нерешенных задач проводится в группе, на занятиях в компьютерной школе. Подготовка школьника к олимпиаде состоит из постоянных тренировок и более всего напоминает подготовку спортсмена к соревнованиям. Надо учитывать, что длительность олимпиад с разбором задач составляет не менее 6 часов, поэтому особое значение имеет психологическая подготовка. Задача учителей и администрации - не превышать планку по другим предметам на период подготовки. Требуется контроль и поддержка не только со стороны родителей и учителя, а иногда помощь и понимание администрации.
В последние 6 лет ученики Лицея неоднократно становились победителями и призерами олимпиад самого различного уровня: Заключительного этапа Всероссийской олимпиады, Московской областной олимпиады, Открытой олимпиады «Информационные технологии»», Олимпиады школьников «Ломоносов», Открытой олимпиады школьников по информатике и программированию, Муниципальных олимпиад, Московской олимпиады по программированию, Всероссийского конкурса КИТ и других.
Как готовить к олимпиадам по информатике в таких условиях?
· Найти способных учеников и увлечь их программированием
· Удержать от «соблазнов» on-line жизни
· Стать им другом и сформировать из них команду
· Тесно взаимодействовать с родителями, администрацией, классными руководителями и учителями - предметниками
· Быть готовым к тому, что на каком-то этапе кто-то из них вас перерастет
Здравствуй, Хабр!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у хабражителей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.
Что же это за школа, как в ней учиться и как в нее поступить?
Отбор проходит в два этапа. Первый - экзамен по физике и математике. После него некоторые счастливчики попадают на собеседование, где от них требуется решить несколько олимпиадных задач по математике. И только после этого самые умные и удачливые становятся учениками.
Учиться очень тяжело и сложно. Учителя требуют идеального знания чуть ли не всех предметов. На родительском собрании сказали: «В начале обучения абсолютно все ученики скатываются до двоек, даже отличники. Те, кто начинают реально учиться - получают хорошие оценки. Остальные отсеиваются». У меня больше всего было проблем с русским языком и литературой, как бы это ни было странно.
Меня всегда привлекало программирование (что это такое я понял аж в 4 классе). Я был очень рад, когда в седьмом классе начали преподавать Pascal и различные вычислительные алгоритмы. Именно тогда я написал первый «Hello World!», алгоритм Евклида; изучил условные операторы, циклы, массивы.
С восьмого класса учителя приглашали на факультативы по информатике, где мы изучали графы, алгоритмы сортировки массивов и многое другое.
Посмотрим на совершенно типичную задачу для начинающих программистов-олимпиадников
Пятью пять - двадцать пять!
(Время: 1 сек. Память: 16 Мб Сложность: 8%)
Вася и Петя учатся в школе в одном классе. Недавно Петя поведал Васе о хитром способе возведения в квадрат натуральных чисел, оканчивающихся на цифру 5. Теперь Вася может с легкостью возводить в квадрат двузначные (и даже некоторые трехзначные) числа, оканчивающиеся на 5. Способ заключается в следующем: для возведения в квадрат числа, оканчивающегося на 5 достаточно умножить число, полученное из исходного вычеркиванием последней пятерки на следующее по порядку число, затем остается лишь приписать «25» к получившемуся результату справа. Например, для того, чтобы возвести число 125 в квадрат достаточно 12 умножить на 13 и приписать 25, т.е. приписывая к числу 12*13=156 число 25, получаем результат 15625, т.е. 1252=15625. Напишите программу, возводящую число, оканчивающееся на 5, в квадрат для того, чтобы Вася смог проверить свои навыки.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число А, оканчивающееся на цифру 5, не превышающее 4*10^5.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно натуральное число - A2 без лидирующих нулей.
Примеры:
INPUT.TXT
5
75
4255
OUTPUT.TXT
25
5625
18105025
Скрытый текст
Wrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Вот задача оттуда
Б. Бобр
Ограничения по памяти: 64 Мб
Бобр собирается построить каскад плотин и уютную хатку в русле неширокой реки. Так получилось, что река протекает по идеально прямой траектории, и ширина реки настолько мала, что в рамках данной задачи мы можем ею пренебречь. На берегах реки стоят деревья, которые бобр может использовать для строительства. Ученые решили выяснить, насколько оптимально бобр выбирает места для строительства плотин и хатки с точки зрения минимального суммарного расстояния, на которое необходимо переносить деревья.
Напишите программу, которая по заданным координатам деревьев относительно начала прямого участка реки, если считать ось сонаправленной течению определяет координаты объектов, соответствующие минимальному суммарному расстоянию, на которое необходимо переносить деревья.
Формат входных данных:
<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится два целых положительных числа 1<=N<=1000, 0<=М<=10, 0<=L<=100 – соответственно количество деревьев, растущих на берегах реки, количество деревьев, необходимое для возведения одного объекта и количество объектов, которые необходимо возвести. В каждой из следующих N строчек записано единственное положительное вещественное число – расстояние в метрах от начала прямого участка реки (самого высокого по течению) до места, где растет соответствующее дерево. Известно, что деревьев гарантированно хватает, чтобы построить все объекты (N>=M*L)
Формат выходных данных:
Для каждого тестового блока в отдельной строке необходимо вывести единственное число - сумму координат мест, в которых необходимо возвести объекты, чтобы суммарное расстояние, на которое потребуется перенести деревья для строительства, было минимальным, указав три точных знака после десятичного разделителя.
Входные данные
2
5 3 1
0.1
1.2
5.6
7.3
9.4
2 2 1
1
2
Выходные данные
7.300
1.000
Решить задачу, если объект один достаточно просто. Но когда объектов больше - приходится применять достаточно сложный раздел программирования, «Динамическое программирование». Учитель, который вел у нас факультатив признался в том, что он плохо представляет как решить эту задачу (совместными усилиями мы вывели значение, которое нужно минимализировать, просто построив несколько графиков, даже не спрашивайте что это за значение - я его благополучно забыл).
В результате задачу на полный балл решил лишь один участник олимпиады.
А вот еще одна задача, решение жюри на которой было пересмотрено (из того же муниципального этапа):
А. Альбатрос
Ограничения по времени: 1 секунда на тест
Ограничения по памяти: 64 Мб
Альбатрос может совершать длительные перелеты, преодолевая длинные расстояния над просторами океана. Орнитологи решили определить, сколько километров может пролететь альбатрос, не посещая сушу. Для этого флотилия плавучих исследовательских лабораторий рассредоточилась по океану и записала данные об изучаемой особи, к которой прикреплена радиометка. Ученые фиксируют момент времени и текущие координаты того места, где они обнаружили альбатроса.
Напишите программу, определяющую расстояние, которое преодолел альбатрос в течение эксперимента, если считать, что в зоне наблюдений наша планета представляет собой идеальный шар радиусом 6366,197 километров.
Формат входных данных:
В первой строке входных данных содержится единственное целое положительное число 1<=T<=10 – количество тестовых блоков, идущих друг за другом. В первой строке каждого тестового блока содержится единственное целое положительное число 2<=N<=1000, количество записей о появлении альбатроса. В каждой из следующих N строчек записаны по двенадцать целых неотрицательных чисел (0<=d1<=90, 0<=m1<=90, 0<=s1<=90, 0<=d2<=90, 0<=m2<=90, 0<=s2<=90, 0<=h<=23, 0<=mt<=59, 0<=sec<=59, 1<=dd<=31, 1<=mm<=12, 2000<=yy<=2012) – соответственно градусы минуты и секунды северной широты, градусы, минуты и секунды западной долготы того места, где плавучая исследовательская лаборатория заметила альбатроса; время в формате часы, минуты, секунды и дата наблюдения в формате день, месяц, год.
Формат выходных данных:
Для каждого из тестовых блоков в отдельной строке необходимо вывести единственное целое число – расстояние, которое преодолел альбатрос, округленное до ближайшего четного целого числа.
Пример входных и выходных данных:
Входные данные
2
3
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 2 0 0 0 0 3 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
2
0 0 0 0 0 0 0 0 0 1 1 2012
0 0 0 0 1 0 0 0 0 2 1 2012
Выходные данные
4
2
Полный текст муниципального этапа можно найти .
Вот первая
Г. Герой дня
Ввод/вывод: стандартный
Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 1<=L<=10000 – количество записей, попавших в обзор за текущий день. В каждой из следующих строк вначале указывается число – количество просмотров соответствующей записи и затем имена и фамилии людей, упоминающихся в записи. Имена и фамилии состоят из букв английского алфавита, число, а также все соседние слова отделяются друг от друга ровно одним пробелом. Суммарная длина строки составляет не более 200 символов.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести имя и фамилию человека, записи с упоминанием которого набрали больше всего просмотров. Если таких людей несколько нужно вывести того, кто идет раньше других по алфавиту.
Входные данные
1
100500 John Travolta John Lennon
5
5 Vasya Pupkin Sergey Syroezhkin
10 Harry Potter
5 Garry Potter Vasya Pupkin
5 Sergey Syroezhkin
12341234463456234123466543342 Arnold Schwarzenegger
Выходные данные
John Lennon
Arnold Schwarzenegger
Именно после этой задачи мне пришла идея «словаря», тип данных с удобным поиском по людям. Если кому интересно - напишу в комментариях, можете спросить в ЛС, но чувствую что это тот еще велосипед.
Необходимо составить список из людей с общим количеством просмотров (посмотрите на человека с идентификатором Arnold Schwarzenegger, требуется длинная арифметика), а затем просто выбрать нужного человека из нашего списка. Чтобы упростить алгоритм наши одиннадцатиклассники использовали хэш-функцию для имени (сумма всех ASCII номеров символов в имени), что существенно ускорило работу программы, коллизии получились небольшими.
Вторая задача или задача архивации
В. Великий архиватор
Ввод/вывод: стандартный
Ограничения по времени: 1 секунда
На планете роботов очень любят автоматическую обработку текстов. Для этого роботы ввели специальную должность Великого Архиватора. В обязанности Великого Архиватора входит составление списка всех слов текста и замена слов на число, обозначающее номер этого слова в списке.
Напишите программу, выполняющую функции Великого Архиватора.
Формат входных данных:
В единственной строке входных данных приводится строка длиной не более миллиона символов, состоящая из строчных и заглавных букв английского алфавита и пробелов. Любые два соседних слова в тексте разделены ровно одним пробелом. Слова считаются одинаковыми, если они равны с точки зрения сравнения строк, причем строчные и заглавные буквы считаются различными.
Формат выходных данных:
В единственной строке выходных данных необходимо вывести последовательность номеров слов текста, причем слова в списке должны быть упорядочены в порядке их появления в тексте. Нумерация слов должна начинаться с единицы.
Примеры входных и выходных данных:
Входные данные
To be or not to be
Why do you cry Willie Why do you cry Why Willie Why Willie Why Willie Why
Выходные данные
1 2 3 4 5 2
1 2 3 4 5 1 2 3 4 1 5 1 5 1 5 1
Пояснение к примерам входных и выходных данных: текст во втором примере не содержит символов перевода строки и возврата каретки.
Достаточно простой алгоритм сжатия (не помню как называется). Мне было интересно реализовать. Я решил эту задачу созданием массива из слов, добавлял туда первое слово. Затем считывал каждое следующее слово, проверял, нет ли его в массиве. Если оно было - записывал в выходной поток номер слова, иначе - добавлял в массив, записывал номер.
В принципе, мое решение не получило полный балл.
Полный текст заданий можно найти .
На дистанционном туре я занял 1 место среди девятиклассников.
Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.
