В марте 1995 года исполнилось десять лет со дня введения в школьную программу предмета информатика.
Два события этого месяца ознаменовали юбилей. Речь идет о двух олимпиадах школьников по информатике - московской, проходившей в лицее N 1511 при МИФИ с 5 по 12 марта (N 10/95), и всероссийской, проходившей в г. Троицке Московской области с 23 по 29 марта (N 14, 15/95). Сегодня хотелось бы подвести итоги прошедших олимпиад и поделиться некоторыми мыслями о проведении в дальнейшем московских городских олимпиад. Но прежде небольшой экскурс в историю.
Почти сразу же после введения в школьную программу информатики в Москве стали проходить школьные олимпиады. В их проведении активное участие принимали сотрудники МИФИ и лицея N 1511 (тогда ФМШ N 542 при МИФИ). Олимпиады проходили в безмашинном варианте в два этапа. Первый этап - районные олимпиады, проходившие в середине февраля одновременно во всех районах столицы. Задачи готовились оргкомитетом московской олимпиады. В каждый район выезжали представители оргкомитета и осуществляли проверку задач и выявление победителей. Победители районных олимпиад приглашались на второй тур, который проходил в марте.
Несмотря на большие организационные сложности: выезд представителей оргкомитета сразу в 33 района и безмашинная проверка работ (а это 50-100 работ по 3-4 задачи) - такой способ проведения олимпиады обеспечивал возможность любому школьнику принять в ней участие. И в результате победителями становились действительно сильнейшие.
К девяностым годам ситуация сильно изменилась. В 1989 году прошла первая, тогда еще всесоюзная, олимпиада по информатике. В 1990 году в Минске прошла II международная олимпиада по информатике (это была первая олимпиада, в которой участвовали победители олимпиад разных стран). Все эти олимпиады проводились на компьютерах. Изменились и критерии оценки решения задач. Теперь проверялся не текст программы, а работа программы на специально подобранных тестах.
В этих условиях проведение городской олимпиады в безмашинном варианте потеряло смысл. То ли по этой причине, то ли из-за отсутствия средств, а может быть, еще по каким-то причинам, но олимпиады в Москве проводиться перестали. Правда, на российскую олимпиаду каждый год каким-то образом отбиралась команда. Но, естественно, такая команда не могла добиться каких-либо существенных результатов. В итоге сложилось мнение, что на российских олимпиадах по информатике московская команда не может претендовать на призовые места.
В 1992/93 учебном году мы сделали первую попытку изменить сложившуюся ситуацию. Небольшая инициативная группа под руководством Натальи Михайловны Леоновой, в которую вошли сотрудники и студенты МИФИ, при участии преподавателей и учащихся ФМШ N 542 предложили провести московскую городскую олимпиаду по новым правилам. Идея была взята от проходившей летом 1992 года международной командной олимпиады в Сингапуре. "Сингапурская" олимпиада проводится по следующим правилам. Каждая команда состоит из трех человек. Команде предоставляется один компьютер. Необходимо за короткое время (2 часа) решить несколько задач (3-4). Все задачи оцениваются одинаково - по 100 баллов. В случае если программа не прошла хотя бы один из тестов, она возвращается команде на доработку, а с команды снимается 10 очков. Кроме того, команда получает призовые очки за скорость выполнения задач.
Такой вариант проведения олимпиады имеет ряд преимуществ. Во-первых, количество участников в три раза превышает количество имеющихся компьютеров, во-вторых, результат олимпиады оглашается практически сразу после окончания тура. Кроме того, здесь проявляются такие важные для современного программиста качества, как умение работать в команде, разделить работу на несколько человек, довести свои мысли до товарищей.
Правда, от организаторов требуется особая четкость в проведении олимпиады, так как проверка задач происходит в реальном времени и ошибки или нерасторопность проверяющих могут стоить командам очень дорого. Есть и еще некоторые недостатки, о которых будет сказано несколько позднее.
Решив провести олимпиаду, мы обнаружили, что московский департамент образования не горит желанием чем-то помочь нам. Ни на проведение олимпиады, ни на подарки средств нам не выделили. И только благодаря МИФИ, АО КУДИЦ, КНПП БИТ и, конечно же, ФМШ N 542, предоставившей помещения и компьютеры, удалось провести первую компьютерную олимпиаду в Москве. Победители получили право внеконкурсного поступления в МИФИ. По результатам олимпиады и дополнительного отборочного тура среди лучших команд была отобрана команда Москвы для участия в Российской олимпиаде, в нее вошли два одиннадцатиклассника из 444-й школы и два десятиклассника из 542-й школы, которые, хотя и не смогли победить, привезли один диплом II степени и два III. Это был первый прорыв.
К сожалению, на следующий год, несмотря на все наши старания, средства не были выделены и олимпиада в Москве опять не проходила.
В этом году удалось наконец-то получить поддержку в департаменте образования Москвы. Правда, финансировать олимпиаду было поручено МИПКРО. Не буду описывать, насколько сложно работать с этой организацией, скажу только, что согласие финансировать олимпиаду было получено менее чем за неделю до ее начала. Часть подарков была оплачена через две недели после их вручения, подарки за второй тур еще не вручены, так как были оплачены почти через месяц после их заказа, а людям, принимавшим участие в организации и проведении олимпиады, в разработке и проверке задач, деньги до сих пор не выплатили. И без поддержки таких фирм, как Microcom и КНПП БИТ, нам опять не удалось бы провести олимпиаду.
Теперь о самой московской олимпиаде. Она проходила в два тура. Первый тур командный. Каждый округ выставил по две команды, плюс по одной команде от лицеев и гимназий городского подчинения. Лицей N 1511 при МИФИ как организатор выставил две команды. Вне конкурса участвовала команда СУНЦ МГУ. Всего в I туре участвовали 30 команд.
Несколько слов о подборе задач. Конечно, в связи с финансовыми трудностями трудно было привлечь большое количество квалифицированных людей в задачную комиссию. Однако, на наш взгляд и по мнению многих руководителей команд, задачи получились неплохие. Об этом говорят и результаты. Все три задачи решили только две команды. Несколько команд решили две задачи, были и те, кто не решил ни одной. Таким образом, сложность задач была подобрана так, что удалось об'ективно проранжировать команды.
Первое место с результатом 334 очка завоевала команда Восточного округа, состоявшая из одиннадцатиклассников 444-й и 400-й школ.
Второе место с результатом 291 очко заняла команда лицея N 1511 при МИФИ. Эту команду хотелось бы особо отметить, так как она состояла только из десятиклассников и капитаном команды была девушка.
Третье место с результатом 159 очков заняла команда Центрального округа, состоявшая из одиннадцатиклассников 345-й школы.
Следует также отметить команду СУНЦ МГУ, выступавшую вне конкурса и набравшую 216 очков.
К недостаткам командного тура можно отнести невозможность определения силы каждого участника, так как в сильной команде может оказаться слабый участник и наоборот. С этой целью был проведен второй тур московской олимпиады - индивидуальный. На него приглашались члены команд, занявших первые девять мест. К указанным ранее четырем были добавлены команды Зеленограда (шк. N 1030), вторая команда лицея N 1511 при МИФИ, а также округов Западный (шк. N 1543), Северо-восточный (шк. N 301) и Юго-восточный (шк. N 491).
При этом если в команде был хоть один сильный участник, то команда должна была сделать хотя бы и не полностью две задачи, а следовательно, заведомо попасть в число первых девяти.
На второй тур была предложена одна задача на 4,5 часа. К сожалению, задачная комиссия недооценила силы участников и дала слишком много времени. В результате определилась группа из шести человек, которая хотя и значительно опередила остальных, но очки у участников, входящих в эту группу, не сильно различались.
При отборе команды Москвы на Российскую олимпиаду было принято решение среди этой шестерки провести дополнительный отборочный тур. В результате была отобрана команда из трех человек, состоящая из учеников 444-й школы и лицея N 1511.
На Российской олимпиаде московская команда впервые добилась ощутимых результатов. Павловский Владимир (шк. N 444) занял абсолютное второе место с существенным отрывом от третьего, проиграв только прошлогоднему победителю международной олимпиады по информатике. А Кольцова Света (лицей N 1511) вообще оказалась единственной девушкой на олимпиаде, сумевшей к тому же оставить позади 24 школьника, большей частью одиннадцатиклассников.
В целом по Москве хочется отметить Восточный округ, выставивший очень сильную команду из 444-й и 400-й школ, Центральный округ - команда 345-й школы и лицея N 1511 при МИФИ. Следует сказать, что в 1992/93 учебном году также отличились именно эти школы. Таким образом, напрашивается вывод, что в этих школах традиционно сильная подготовка по информатике.
К сожалению, ни один лицей (кроме 1511-го) не смог представить команду, способную достойно выступать на олимпиадах. Да и вообще большинство команд (кроме упомянутых ранее) были откровенно слабыми. На наш взгляд, причина здесь в том, что по округам не проводилось отборочных олимпиад и команды формировались далеко не из самых сильных ребят. В связи с этим хочется сказать, как нам видится будущее московских олимпиад.
Уже в следующем учебном году необходимо возобновить предварительные туры олимпиад, проводимые в округах. Регламент их проведения может быть аналогичным регламенту городской олимпиады. Проводить их надо не позднее конца января. В феврале должна быть проведена городская олимпиада. По ее результатам необходимо отобрать команду города Москвы и провести с ней как минимум недельные сборы. Такие города, как Санкт-Петербург, Киров, Нижний Новгород, постоянно готовят команды и имеют стабильные результаты на российских олимпиадах. Если мы хотим, чтобы успех этого года не стал хоть и приятным, но исключением из правил, то должны уделять значительно больше внимания подготовке ребят. Дело в том, что олимпиады по информатике в значительной степени приближаются к спортивным соревнованиям, таким как шашки или шахматы, и требуют определенной подготовки.
Необходимо изменить и сам регламент городской олимпиады. Индивидуальных туров надо проводить два. Задач должно быть по 2-3 в каждом туре, так же, как на российской и международной олимпиадах.
В заключение хотелось бы сказать, что приведенные выше мысли отнюдь не претендуют на истину в последней инстанции, и мы были бы очень рады любым предложениям по улучшению проведения олимпиад, а также сотрудничеству с любыми заинтересованными людьми. Нас всегда можно найти в лицее N 1511 при МИФИ, тел. 324-55-86.
Ю. КАЛМЫКОВ,
председатель задачной комиссии
Московской городской олимпиады
по информатике
Второй тур московской олимпиады по информатике
Треугольная матрица
Пусть имеется матрица, составленная из равносторонних треугольников и заполненная нулями и единицами (см. пример).
Размер матрицы m*n (где m - число строк, n - число треугольников в строке). Фигурой будем называть часть матрицы, состоящую из треугольников, заполненных единицами. Два треугольника принадлежат одной фигуре, если они соприкасаются друг с другом одной из своих сторон. Треугольник, заполненный единицей и не соприкасающийся своими сторонами ни с одним другим треугольником, содержащим единицу, так же назовем фигурой.
Исходные данные хранятся в текстовом файле следующей структуры:
- в первой строке записаны числа m и n, разделенные пробелом (mЬ14, nЬ14, n - четное);
- в остальных строках - нули и единицы, разделенные пробелами, соответствующие строкам исходной матрицы.
Необходимо:
1) подсчитать количество фигур в матрице;
2) вычислить периметр каждой фигуры (считать длину стороны треугольника равной 1 см);
3) распечатать матрицу на экране, заменив единицы на номера областей и выделив каждую область своим цветом (нули не печатать);
4) программа должна проверять корректность исходных данных.
Пример:
Исходная матрица:
Исходный файл:
Результат работы программы:
Число областей: 4
Периметры областей
1 область - 4 см
2 область - 3 см
3 область -3 см
4 область - 9 см