Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения: Учебное издание. Часть 2
Подождите немного. Документ загружается.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
О .Ф.Ускова
О .Д .Горбенко
А .И . Шашкин
ОЛИМПИАДНЫЕ ЗАДАЧИ ПО
ПРОГРАММИРОВАНИЮ .
ЛУЧШИЕ РЕШЕНИЯ
Часть 2
Учебное издание
ВОРОНЕЖ – 2001
ББК 32.97
УДК 681.3
Олимпиадные задачи по программированию. Лучшие решения. В трех
частях. Часть 2.: Учебное издание/ О .Ф .Ускова, О .Д .Горбенко, А.И.Шашкин –
Воронеж: ООО ПФ «Джуди», 2001 – 44 с.
Работа выполнена в рамках Федеральной целевой программы «Интеграция»
по направлению «Воссоздание студенческих научных школ и олимпиад»
(проект Р0054).
Издается при финансовой поддержке ООО ПФ «Джуди».
ББК 32.97
УДК 681.3
ISBN 5-815-047-0
© Воронежский университет
© Федеральная целевая программа «Интеграция»
© О .Ф .Ускова, О .Д .Горбенко, А.И.Шашкин
© ООО ПФ «Джуди»
О Г Л А В Л Е Н И Е
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1. Общая информация о школе - олимпиаде . . . . . . . . . . . . . . . . . . . . . . . . . .4
2. Задачи с комментариями и решениями . . . . . . . . . . . . . . . . . . . . . . . . . . .
ПРЕДИСЛОВИЕ
Издание подготовлено в рамках проекта Р0054 Целевой Федеральной
программы "Интеграция" по направлению "Воссоздание студенческих
научных школ и олимпиад ". Оно ориентировано в основном на участников
региональной открытой студенческой школы-олимпиады по
программированию и компьютерному моделированию , но может быть
также полезно школьникам старших классов, студентам и учителям
информатики общеобразовательных и профильных учебных заведений .
Организаторами школы -олимпиады являются Воронежский
госуниверситет , Вычислительный Центр Российской Академии Наук (РАН ) и
Воронежский государственный педагогический университет .
В первой части рассматривались задачи предшествовавших олимпиад по
информатике различного уровня (факультетских, вузовских, межвузовских ,
региональных, федеральных). Некоторые задачи приведены с решениями, в
основном разработанными студентами факультета прикладной
математики и механики Воронежского университета, ставшими в свое
время призерами этих олимпиад . Во второй части помимо задач ,
предложенных на олимпиадах различного уровня , представлены материалы
первого (заочного) тура школы -олимпиады.
Воронежский университет , на базе которого проводится школа-
олимпиада, выражает признательность ООО ПФ "Джуди" (директор Андрей
.Васильевич Андрейчиков), оказавшему серьезную поддержку в издании этой
книги.
1. ОБЩАЯ ИНФОРМАЦИЯ О ШКОЛЕ -ОЛИМПИАДЕ
ПОЛОЖЕНИЕ О ПЕРВОМ ТУРЕ
Первый тур школы - олимпиады состоится 17 сентября 2001 года. Его
предусмотрено провести в телекоммуникационном режиме. Если вуз не
подключен к Интернету , то получить задания можно одним из способов:
1. Лично явиться в Оргкомитет школы - олимпиады (Университетская пл., 1,
комн.8)
2. Обратиться в ближайший Интернет-салон (например, на главные почтовые
отделения)
3. Прислать заявку на выдачу задания по электронной почте по адресу
P0054@mail.ru .
Филиалы университета (Лиски , Верхний Мамон, Старый Оскол) получат
задания через представителей университета на местах, в своих учебных отделах.
На первом туре будут предложены 2 задачи : первая - общая, вторая -
учитывающая специальность участников олимпиады. К рассмотрению
принимаются работы , в которых решена хотя бы одна задача.
Оргкомитет предупреждает, что совпадающие друг с другом с точностью до
лексемы программы рассматриваться не будут.
Решения должны быть высланы по электронной почте по адресу
P0054@mail.ru , либо представлены лично в Оргкомитет школы - олимпиады
(Университетская пл., 1, комн.8) до 17 часов 19 сентября 2001 года. В самом
начале программы в качестве вводного комментария необходимо указать
следующие сведения:
- фамилию, имя, отчество автора (полностью );
- представляемый вуз;
- адрес вуза;
- факультет;
- специальность (специализацию);
- форма обучения (вечерняя, заочная);
- фамилию, имя, отчество и ученое звание декана факультета ;
- фамилию, имя, отчество и ученое звание преподавателя , которого автор
считает своим тренером (если такой есть);
- домашний адрес автора программы;
- e-mail, URL, ICQ.
Оргкомитет будет рассматривать работы только студентов вузов.
В первом туре устанавлены следующие номинации для участников:
- студенты 1 курса (независимо от специальности );
- студенты , для которых информатика является профилирующей дисциплиной
(специальности - прикладная математика, математика, механика, физика,
компьютерные науки , САПР, информатика, вычислительные системы,
системное программирование, экономика, экономическая кибернетика,
информационные системы , информационная безопасность);
- студенты , для которых информатика является общеобразовательной
дисциплиной;
- студенты гуманитарных специальностей;
- студенты , специализирующиеся в области искусства, культуры , спорта .
По желанию студенты 1 курса могут перейти в номинацию, отвечающую их
специальности .
З А Д А Н И Я 1 Т У Р А
З а д а ч а
(общая для всех номинаций)
На острове BORLAND каждый из его жителей организовал партию,
которую сам и возглавил. В каждой партии – не менее двух человек. По
Конституции острова в парламент должны войти главы всех партий, но
финансовые трудности не позволяют это сделать. На референдуме граждане
острова решили , что каждую партию в парламенте достаточно представлять
одним членом партии.
Требуется сформировать парламент как можно меньшей численности , в
котором были бы представлены все партии.
Технические требования.
Все главы партий (и партии) перенумерованы от 1 до N (4<=N<=150).
Входные данные.
Первая строка входного текстового файла input.txt содержит N - число
партий, в каждой из последующих строк перечисляются через пробел
порядковые номера граждан – членов соответствующей партии.
Выходные данные.
Выходной текстовый файл output.txt содержит порядковые номера глав
партий, вошедших в парламент.
Пример
Input.txt output.txt
N 4 2
1 2 3 4
2 3
3 1 4 2
4 2
Задачи по номинациям
Номинация «Физкультура и спорт»
В чемпионате региона по футболу участвует 10 команд. В таблице
чемпионата занесены результаты встреч команд друг с другом . В случае
выигрыша команда получает 2 очка, в случае ничьей – 1 очко, в случае
проигрыша – 0 очков. Требуется разработать алгоритм (программу) для :
- построения таблицы чемпионата по данным, вводимым с клавиатуры ;
- вывода этой таблицы (на экран или бумагу );
- определения названий команд, занявших последние три места в чемпионате ;
- определения первой по списку из команд, не имевших ни одной ничьей;
- определения команды-чемпиона.
Номинация «Искусство»
В конкурсе пианистов выступления участников оценивает жюри , в состав
которого входят шесть музыкантов. Максимальная оценка, которую может
выставить каждый член жюри , 10 баллов, минимальная – ноль. Требуется
разработать алгоритм (программу) для
- построения линейной таблицы , содержащей фамилии и инициалы участников,
и прямоугольной таблицы , содержащей оценки каждого члена жюри ;
- определения фамилии участника – победителя конкурса ;
- номер самого строгого члена жюри .
Номинация «Первокурсники»
На Компьютерной улице живут в собственных домах только семьи
Паскалёвых и Сиплюсплюсовых. Они решили переселиться так , чтобы все
Паскалёвы жили в начале улицы , а все Сиплюсплюсовы - в конце . Известно
общее количество домов на улице и кто живет в каждом доме.
Разработайте модель и составьте алгоритм (программу) переселения, при
условии, что каждая семья должна переезжать не более одного раза, а в каждом
обмене должны участвовать только две семьи .
Номинация «Информатика, как общеобразовательная дисциплина»
На Южном полюсе расположены N пронумерованных мете o рологических
станций. Каждая станция соединена с другими станциями линиями связи . В
результате стихийного бедствия некоторые линии связи оказались
нарушенными. Исправность линии связи между I-той и K-той станциями
определяется из целочисленной таблицы NET: элемент с индексами (I,K)
равен 1, если связь между I-той и K-той станциями не нарушена, и 0 - в
противном случае .
Требуется определить, между какими парами станций связь невозможна даже
через цепочки других станций. Создать модель сети станций и разработать
программу для определения пар станций, между которым невозможно
установить связь.
Технические требования
Входными данными являются число станций N и целочисленная
таблица NET размером NxN.
Входные данные берутся из текстового файла INPUT.TXT (его
предварительно нужно создать), в первой строке которого указывается число
станций, в каждой следующей строке - очередная строка таблицы . Результаты -
пары номеров станций - выводятся построчно на экран .
Номинация «Информатика как профилирующая дисциплина»
Требуется смоделировать размещение Т файлов на дискетах так, чтобы число
дискет было минимальным, при условии, что размер каждого файла не
превышает емкости дискеты , и файлы нельзя разбивать на части .
Технические требования.
Входными данными являются число файлов Т и целочисленная таблица
FILES, содержащая размеры файлов. Емкость дискеты считается известной и
равна 1,44 Мб.
Входные данные берутся из текстового файла INPUT.TXT (его
предварительно нужно создать), в первой строке которого указывается число
файлов, в следующей строке - строка таблицы . Результаты – число дискет и
номера файлов на каждой из дискет - выводятся построчно на экран .
Номинация «Студенты гуманитарных специальностей»
Требуется найти и вывести на экран все слова заданного текста , корень
которых вводится с клавиатуры . Текст представляет собой последовательность
слов, разделенных любым числом пробелов. Требуется построить модель,
алгоритм и программу решения поставленной задачи .
Оргкомитет
Открытой региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию
(Президентская целевая программа "Интеграция",
раздел 1.6, проект Р 0054)
Председатель
оргкомитета -
ЗАПРЯГАЕВ Сергей Александрович, Первый проректор
Воронежского госуниверситета , доктор физико-
математических
наук, профессор
Зам .
Председателя -
ШАШКИН Александр Иванович, декан факультета ПММ,
доктор физико-математических наук, профессор.
Члены
оргкомитета :
МИХАЙЛОВ Гурий Михайлович, зам . директора
Вычислительного центра РАН, кандидат физико-
математических наук, г.Москва
ШАКИН Всеволод Владимирович, зав. сектором
Вычислительного центра РАН, кандидат физико-
математических наук, г.Москва
СУРОВЦЕВ Игорь Степанович, начальник управления
профессионального образования и науки Главного управления
образования администрации Воронежской области , доктор
технических наук, профессор
УСКОВА Ольга Федоровна, доцент кафедры математического
обеспечения ЭВМ ВГУ , кандидат технических наук,
координатор проекта
ГОРБЕНКО Олег Данилович, зав.кафедрой математического
обеспечения ЭВМ ВГУ , кандидат физико-математических наук
ПОТАПОВ Александр Сергеевич, проректор Воронежского
госпедуниверситета , профессор
АНТИПОВ Сергей Анатольевич, ректор Воронежского
областного института повышения квалификации и
переподготовки работников образования, доктор физико-
математических наук, профессор
ФЕДОТОВ Владимир Иванович, декан географического
факультета ВГУ , доктор географических наук, профессор
КОСТИН Владимир Алексеевич, декан математического
факультета ВГУ , доктор физико-математических наук,
профессор
КАЗАКОВ Виталий Григорьевич, директор Старооскольского
филиала ВГУ , кандидат педагогических наук
ЛАПЫГИН Дмитрий Рудольфович, зам . генерального
директора ЗАО "РЕТ", г.Воронеж
БАШКИН Виктор Наумович, председатель Совета директоров
ЗАО Торговый дом "Финист", г.Воронеж
ПЕРЕЛЫГИНА Зоя Нестеровна, зав. лабораторией
вычислительной техники ВГУ
ЧЕРНЫХ Нина Петровна, кандидат физико-математических
наук, руководитель регионального центра фирмы «Мирра-
Люкс»
КРАСНЕР Илья Наумович, директор Центра правовой
информатики Министерства юстиции РФ по Воронежской
области
Секретариат олимпиады
КРОВЯКОВА Валентина Алексеевна, лаборант кафедры ММИО
ТЮНИНА Лидия Николаевна, инженер ЛВТ
МЕНЬШИКОВА Ольга Ивановна, секретарь деканата факультета
ПММ
Студенческий директорат
ЯКУБЕНКО Адрей, магистрант 1 года обучения
ВАХТИН Алексей, магистрант 2 года обучения
ПОЛЯКОВ Андрей, магистрант 1 года обучения
ЕФРЕМОВ Максим, магистрант 1 года обучения
МХИТАРЯН Лусине, магистрант 1 года обучения
РОМАЩЕНКО Алексей, магистрант 1 года обучения
Жюри
Открытой региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию
Председатель
жюри -
ГОРБЕНКО Олег Данилович, зав. кафедрой математического
обеспечения ЭВМ ВГУ , кандидат физико-математических наук
Зам .председат
еля -
УСКОВА Ольга Федоровна, доцент кафедры математического
обеспечения ЭВМ ВГУ , кандидат технических наук
Члены
жюри :
МИЛОВСКАЯ Людмила Серафимовна, доцент кафедры
информатики ВГПУ , кандидат физико-математических наук
КУЛАПИН Леонид Генрихович, директор центра ИНТЕРНЕТ,
кандидат физико-математических наук
ВОРОНИНА Ирина Евгеньевна, зам . директора научно-
методического центра по компьютерной лингвистике, кандидат
технических наук, доцент
МЕЛЬНИКОВ Вадим Митрофанович, преподаватель кафедры
математического обеспечения ЭВМ ;
СЕЛЕЗНЕВ Константин Егорович, преподаватель кафедры
математического обеспечения ЭВМ ;
АЗНАУРЬЯНЦ Александр Владимирович, генеральны
й директор
Центрально-Черноземного представительства корпорации
"ПАРУС", г.Воронеж
Cпонсоры открытой региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию
Администрация Воронежской области
Центрально-Черноземное представительство корпорации "ПАРУС", г.Воронеж
(Руководитель - А.В .Азнаурьянц)
ЗАО "РЕТ", г.Воронеж (Генеральный директор В .М .Колыхалин)
ЗАО ПКФ "Воронежский керамический завод " (генеральный директор
Горемыкин В.А.)
Торговый дом "Финист", г.Воронеж (Председатель совета директоров
В .Н .Башкин)
Косметическая фирма NINELLE, Испания (Бренд-менеджер компании по ЦЧЭР
Г.Иванова)
ЗАО "РЕЛЭКС", г.Воронеж (Генеральный директор И.А.Бойченко)
ЗАО НЭКС, г.Воронеж (Генеральный директор Г.В.Пономарев)
Фонд С .Г.Крейна
Оскольский электро-металлургический комбинат Белгородской области
Филиал Гута - банка в г.Ст.Оскол Белгородской области
Российская Ассоциация "Женщины в науке и образовании" (Президент
Ассоциации профессор МГУ Г. Ю . Ризниченко)
Российская Ассоциация "Женщины -математики " (Президент Ассоциации
доцент ВГУ И.С . Гудович)
Кондитерская фабрика "Славянка" г. Ст. Оскол Белгородской области
( Директор С .А.Гусев)
Региональный центр фирмы «Мирра-Люкс» (Руководитель Н . П . Черных)
ЗАО "Кедр+" , г.Воронеж. (Директор Ю .П.Листрова, канд. физико-
математических наук, доцент)
ООО ПФ "Джуди" (Директор А.В.Андрейчиков)
Старооскольский технологический институт (филиал МИСиС)
Компания "Информсвязь- Черноземье " (Директор Б .И.Даньшин)
ООО Интеркон (Руководитель А . В . Осипов)
Финансовая группа "Спасские ворота ", филиал в г.Воронеже
Компания "Oriflaime" (Швеция)
Фирма "Компьютерные технологии"(руководитель И . И . Окунев)
Информационная поддержка открытой региональной
студенческой школы -олимпиады по программированию и
компьютерному моделированию
Воронежское государственное радио
Газета "Известия" (Региональный выпуск )
Общественно-политический еженедельник "Донъ"
"Газета с улицы Лизюкова"
Газета "Молодой коммунар"
Газета "Воронежский университет"
Газета "Компьютерное чтиво"
Газета «Факультет ПММ»
ООО ПФ "Джуди"
Газета "Компьютерра"
Результаты 1 тура открытой региональной студенческой школы -олимпиады по
программированию и компьютерному моделированию