ББК 32.973.26-018.1

Д 21

Д 21 Даулеткулов А.Б. Олимпиады по информатике: Учебно-методическое пособие. -Алматы: ИНТ,

2004 - 242 c.

ISBN 9965-9293-5-1

Олимпиады по информатике среди школьников проводятся с середины 80-х годов. С начала 90-х

годов основными условиями победы на олимпиадах по информатике принято считать успешную отладку на ЭВМ программ, решающих конкурсные задачи.

Книга ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ состоит из трех частей.

В первой части приведены задачи международных, республиканских и городских олимпиад по информатике среди школьников, а также задачи, использованные при подготовке сборных команд Казахстана по информатике. Рассмотрен ход решения и типичные ошибки.

Во второй части рассматриваются вопросы, связанные с технической, тактической и психологической подготовкой учащихся к соревнованиям.

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

Рецензенты:

Ускенбаева Р.К. – кандидат технических наук, доцент, заведующая кафедры информатика КАзНТУ им. К.И.Сатпаева.

Мухамбетжанова С.Т. – кандидат педагогических наук, заведующая кабинетом информатики

РИПК СО МОН РК.

ББК 32.973.26-018. Д 00(05) - Институт новых технологий, ISBN 9965-9293-5- 2004 г Даулеткулов А.Б., 2004 г

ОТ АВТОРА

Предисловие к первому изданию Все началось весной 1993 года — именно тогда в Республиканском Центре Новых Информационных Технологий Министерства образования Республики Казахстан шло формирование жюри Республиканской олимпиады по информатике среди школьников. Больших трудов стоило мне осуществить свою школьную мечту — участвовать в Республиканской олимпиаде. Так впервые я принял участие в олимпиаде по информатике (как член жюри) и впервые написал две задачи для школьников.

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

Предлагаемая Вашему вниманию книга — попытка поделиться с Вами теми наблюдениями и мыслями, которые стали результатом участия в городских, республиканских и международных олимпиадах, работы в “Школе юного программиста” и со сборными командами Казахстана среди школьников по информатике.

Я выражаю свою искреннюю признательность своим старшим коллегам: В.М.Котову и И.А.Волкову (Белоруссия), профессору В.А.Каймину (г. Москва), В.В.Харасахалу и Б.К.Накисбекову (г. Алматы); моему другу И. Пашину (г. Темиртау); замечательному человеку, подвижнику олимпиадного движения Э.С.Ратобыльской (Белоруссия); членам жюри, руководителям команд и всем, кто занимается этим прекрасным и увлекательным делом, а так же моим ученикам - членам сборных команд Республики Казахстан 1993, 1994, 1996, 1997 годов. Благодаря вам, друзья, появилась эта книга.

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

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

К сожалению, в последнее время олимпиадное движение Республики имеет ряд недостатков.

Лакмусовой бумагой неблагополучия в этом являются результаты выступления наших школьников на Всемирных олимпиадах по информатике. Анализ работ и результатов городских, областных, республиканских олимпиад школьников по информатике указывает на низкий уровень подготовки учащихся к олимпиадам по информатике. Отсутствие базовых знаний, умений и навыков. Это, на мой взгляд, обусловлено рядом объективных и субъективных причин(на IOI-2007 команда Казахстана заняла 3-е общекомандное место. прим. автора).

Предлагаемое Вашему вниманию второе издание книги “Олимпиады по информатике” несколько отличается от первого издания. Во-первых, в него вошли новые задачи. Во вторых, небольшим изменениям подверглась вторая часть книги, связанная с технической подготовкой. Третья часть книги практически не изменилась, так как опыт прошедших пяти лет показал правильность идей и методологии заложенных в ней.

Автор будет рад если эта книга окажет помощь в подготовке к олимпиадам по информатике и привлечет в олимпиадное движение новых ребят. Замечания и пожелания направляете по адресу [email protected]. Успехов Вам.

Искренне Ваш Даулеткулов Алдияр.

Часть I Олимпиадные задачи

ВВЕДЕНИЕ

Олимпиада - невидимый накал страстей: взлеты и падения, надежды и разочарования, слезы и радость, поражения и долгожданная победа. Все это крутится вокруг одного - Ее Величества Задачи.

Олимпиадные задачи - это особый мир, в каждой из них (я имею в виду настоящую олимпиадную задачу) есть своя изюминка, которая является ключом к решению. В этом смысле тот, кто решает задачу, подобен сыщику, распутывающему сложное дело. Все улики налицо, но часть из них ложные, а часть - может привести к решению. Сможете ли Вы как Шерлок Холмс разгадать замысел автора задачи или пойдете по ложному следу?

Перед началом чтения несколько советов.

Советы для учащихся Совет 1. Не торопитесь читать решение задачи. Попробуйте решить задачу самостоятельно.

Совет 2. Перед решением задачи внимательно прочитайте условие, выявите неясные места, сформулируйте вопросы и запишите их.

Совет 3. Попробуйте придумать тесты для проверки правильности решения.

Совет 4. Больше времени работайте без компьютера, записывайте все свои мысли и алгоритмы решения на бумаге - это поможет Вам разобраться, что и почему Вы упустили из виду в случае неудачи.

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

Совет 6. Не огорчайтесь, если Вы не смогли полностью решить задачу. Х.Р. Капабланка сказал:

“Мало есть выигранных мною партий, которые научили бы меня столько, сколько мои проигрыши” Совет 7. Не зазнавайтесь, если решили все правильно - у автора всегда найдется “камень за пазухой”.

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

Совет 2. Задачи приведены в хронологическом порядке, то есть по времени их использования или написания, поэтому Вы можете рассматривать их в любом порядке. Однако тему “лабиринты” лучше рассматривать в порядке, представленном в книге.

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

Совет 4. Смотри Совет 1.

Совет для Всех. Можно не слушать мои советы.

Если Ваша программа успешно прошла все тесты, но Ваше решение задачи отличается от подхода, предложенного в книге, пожалуйста, опишите это решение и пришлите мне.

1.1 Две очень “простые” задачи С этой задачи я, обычно, начинал первое занятие в “Школе юных программистов”. Она предлагалась на тренировочных сборах сборной команды СССР по информатике.

Задача 1.

Условие задачи: Дана сфера радиуса R, центр которой находится в центре координат. Необходимо определить количество точек, находящихся в сфере, с целочисленными координатами. Если точка лежит на поверхности сферы, то ее надо учитывать.

Как правило, первым ребята предлагают следующий вариант решения :

var R,x,y,z :integer;

Begin readln(R);

S:=0;

if (sqr(x)+sqr(y)+sqr(z))

Символ - площадь < SL>

ТЕХНИЧЕСКИЕ ОГРАНИЧЕНИЯ

2. Имя входного ASCII файла должно быть “TESTx.TXT”, где х - номер варианта.

3. Имя выходного ASCII файла должно быть “ANSx.TXT”, где х - номер варианта.

4. Рабочая программа должна быть представлена в виде исполняемого модуля с именем “УХХХ.ехе” или виде текстового файла (для интерпретатора Бейсик) с именем “УХХХ.BAS”, где У номер класса, ХХХ - номер участника.

5. Время прохождения одного теста - не более 10 минут.

Пример 1.

********** *1111***** 1****1*** *11111**** ********** С данной задачей у автора связано несколько неприятных воспоминаний. В первоначальном варианте задачи разные острова могли обозначаться одинаковыми символами. Один изпредполагаемых тестов как раз и был подготовлен для проверки умения различать эти острова. Однако за час до начала тура, еще раз просматривая условие задачи, я обнаружил следующее - если строго следовать духу задачи, то, при наличии этого условия, появляется побочное решение. Участник может заявить, что каждый единичный символ является отдельным островом (таков масштаб карты!!!), и ему просто надо определить, какие символы используются и приписать им площадь, равную единице.

1.7 Опять вода Очень часто толчком к написанию задачи является эпизод или отрывок из какой либо книги. Не была исключением и предлагаемая Вам следующая задача.

ТРИ ДОКУМЕНТА

Матчевая встреча сш 28, РСФМШИ, “Школа юного программиста» РЦ НИТ, Алматы, 1995г., автор Извлеченные из бутылки клочки бумаги были наполовину разъедены морской водой. Из почти расплывшихся строк еле-еле можно было разобрать кое-какие непонятные слова. В течение нескольких минут Гленарван внимательно рассматривал клочки. Он поворачивал их то так, то сяк, разглядывая на свет и изучая малейшие следы уцелевших слов, которые пощадило море...

...- А можно уловить смысл документа? - спросила леди Гленарван.

- Трудно утверждать что-нибудь определенное, дорогая Элен, уцелевшие слова слишком отрывочны.

- А может быть, они дополняют друг друга? - спросил майор.

- Несомненно, - ответил Джон Манглс. - Вряд ли морская вода уничтожила во всех документах одни и те же слова. Сличая сохранившиеся обрывки фраз, мы, в конце концов, доберемся до их смысла.

К Вам попала бутылка с сообщением. Бросивший ее в море, для страховки написал текст сообщения несколько раз. Но листки с текстами оказались сильно подпорчены морской водой: она смыла не только часть букв, но и испортила бумагу. У вас есть N клочков бумаги (разной величины), на которых находится текст одного и того же документа. Часть букв в них стерта. Обрывки документов находятся во входном файле “TESTх.TXT” (Х - номер варианта теста). Входной ASCII файл имеет следующий формат (Пример 1):

Z1 (текст на первом клочке);

Z2 (текст на втором клочке);

ZN (текст на N-том клочке).

ПОСТАНОВКА ЗАДАЧИ

Написать программу, которая выполняет следующие действия:

1. Вводит с клавиатуры имя входного файла.

2. Считывает из входного файла части документа.

3. Восстанавливает исходный текст документа.

4. Выводит в выходной файл текст исходного документа.

ТЕХНИЧЕСКИЕ ОГРАНИЧЕНИЯ

K-я строка файла (характеристики последней упряжки последнего участника)

ПОСТАНОВКА ЗАДАЧИ

Написать программу, которая выполняет следующие действия:

1. Вводит с клавиатуры имя входного файла.

2. Считывает из входного файла.

3. Определяет оптимальное использование упряжек на трассе и победителя гонки.

4. Вводит в выходной файл:

- номер победителя (1-я строка файла);

- номер 1-й упряжки, пробег в км, скорость (2-я строка файла);

.........

- номер n -й упряжки, пробег в км, скорость (n+1-я строка файла);

- в случае невозможности доехать до финиша, выдает сообщение: “Нет решения”.

ТЕХНИЧЕСКИЕ ОГРАНИЧЕНИЯ