Олимпиада по программированию в ШГПИ

Олимпиада по программированию проводится 25 марта 2010 года с 11.00 до 17.00 (с перерывом на обед с 13.00 до 14.00) в аудитории 219А. Подготовка олимпиадных заданий и проверка решений возлагаются на комитет олимпиады, в состав которого входят Пирогов В.Ю., к.ф-м.н, профессор, зав. кафедрой прикладной информатики и экономики Шадринского пединститута и Слинкин Д.А., к.п.н, доцент, начальник вычислительного центра Шадринского пединститута.

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

На всех компьютерах обеспечена двойная загрузка, с возможностью выбора операционных систем Linux (AltLinux 4.1 или AltLinux 5.0) и Windows XP со следующим набором языков и систем программирования:

Каждое решение должно включать в себя исходный и (если это возможно) исполняемый код. В заголовке каждого файла исходного кода должны быть приведены идентификационные данные студента (ФИО, город, вуз, курс, группа), а также используемая операционная система и среда (язык) программирования.

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

Для Windows:

Для Linux:

По окончании работы студент должен обратиться к сотруднику комитета олимпиады с просьбой зафиксировать результаты.

Подведение предварительных итогов олимпиады запланировано на 26 марта 2010 года, 9.00. Информация о предварительных результатах будет опубликована в аудитории 219А, а также на интернет-форуме ШГПИ .

С 9.00 до 11.00 26 марта 2010 года каждый студент может подать апелляцию оргкомитету олимпиады. При возникновении разногласий между студентом и оргкомитетом олимпиады, суть претензий студента и спорный программный код будут выложены для общего обсуждения на интернет-форум ШГПИ.

С 11.00 до 12.00 26 марта 2010 года оргкомитет олимпиады вынесет решения по апелляционным требованиями и опубликует окончательные итоги олимпиады в аудитории 219А, на интернет-форуме и веб-портале ШГПИ (http://shgpi.edu.ru).

С 12.00 до 13.00 26 марта 2010 года — разбор решений олимпиадных задач.

14.30 26 марта 2010 года - официальное оглашение результатов, награждение победителей ценными призами и подарками, предоставленными оргкомитетом студенческого научно-практического форума.

Условия олимпиадных задач.

Окружности

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: 2

На плоскости расположено некоторое количество окружностей разных радиусов. Некоторые окружности накладываются друг на друга. Определить количество наложений для каждой из окружности.

Исходный (входящий) файл (input.txt) содержит в каждой строке координаты и радиус для каждой окружности в формате x y r. Например

2 4 5
1 2 10
4 20 1
1 3 3
5 6 10
10 10 2

Выходной файл (output.txt) содержит координаты, радиус и количество наложений для каждой окружности. Строки должны быть упорядочены по возрастанию количества наложений. Для выше представленного входного файла input.txt имеем выходной файл

4 20 1 0
10 10 2 1
2 4 5 3
1 2 10 3
1 3 3 3
5 6 10 4

Замечание.

Отсутствие данных должно генерировать в выходном файле сообщение об ошибке, начинающееся со слова "Error".

Сравнение текстов

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: 4

Существуют разные подходы сравнения двух текстов для выявления их подобия. Выберем следующий простой подход: сравнение предложений в каждом тексте.

Пусть даны два текста T1 и T2. Необходимо найти все предложения текста T1 которые имеются и в тексте T2. При этом сравниваются слова предложений и игнорируются знаки препинания, пробелы и управляющие символы. Предложения друг от друга отделяются символами ".", "!", или "?".

Входной поток (файл) содержит и текст T1 и текст T2, разделенных символом '*'. Слова в текстах могут состоять из английских букв (заглавных и прописных) и цифр. Заглавные и прописные буквы не различаются, т.е., например 'A'='a'. Между словами могут стоять пробелы, знаки препинания, управляющие и другие символы. Тире считается знаком препинания (т.е. перенос слов не предполагается).

Два предложения

The
two nations    are evenly matched, but have very different strengths.

The
two nations are evenly matched but have very different strengths. 

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

Пример

Входной файл (input.txt). Содержит два текста, разделенных знаком '*'.

The embargo, is
strengthened when the Danes seize Hamburg, the main harbour for
British,
trade with the German
states.
Third parties
suffer as much as anyone from this form of economic.
warfare, particularly
after Britain adopts the policy of seizing goods.
carried by the ships of
neutral nations if they are destined for a
harbour under blockade.
They declare       
the Baltic ports out
of bounds to British
ships..
*
Indignation at this
British policy, heightened
by diplomatic pressure
from Napoleon, prompts Russia, Sweden and Denmark
to form in December
1800 a League of Armed Neutrality. They declare the
Baltic ports out of
bounds to.
British ships..
The embargo is
strengthened when the Danes seize Hamburg, the main
harbour for British
trade with the German states. Britain responds by
sending a naval fleet
into the Baltic. They declare,,,       
the Baltic ports out
of bounds to British
ships.. The second-in-command is Nelson,
who sails into shallow
and well defended waters in Copenhagen harbour.
There is heavy
fighting, during which the commander of the fleet flies
the signal for Nelson
to withdraw (this is the famous occasion when he
puts the telescope to
his blind eye)..

Выходной файл (output.txt) содержит предложения из первого текста, которые имеют совпадающие предложения во втором тексте.

The embargo, is strengthened when the Danes seize Hamburg, the main harbour for British, trade with the German states.

They declare the Baltic ports out of bounds to British ships.

Замечание 1.

Если не найдено ни одного предложения, то в выходной файл должен быть выведен символ *.

Замечание 2.

При написании программы нельзя использовать регулярные выражения.

Оплата обучения

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 8

Условие задачи навеяно воспоминаниями о разработке бухгалтерского модуля для системы управления базами данных ШГПИ, который успешно функционирует с 2004 года.

Некоторое учебное заведение принимает студентов на коммерческой основе. Студент может обучатся сразу на нескольких специальностях, на каждую из которых с ним заключается отдельный договор. Каждый студент обучается 3 года и должен ежегодно оплачивать обучение. Стоимость года обучения фиксируется в договоре со студентом. Студент может оплачивать свое обучение частями, причем, не оплатив полностью текущий год, он не имеет права оплачивать следующий. Если студент вносит за текущий год сумму, превышающую стоимость данного года обучения, то остаток переносится на следующий(е) год(ы). Задача заключается в поиске должников на определенный год.

Исходный файл input.txt состоит из четырех наборов строк. Наборы отделены друг от друга пустой строкой.

Первый набор состоит из одной строки и содержит год, для которого производится поиск должников.

Второй набор (студенты) состоит из произвольного количества непустых строк, в каждой из которых содержится ФИО студента.

Третий набор (договора) состоит из произвольного количества непустых строк, в каждой из которых содержатся через разделители порядковый номер студента, специальность, год поступления, стоимость года обучения.

Четвертый набор (оплаты) состоит из произвольного количества непустых строк, в каждой из которых содержатся через разделители порядковый номер договора, год обучения (за который вносится оплата), сумма оплаты. Данный набор может полностью отсутствовать.

Результирующий файл output.txt должен содержать кол-во рублей, которые должен студент учебному заведению за указанный год (без учета долгов прошлых лет), либо 0, если долг отсутствует или имеет место быть переплата.

Пример input.txt:

2007

федя
вася

1 информатика	2007	10000
1 экономика	2008	12000
2 физика	2006	9000

1 1 900
3 1 15000
1 1 9000
3 2 4000
2 1 15000

Пример файла output.txt:

100
0

Расшифровка:

Студент "федя" поступил в 2007 на специальность "информатика", а через год - дополнительно (или перевелся - история об этом умалчивает) на специальность "экономика". В 2007 году он два раза оплачивал свое обучение на специальности "информатика", первый раз - 900, второй раз - 9000 рублей, оставшись при этом должным за 2007 год 100 рублей. В 2008 году он оплатил обучение по специальности "экономика", с переплатой в 3000 рублей (эти данные являются несущественными, т.к. анализируется только состояние на 2007 год). Таким образом студент "федя" имеет на 2007 долг перед учебным заведением по оплате обучения размером в 100 рублей.

Студент "вася" поступил в 2006 на специальность "физика". В 2006 году он оплатил обучение, с переплатой в 6000 рублей. В 2007 году он оплатил обучение в сумме 4000 рублей, что, с учетом переплаты 2006 года, полностью покрывает стоимость обучения за 2007 год, и обеспечивает аванс в 1000 рублей на 2008 год (эти данные уже являются несущественными, т.к. анализируется только состояние на 2007 год). Таким образом студент "вася" на 2007 год не имеет долгов перед учебным заведением по оплате обучения.

Игра в числа

Автор: Пирогов В.Ю.
Максимальное кол-во баллов: 10

Игра в числа кажется на первый взгляд не сложной. Однако с увеличением размера поля игры количество вариантов резко возрастает до огромных значений. В результате решать задачу в лоб, т.е. перебором всех вариантов, для выбора оптимального решения уже при размере, скажем 10*10 дело весьма трудоемкое. Впрочем, можно упростить задачу, просчитывая, скажем, на 5 ходов вперед. Но обо всем по порядку.

Игра происходит на квадратном поле, разделенном на клетки. Если размер поля N, то количество клеток т.о. равно N*N. Играют два игрока. Будем называть их A и B. Игроки по очереди выбирают клетки с целыми числами, набирая таким образом очки. Числа в выбранных клетках выходят из игры. Задача игроков набрать в конце игры большее число очков. Правила очень просты. Один игрок может выбирать только по строкам, а другой по столбцам. Причем выбор можно осуществлять только в строке (столбце), где был последний ход противника. Игрок, ходящий первым, может выбирать любую клетку.

Рис.1. Игра в числа.

Обратимся к рисунку 1. В нем показана одна из возможных игр участников A и B на поле размером 3*3. Как видим, было сделано всего 6 ходов (каждый сделал по три хода). Выигрыш достался игроку B. Заметим, что даже для такого маленького поля количество вариантов составляет 24. Для поля же размером 4*4 количество вариантов игры составляет уже более 4000 (!).

Задание.

Программа на входе (input.txt) получает информацию о исходных данных игры (см. ниже).

8
1 8
0 8 1 3 7 8 1 3
5 0 4 2 1 2 2 2
8 0 1 3 7 3 3 1
1 7 3 3 6 7 4 5
3 0 7 2 7 6 5 1
3 0 6 5 4 4 6 1
3 1 7 1 4 2 1 5
9 2 3 1 5 6 8 6

Первая строка — размер поля (в примере - 8), вторая строка — ход игрока A (в примере 1 8), и само игровое поле, заполненное числами. Программа должна просчитать возможные варианты игры на пять ходов вперед. На выходе должно быть число вариантов, в которых после пяти ходов выигрывает игрок B (заметим, что пятый ход делает игрок A). Сами варианты выводить не надо, так как их число может быть довольно велико. Например, в приведенном примере наша программа выдает строку. Считаются также варианты, когда полное количество ходов меньше 5 (для размера поля 2*2).

Total 614.

Максимальный размер поля игры возьмем 40*40, так как дальнейшее увеличение может уже сказываться на скорости выполнения программы.

Замечание.

Игра не предполагает использование отрицательных чисел, но это не противоречит общей логике. Примем, что в поле могут располагаться и целые отрицательные числа.

В поисках пиратского клада, третий сезон

Автор: Слинкин Д.А.
Максимальное кол-во баллов: 10

Суть задачи: прямоугольные щиты лежат на земле в произвольном расположении. Удар первого копья должен пробить их все. Копье поднимается и устанавливатеся горизонтально над землей вместе со щитами, которые свободно раскачиваются, пока не успокаиваются под действием силы тяжести. Удар второго копья также должен пробить их все. Задача заключается в определении, выполняются или нет оба заявленных требования.

Исходный файл input.txt содержит:
в первой строке - координаты удара первого копья
во второй строке - координаты попадания второго копья относительно первого копья
в третьей строке - количество щитов
каждая последующая строка файла соодержит информацию о расположении очередного шита на земле и состоит из пяти полей: координат левого нижнего угла щита, размеров щита по горизонтали и вертикали, угла поворота щита против часовой стрелки относительно левого нижнего угла щита (в градусах)

Результирующий файл output.txt содержит:
в первой строке - TRUE, если оба копья пробили все щиты и FALSE в противном случае
каждая последующая строка содержит информацию о попадании копий в очередной щит, состоящую из одного или двух полей. Первое поле определяет попадание первого копья в щит. Если оно равно FALSE, то второе поле в строке отсутствует. Если первое поле равно TRUE, то второе поле определяет попадание второго копья в щит.

Пример файла input.txt:

10 10  
      -2 1
      4
      0 0 20 20 45
      -20 -50 70 60 40
      15 5 100 100 120
      5 5 20 30 270
      

Пример файла output.txt:

FALSE
      TRUE FALSE
      TRUE TRUE
      TRUE FALSE
      FALSE