Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
Центрально-
Черноземное представительство корпорации "ПАРУС",
г.Воронеж
ЗАО "РЕТ", г.Воронеж
Завод керамических изделий, г.Воронеж
Торговый дом "Финист", г.Воронеж
Косметическая фирма NINELLE, Испания
ЗАО "РЕЛЭКС", г.Воронеж
Спецгормолзавод "Лискинский", г.Лиски , Воронежской области
ЗАО НЭКС, г.Воронеж
Фонд С.Г.Крейна
АОО “Маслосырзавод”, с.Верхний Мамон Воронежской области
Оскольский электро-металлургический комбинат Белгородской
области
Филиал Гута - банка в г.Ст.Оскол Белгородской области
Российская Ассоциация "Женщины в науке и образовании"
Российская Ассоциация "Женщины -математики "
Кондитерская фабрика "Славянка" г. Ст. Оскол Белгородской
области (Директор С .А.Гусев)
Региональный центр фирмы «Мирра-Люкс»
ЗАО "Кедр+" , г.Воронеж. (Директор Ю .П.Листрова, канд. физико -
математических наук, доцент)
ООО ПФ "Джуди" (Директор А.В.Андрейчиков)
Управление профессионального образования и науки Главного
управления образования администрации Воронежской области
учредило призы для студентов – участников школы -олимпиады –
из малообеспеченных семей.
Семья Н . Я . Краснера учредила приз памяти Наума Яковлевича
(1924 – 1999) для участника школы -олимпиады , показавшего
лучшие результаты в разделе экономика и экономическая
кибернетика по итогам второго тура. Н .Я .Краснер – один из
ведущих организаторов науки на факультете ПММ, видный
ученый в области применения математических методов в
экономике , организатор кафедры математических методов
исследования операций .
Региональный центр фирмы «Мирра-Люкс» учредил призы
участницам школы - олимпиады за лучший компьютерный дизайн
реализации задания первого тура.
Управление профессионального образования и науки Главного
управления образования администрации Воронежской области
учредило призы для студентов–инвалидов - участников первого и
второго туров школы -олимпиады .
Фирма «РЕТ» учредила призы для студентов - победителей
школы -олимпиады - специализирующихся в области прикладной
математики и информатики.
Центр правовой информатики Министерства юстиции РФ по
Воронежской области учредил приз для участника школы -
олимпиады , показавшего лучшие результаты в разделе
юриспруденция по итогам второго тура.
Ректорат Воронежского госуниверситета планирует выделить
бесплатные путевки для отдыха на турбазах России, а также
санаторно - курортные путевки восьми студентам Воронежского
университета, показавшим наилучшие результаты в олимпиаде.
Ректорат Воронежского госуниверситета планирует выделить
бесплатные путевки для санаторно - курортного лечения всем
студентам-инвалидам Воронежского университета – участникам
школы -олимпиады и поощрить их денежным вознаграждением.
Кондитерская фабрика «Славянка» (г . Старый Оскол
Белгородской области) планирует поощрить участников первого
тура из г . Старый Оскол, показавших хорошие результаты в
олимпиаде.
Ассоциация «Женщины в науке и образовании» выделила приз
участнику первого тура, первым приславшему правильное решение
заданий первого тура независимо от номинации.
Ассоциация «Женщины - математики» выделила приз участнице
первого тура, представившей оригинальное решение заданий
первого тура независимо от номинации .
Фонд профессора С .Г.Крейна выделил приз участнику первого
тура, показавшему наилучшие результаты в разделе математика.
Спецгормолзавод "Лискинский" ( г .Лиски, Воронежской области)
планирует поощрить участников первого тура из г . Лиски,
показавшим хорошие результаты.
АОО “Маслосырзавод” ( с.Верхний Мамон Воронежской области)
планирует поощрить участников первого тура из с. Верхний
Мамон, показавшим хорошие результаты.
ЗАО НЭКС ( г .Воронеж) планирует поощрить участников
второго тура, показавших хорошие результаты в
нематематических разделах.
ЗАО "Кедр+" планирует поощрить декана факультета любого
вуза, студенты которого приняли наиболее активное участие в
школе -олимпиаде.
Воронежский госуниверситет учредил призы студентам ,
показавшим хорошие результаты в олимпиаде
- геологический факультет : по направлению геология
и геофизика;
- физический факультет : по направлению физико -
математические науки;
- факультет компьютерных наук : по направлению
компьютерные науки;
- математический факультет : по направлению
математика;
- биолого -почвенный факультет : по направлениям
биология и почвоведение ;
- химический факультет : по направлениям химия и
медицина ;
- юридический факультет : по направлению
юриспруденция ;
- факультет романо - германской филологии: по
направлению компьютерная лингвистика;
- исторический факультет : по направлению
историческая информатика;
- филологический факультет : по направлению
гуманитарные науки;
- факультет философии и психологии: по
направлениям философия и психология;
- экономический факультет : по направлению
экономика;
- факультет прикладной математики и механики:
по направлениям программирование и
компьютерное моделирование .
Ректорат Воронежского государственного педагогического
университета планирует поощрить студентов периферийных
педагогических вузов (Мичуринского, Борисоглебского, Елецкого ),
показавших хорошие результаты в олимпиаде.
Приглашаем к сотрудничеству любые предприятия любых форм
собственности. Реклама о Вашем предприятии будет размещена
на страницах олимпиадного сайта www.main.vsu.ru/~pmmmo, а
также на страницах печати
Банковские реквизиты :
ВГУ
ИНН 3666029505
Р/с 40503810313002000067
Центрально-Черноземный банк Сбербанка РФ
г.Воронежа
БИК 042007681 к/с 3010181060000000068
Код ОКПО 02068120
Код ОКОНХ 92110
В платежном поручении указать НИЧ-1069 (Ускова О .Ф.)
Информационная поддержка открытой региональной
студенческой школы - олимпиады по программированию и
компьютерному моделированию
"Газета с улицы Лизюкова"
Газета "Молодой коммунар"
Газета "Воронежский университет"
Газета "Компьютерное чтиво"
Газета «Факультет ПММ»
ООО ПФ "Джуди"
2. ЗАДАЧИ ПО ИНФОРМАТИКЕ, ПРЕДЛАГАВШИЕСЯ
НА ОЛИМПИАДАХ ПРОШЛЫХ ЛЕТ
Следующая группа задач предлагалась на университетской
олимпиаде студентов по информатике в 1997 году.
Задача 1. "Телефонная связь"
Поселок состоит из N домов, расположенных вдоль прямой
дороги с одной стороны на равных расстояниях. Дома
пронумерованы последовательно: 1, 2, 3,..., N. В поселке проводят
телефонную связь. В таблице Т указано, сколько телефонных
аппаратов надо установить в каждом доме. Расстояние между
двумя соседними домами считается равным единице .
Задание.
Создать программу для определения номера дома, в котором
надо установить АТС , чтобы суммарное расстояние от АТС до
всех телефонных аппаратов было минимальным. Если таких домов
несколько , достаточно найти любой. Каждый телефон связан с
АТС отдельным проводом .
(Под расстоянием до телефонного аппарата подразумевается
расстояние до дома, в котором будет установлен аппарат.
Расстояние от АТС до телефонного аппарата , установленного в
доме, где стоит АТС , считается равным нулю .)
Технические требования.
Входные данные берутся из текстового файла input1.txt, первая
строка которого содержит число домов, вторая - линейную таблицу
Т. Исходные данные корректны , их проверка не требуется.
Выходные данные - номер дома, где нужно поставить АТС , и
суммарное расстояние до всех телефонных аппаратов - выводятся
на экран .
Пример входных данных Пример выходных данных
6 АТС - в доме 4
1 0 3 1 1 3 Суммарное расстояние - 13
Задача 2. " Функция "
Целое положительное число М записывается в двоичной
системе счисления, затем разряды переставляются в обратном
порядке . Получившееся число принимается за значение функции
В(М).
Задание. Создать программу для вывода в текстовый файл
OUT.TXT значений функции В(М) на отрезке [512,1023].
Задача 3. "Считалка"
Вокруг считающего стоят N человек, один из которых назван
первым, а остальные занумерованы по часовой стрелке числами от
2 до N. Считающий ведет счет до М, начиная с первого. Человек,
на котором остановился счет, выходит из круга. Счет вновь
начинается со следующего за выбывшим человека (при этом
выбывшие из круга не считаются) и так до тех пор, пока не
останется один человек.
Задание. Определить начальный номер оставшегося человека.
Технические требования .
Входными данными являются числа N и M, которые вводятся
с клавиатуры . Результат - номер оставшегося человека –
выводится на экран .
Пример входных данных Пример выходных данных
5 3 Номер оставшегося - 4
Следующие задачи предлагались на городской студенческой
олимпиаде по информатике в 1997 году.
Задача 4. "Многоугольник "
Выпуклый многоугольник на плоскости задан
целочисленными координатами своих вершин. Требуется
подсчитать количество точек с целочисленными координатами,
лежащих на границе многоугольника.
Задание.
Создать программу для вычисления требуемого количества
точек (для каждого из двух указанных случаев).
Технические требования .
Входными данными являются число вершин многоугольника
и их координаты в порядке обхода по часовой стрелке .
Координаты вершин - целые числа и по модулю не превосходят
1000000.
Входные данные берутся из текстового файла INPUT4.TXT,
в первой строке которого указывается число вершин
многоугольника, в каждой следующей строке - пара координат.
Результаты выводятся на экран .
Исходные данные корректны , их проверка не требуется.
Пример входных данных Выходные данные
4 80
-10 -10
-10 10
10 10
10 -10
Задача 5. «Метеостанции»
На Южном полюсе расположены N пронумерованных
мете o рологических станций. Каждая станция соединена с другими
станциями линиями связи . В результате стихийного бедствия
некоторые линии связи оказались нарушенными. Исправность
линии связи между I-той и K-той станциями определяется из
целочисленной таблицы NET: элемент с индексами (I,K) равен
1, если связь между I-той и K-той станциями не нарушена, и 0 - в
противном случае .
Требуется определить, между какими парами станций связь
невозможна даже через цепочки других станций.
Задание.
Создать программу для определения пар станций, между
которым невозможно установить связь.
Технические требования.
Входными данными являются число станций N и
целочисленная таблица NET размером NxN.
Входные данные берутся из текстового файла INPUT5.TXT,
в первой строке которого указывается число станций, в каждой
следующей строке - очередная строка таблицы . Результаты - пары
номеров станций - выводятся построчно на экран .
Исходные данные корректны , их проверка не требуется.
Пример входных данных Выходные данные
4
1 1 0 1 1 3
1 1 0 0 2 3
0 0 1 0 3 4
1 0 0 1
Задача 6. «Скобки»
Дано арифметическое выражение, состоящее из букв ,
однозначных чисел, знаков арифметических операций и скобок,
записанное в общепринятой форме. Требуется удалить из
выражения лишние пары скобок (то есть пары , не влияющие на
порядок выполнения операций).
Задание.
Создать программу для удаления из заданного выражения
лишних пар скобок.
Технические требования.
Исходная строка с выражением вводится с клавиатуры .
Результат - упрощенное выражение - выводится на экран .
Пример входных данных Выходные данные
((6/2)*А+(8-5))/(E) (6/2*A+8-5)/E
Задача 7. «Криптограмма»
Текст закодирован с помощью сетки , представленной на
рисунке , где цифрой 0 обозначено отверстие. Для того, чтобы
раскодировать сообщение (криптограмму), нужно наложить сетку
на текст так, чтобы в отверстия можно было видеть символы
закодированного текста . Первый раз сетка накладывается так,
чтобы сторона, отмеченная знаком "+", была верхней, затем сетка
поворачивается по часовой стрелке на 90 градусов, читается
следующий набор символов, и т.д . до полного оборота сетки на 360
градусов.
+
1 0 1 0 1 0
1 1 1 1 0 1
1 1 0 1 1 1
1 0 1 1 0 1