Здравствуй, Хабр!
Пишет тебе девятиклассник, призер регионального этапа всероссийской олимпиады по информатике. В последнее время я стал замечать, что у хабражителей повысился интерес к олимпиадам по программированию. Как их активный участник я постараюсь ответить на все вопросы, рассказать о своем пути, привести примеры реальных, запомнившихся мне задач.
Об обучении
Учусь я в школе с углубленным изучением физики, математики и информатики.Что же это за школа, как в ней учиться и как в нее поступить?
Отбор проходит в два этапа. Первый - экзамен по физике и математике. После него некоторые счастливчики попадают на собеседование, где от них требуется решить несколько олимпиадных задач по математике. И только после этого самые умные и удачливые становятся учениками.
Учиться очень тяжело и сложно. Учителя требуют идеального знания чуть ли не всех предметов. На родительском собрании сказали: «В начале обучения абсолютно все ученики скатываются до двоек, даже отличники. Те, кто начинают реально учиться - получают хорошие оценки. Остальные отсеиваются». У меня больше всего было проблем с русским языком и литературой, как бы это ни было странно.
Меня всегда привлекало программирование (что это такое я понял аж в 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
Требования
От олимпиадника требуется написать программу на одном из принимаемых языков (обычно этот набор состоит из Pascal (сам пишу, никогда проблем не было), Delphi, C++, Java, Visual Basic, в последнее время добавляют C#, Python). После этого исходный файл отправляется в систему-песочницу, где он компилируется и выполняется на группе тестов. За каждый тест участник олимпиады получает некоторый балл, которые потом складываются. После олимпиады результаты становятся видны всем. Чем больше суммарный балл - тем выше место.Стоит отметить, что обычно проверяющими системами плохо обрабатывается управляемый код (Java, C#). Мой друг лично на региональном этапе получил на трех из четырех задач 0 баллов из-за ошибки во время выполнения (писал на C#), хотя проверялось все нормально. Что делать в таком случае не понял ни я, ни он; на апелляции жюри просто пожали плечами.
Риски
На чем можно проиграть? Существуют 7 типов ошибок:Скрытый текст
Wrong answer
Неверный ответ. Результат работы программы не совпадает с ответом жюри
Неверный формат вывода или алгоритмическая ошибка в программе
Time limit exceeded
Превышен указанный в задаче лимит времени. Программа выполняется дольше установленного времени
Неэффективное решение или алгоритмическая ошибка в программе
Presentation Error
Отсутствие выходного файла OUTPUT.TXT
Файл не создан, неверное имя файла или сбой программы до открытия выходного файла
Compilation error
Ошибка компиляции. В результате компиляции не создан исполняемый файл
Синтаксическая ошибка в программе или неверно указано расширение файла. Возможно, что при реализации на языке Java был использован класс, отличный от Main
Memory limit exceeded
Превышен указанный в задаче лимит памяти. Программа использует больше установленного размера памяти.
Неэффективный алгоритм, либо нерациональное использование памяти
Runtime error
Ошибка исполнения. Программа завершила работу с ненулевым кодом возврата. В этом случае результат работы не проверяется
Возможно, в программе произошло обращение к несуществующему элементу массива, деление на ноль и т.д. Возможно, программа на C++ не завершается оператором «return 0» или по иной причине вернула ненулевой код возврата
Олимпиады
Как проходит всероссийская олимпиада по информатике?Я прошел всего 5 этапов: 8-9 классы в школе, 8-11 классы в школе, муниципальный этап, дистанционный тур региональной олимпиады, региональная олимпиада. Далее идет всероссийский тур, но я на него, к сожалению, не попал. Сейчас я расскажу про те задачи, которые мне очень понравились.
Этап среди старшеклассников
Во время тура среди 8-11 классов была задача «Полиномиальные хэш функции» условие которой было записано на двух страницах формата A5. В этом условии была приведена краткая информация о хэш функциях, их истории, была предложена одна такая функция. Задача заключалась в её вычислении для массива входных данных. Нас испугало очень страшное название, сложная терминология, запись суммы её значком (тот который выглядит как буква E) и в результате её мало кто вообще начал решать. Условие сейчас найти, к сожалению, не смогу.Муниципальный этап
Муниципальный этап получился просто убийственным по сложности.Вот задача оттуда
Б. Бобр
Ограничения по памяти: 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
Достаточно простая задача: необходимо отсортировать значения по дате появления Альбатроса, вычислить длину каждой дуги между двумя точками, а потом их все сложить. В решении принимается допущение, которое позволяет использовать теорему Пифагора.
Но почему же решение было пересмотрено? Взглянем на диапазон минут и секунд.
0<=m1<=90, 0<=s1<=90
Вы, наверное, наивно предположили, что в одном градусе 60 минут? Или что в одной минуте 60 секунд? Ха-ха! Тут же явно написано «90».
Тесты были составлены именно с учетом перевода: в одном градусе 60 минут, в одной минуте 60 секунд. Это безобразие было успешно оспорено нашими учителями.
Самое обидное, что даже пример получился неправильный
В результате задачу не решил, по-моему, вообще никто.
Полный текст муниципального этапа можно найти .
Дистанционный тур
Задачи дистанционного тура были гораздо интереснее. Мне запомнились две задачи.Вот первая
Г. Герой дня
Ввод/вывод: стандартный
Медиахолдинг «Пермь Великая» отслеживает сообщения блоггеров Пермского края и каждый день пытается выяснить, кто является наиболее популярным в записях для того чтобы включить этого человека в традиционную рубрику «Герой дня».
Для каждой записи, попавшей в список отслеживания, известно количество просмотров и те персоналии, которые в ней упоминаются. Напишите программу, определяющую человека, для которого суммарное количество просмотров для записей, где он упоминается, максимально.
Формат входных данных:
В первой строке входных данных приводится единственное целое число 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 место среди девятиклассников.
Региональный этап
На этапе региональном было не так весело, тура было два. Я боялся подвести школу и не пройти на следующий этап, плохо показать нашу школу. Поэтому и задания воспринимались не так весело и приятно. В общем: ничего не запомнил оттуда, но получил заветный диплом. Да и условия мне не удалось найти.На второй день к нам приехали представители местной компании «Прогноз», поиграли с нами в «Что? Где? Когда?», провели викторину. Победителям раздали призы.
Подготовка
Как же я готовился?Ответ достаточно прост: у меня хорошие учителя. Мне это было интересно и я получал от всего происходящего удовольствие. Я усердно готовился и добился того, чего хотел.
Что делать, если Вам это тоже интересно и Вы хотите принять во всем этом участие?
- Существуют системы подготовки школьников к олимпиадам по программированию, на них есть тестовая система и куча условий с решениями. Насколько я понимаю, на всех таких системах нужна регистрация. Я готовился при помощи двух:
- acmp.ru Есть достаточно много задач разной сложности, так же интересен раздел «Курс олимпиадника»
- http://acm.timus.ru/ Куча задач с самых разных олимпиад, некоторые на английском. В разделе http://acm.timus.ru/offline у нас проводился дистанционный и региональный этапы.
- Существуют онлайн олимпиады, я участвовал лишь в одной: NetOI от украинцев. Отзыв такой: ХАРДКОР!!! Дальше второго тура не прошел. Код нужно писать ужасно оптимально (я так не умею), для каждого теста индивидуальные условия (удвоенное время программы жюри).
Что же дальше?
Говоря это, я подразумеваю вопрос о том, насколько олимпиадники приспособлены к работе в реальных условиях.Хоть я и не работал еще в IT индустрии, но я считаю: олимпиадники никак не приспособлены к реальной работе. На таких олимпиадах требуется уметь быстро изобрести «велосипед», знать хорошо алгоритмы. Я с другом занимаюсь написанием небольших игр и понимаю, что гораздо важнее уметь выбрать правильную технологию для твоих целей, уметь найти готовое решение чтобы ускорить разработку, «Велосипеды не нужны». Поправьте меня, если это не так.
Если кого интересует то, чего я в жизни хочу: на самом деле я не очень-то люблю IT и информатику, мечта моя - выучиться на физика-теоретика и заниматься исследованиями. А так как в РФ с этим проблемы я планирую уехать в Канаду или США.
Приму любые пожелания в ЛС или в комментариях. Надеюсь, данная статья не получилась длинной. Надеюсь она была для Вас интересна. Надеюсь Вас не раздражала моя неграмотность, уж очень я плохо знаю пунктуацию.
Сайт, поддерживаемый Московским центром непрерывного математического образования, содержит большое количество задач по программированию различного уровня. Идеально подходит для тех, кто делает первые шаги в программировании: во многих разделах есть ссылки на теоретический материал по соответствующий теме, к большинству задач приложен подробный разбор. Для всех заданий доступна автоматизированная проверка решений.
Олимпиада Всероссийская олимпиада по информатике Региональный этап пройдет 16 и 18 января 2020 года
Состязание для школьников 5-11 классов. Победители и призеры финала получают льготы при поступлении в вузы
Информатика
Codeforces.com . Портал, объединяющий огромное количество участников соревнований по программированию по всему миру. На сайте регулярно проводятся онлайн-соревнования для школьников самого разного уровня: от начинающих до многократных чемпионов мира. Многие известные компании, в том числе ВКонтакте, Mail.Ru, Тинькофф Банк и AIM Tech проводят на платформе официальные соревнования.
Помимо этого, на портале обсуждается все, что связано с программированием, начиная от только-только опубликованных статей о структурах данных и заканчивая эмоциями о недавно прошедшем соревновании. На сайте также содержится большой архив задач, доступных для автоматизированной проверки.
Вики-конспекты . Энциклопедия по дискретной математике и теории алгоритмов, составленная студентами ИТМО. В ней описано большинство алгоритмов, используемых на олимпиадах по программированию. Многие статьи содержат примеры задач и псевдокоды приведенных алгоритмов. Конспекты написаны очень подробно и качественно. Это один из немногих ресурсов на русском языке по данной теме.
Maximal . Мини-энциклопедия, содержащая наиболее популярные алгоритмы в олимпиадной информатике, к большинству из которых приведены реализации и примеры использования. Сайт отличается чуть более неформальным стилем изложения (что иногда может сказаться на качестве статей или корректности алгоритмов), однако он облегчает восприятие информации. На сайте размещены ссылки на полезные книги для более детального изучения приведенных алгоритмов, а также разобраны некоторые конкретные задачи, представляющие особенный интерес.
Олимпиады по информатике . Сайт, посвященный олимпиадам школьников по программированию в Санкт-Петербурге, официальный сайт Всероссийской командной олимпиады школьников (ВКОШП), индивидуальной олимпиады школьников по информатике и программированию (ИОИП). Одним из главных достоинств этого сайта является очень богатый архив проводимых в России мероприятий, в том числе Всероссийской олимпиады: сайт содержит презентации с разбором задач и результатами соревнований. Также здесь регулярно проводятся личные и командные соревнования для школьников.
Olympiads.ru . Сайт, посвященный олимпиадам школьников по программированию в Москве, официальный сайт Открытой олимпиады школьников по программированию, задачи на которой не уступают по сложности заданиям Всероссийской, а иногда изящнее и интереснее. Помимо этого, олимпиада включает заочный тур, задачи которого часто требуют изучения новых алгоритмов в течение соревнования. На сайте опубликованы материалы прошедших соревнований, а также ссылки на информацию о предстоящих событиях.Книги
Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ . Данная книга является классическим учебным пособием с подробным описанием алгоритмов и структур данных, а также базовыми сведениями из дискретной математики, необходимыми каждому программисту. Помимо этого книга содержит огромное количество упражнений различной сложности, которые будут интересны и самому искушенному читателю. В ней очень удачный стиль изложения, и хотя она ориентирована на студентов, большая часть материала будет доступна и школьникам.
Вопрос 1. Как научиться решать олимпиадные задачи по информатике?
Чтобы научиться решать олимпиадные задачи по информатике, надо решать задачи по информатике... Естественно при этом заглядывая в соответствующею литературу.
Вопрос 2. Сколько необходимо решить задач, чтобы достойно выступать на олимпиадах по информатике?
Вопрос задан конечно не корректно и ответить на него, пожалуй вряд ли возможно, но сказать пару слов по этому поводу стоит. Как мне соощил специалист в области подготовки к олимпиадам ACM Михаил Медведев , то создать принципиально новую олимпиадную задачу не так то просто, как может показаться на первый взгляд. По этой причине, лица ответственные за проведения олимпиад просто берут задачи за прошлые годы и подают их под "новым соусом". Часто случается, что задачи для районных и зональных олимпиад по информатике "сдирают" без каких либо изменений с сайтов посвященных олимпиадному программированию.
Итак, поскольку многие задачи весьма и весьма схожи, то необходимо научиться решать задачи из всего диапазона: сортировка, динамическое программирование, длинная арифметики и т.д.
Вопрос 3. Можно ли подготовить школьников к олимпиадам по информатике в рамках школьной программы?
Думаю, что это нереально. Всем давно известно, что школьный курс информатики - это одно, а олимпиады по информатике - это совсем другое. Да, в примерной программе по информатике, в 9 классе, довольно большое количество часов уделено изучению программирования. В учебнике Семакина для 9 класса обучение программированию основано на языке Паскаль, у Угриновича примеры дана применительно к Visual Basic . Но, даже если применить дифференцированный подход к обучению школьников, вряд ли этих часов хватит для подготовки к олимпиадам отдельных школьников с "нуля".
Вопрос 4. Если часов по программе не достаточно для подготовки школьникам к олимпиадами, то как тогда готовиться?
По первым двум вариантам все понятно, но должно быть понимание со стороны руководства школы. Частенько, между учителями бывает "битва за часы", на кружок или факультатив по программированию часов может и не перепасть.
Личный энтузиазм доведенный до крайней меры - это весьма пагубное, на мой взгляд, явление. Российское образование не должно держаться на энтузиазме. Иначе получается, что пока есть энтузиазм - дело идет, закончился запал и все рухнуло. На энтузиазме долго не протянешь, но его иногда стоит проявлять в надежде, что дело сдвинется с "мертвой точки".
Вопрос 5. У меня 25 (26, 30...) часов основной нагрузки, реально ли еще заниматься с учащихся на кружке по программированию?
Как мне кажется, при такой нагрузке реальней сойти с ума, чем готовить учащихся к олимпиадам. Искренне сочувствую всем учителям с большой нагрузкой. Я понимаю, что брать большое количество часов приходится не от хорошей жизни, но не понимаю, как можно работать в таких условиях.
Вопрос 6. Могут ли школьники готовиться к олимпиадам во внеурочное время и если могут, то как лучше организовать подготовку?
Могут, но у них как минимум должен быть домашний компьютер. В идеале должен быть еще и Интернет. При наличии ПК и Интернета можно решать задачи на одном из специализированных сайтов с автоматизированной проверкой решений, например на сайте Школа программиста .
Вопрос 7. Что требуется от учителя для качественной подготовки школьников к олимпиаде?
- Умение учиться. Ведь как случается, закончил человек учебное учреждение и на этом его развитие в плане получения информации порой и заканчивается. Для работы в школе вроде хватит, так зачем еще заморачитваться...
- Всегда быть на связи. У вашего ученика может возникнуть вопрос в любое время, есть ведь и такие, которые решают задачки по ночам. Если вам не спится, то почему бы, при возможности, ему не ответить при помощи той же "Аськи" или программы Skype .
ПОДГОТОВКА ШКОЛЬНИКОВ К ОЛИМПИАДАМ ПО ИНФОРМАТИКЕ С ИСПОЛЬЗОВАНИЕМ ВЕБ-САЙТА
Образование, дистанционное обучение, олимпиада школьников, Красноярский край, Интернет-
Предметные олимпиады школьников занимают заметное место среди различного рода интеллектуальных конкурсов и состязаний, направленных на выявление, развитие и социальную поддержку одаренных школьников. Потребность в высококвалифицированных, творчески одаренных специалистах в различных областях знаний возрастает во всех промышленно развитых странах, поэтому наличие эффективной системы работы с одаренными детьми, позволяющей каждому учащемуся в полной мере развить свои таланты, является ключевым фактором интеллектуального и экономического развития каждого региона и страны в целом. По мнению экспертов, в ближайшем будущем Россия столкнется с нехваткой специалистов в области высоких технологий. Уже на сегодняшний день в стране наблюдается высокий спрос на профессионалов во всех сферах информационных технологий, а профессия программиста - разработчика компьютерного аппаратного обеспечения вошла в десятку самых востребованных, по мнению экспертов, профессий ближайшего десятилетия [Топ-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/, свободный. Загл. с экрана. Яз. рус.