|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexey Tigarev 2:467/106.60 12 Oct 2001 01:25:20
To : All
Subject : БелГУТ & Informatics Guru Offline Contest
--------------------------------------------------------------------------------
*БелГУТ & Informatics Guru Offline Contest*
БелГУТ и проект *Informatics* *Guru* _с 5-го по 20-е октября 2001 включительно_
проводят интернет-турнир по программированию (в режиме оффлайн). Исходные тексты
решений должны быть отправлены Жюри на адрес *SDASoft@tut.by* в течение или по
окончанию указанного срока. Максимальный размер присылаемого файла - 100
килобайт, подробнее формат отсылки решений описан в соответствующем пункте
правил турнира.
Основными участниками турнира, очевидно, будут подписчики рассылок проекта
Informatics Guru, эхоконференций ФидоHет, в которых опубликовано данное
сообщение, и те, кому просто повезло :-)
Публикация результатов турнира и обсуждение задач будет происходить в рассылках
проекта *Informatics* *Guru* :
_informatics-guru-subscribe@yahoogroups.com_ - Эта рассылка выходит около двух
раз в месяц. Тематика рассылки включает в себя олимпиадную информатику,
алгоритмику, вопросы методики обучения программированию, различные языки
программирования, программные средства для обучения программированию,
мыслительные стратегии программистов, психологию программирования. В рассылке
часто публикуется информация о сетевых и не очень конкурсах по программированию.
Редактор рассылки - Алексей Тигарев, tigra@forest.od.ua, 2:467/106.60@FidoNet.
_informatics-guru-talk-subscribe@yahoogroups.com_ - А эта рассылка предназначена
для свободного обсуждения подписчиками всего вышеперечисленного.
Для подписки на рассылки нужно послать e-Mail'ы по соответствующим адресам либо
заполнить форму на сайте проекта *Informatics Guru* - http://informatics.od.ua/
Данное письмо содержит правила и задачи турнира.
*ВHИМАHИЕ!* К задаче 2 положен рисунок в формате gif, который будет опубликован
ююком, при условии получения соответствующего разрешения. В любом случае, можете
попросить меня выслать его нетмылом - около 3 кб. Впрочем, и без рисунка вроде
все понятно.
Итак,
*ПРАВИЛА ТУРHИРА*
=================
*Решение задач*
---------------
Во время соревнования участники решают предложенные задачи. Решением является
программа (файл с исходным текстом), написанная на одном из разрешенных языков
программирования. Участники могут решать задачи на различных языках
программирования.
Участники могут использовать произвольные системы программирования. Компиляция
решений будет производиться с помощью компиляторов Borland Pascal 7.0 и Borland
C/C++ 3.1.
Входные/выходные данные подаются программе в стандартном потоке ввода (stdin для
программ на языках C/C++, input для программ на языке Паскаль) и вывода (stdout
для программ на C/C++, output для программ на Паскале), если дополнительно в
условии задачи не оговорено имя входного и выходного файла. Если явно не
оговорено в условии задачи, формат ввода предполагается свободным, то есть
элементы входных данных могут отделяться друг от друга произвольным количеством
пробельных символов. При использовании файлов для ввода/вывода (см. условие
задачи) я входной файл открыт только на чтение, выходной я на запись.
Дополнительные операции с файлами запрещаются.
*Основания для дисквалификации*
-------------------------------
Основаниями для дисквалификации могут служить следующие действия участника
Интернет-турнира:
Посылка потока решений с целью затруднить проверку решений других участников
турнира;
Использование в решении команд с целью нарушить работоспособность проверяющей
системы турнира;
другие действия, мешающие проведению соревнования
Решение о дисквалификации участника принимает Жюри. Решение Жюри окончательное и
обжалованию не подлежит!
*Проверка решений*
------------------
Проверка представленных решений проводится после соревнований. Участники
посылают решения в Жюри посредством электронной почты на адрес SDASoft@tut.by.
Жюри компилирует полученное решение с помощью пакетных компиляторов.
*Правила посылки решений*
-------------------------
Решения должны посылаться в архиве source.rar (т.е. сжаты архиватором RAR),
который должен быть прикреплен к письму.
Задачи именуются как z1.<расширение соответствующее выбранному
языкупрограммирования>. В файле info.txt должна содержаться информация об
участнике в следующем формате:
1-я строка: Как вы будите называться в таблице результатов
2-я: Ваш e-mail (если его нет, то строчка должна остаться пустой)
3-я: Ваша страна в двухбуквенной кодировке (пример: BY я Беларусь, RU я
Россия)
4-я: Ваш город
Пример:
Dmitry Shalagin
SDASoft@tut.by
BY
Gomel
Решение проверяется путем запуска на наборе тестов, который недоступен
участникам и является одинаковым для всех. Тестирование производится
автоматически, поэтому программы должны в точности соблюдать форматы входных и
выходных файлов, описанные в условии каждой задачи. Если не оговорено отдельно,
все входные данные предполагаются корректными и удовлетворяющими всем
ограничениям, указанным в условии задачи.
В условии каждой задачи указывается максимальное время выполнения для одного
теста. Если на одном из тестов программа превысила это время, баллы за тест не
засчитываются.
По мере готовности или в конце соревнования (абсолютно без разницы) участники
посылают свои решения в Жюри для проверки.
*Определение победителей*
-------------------------
Полную и окончательную ответственность за проверку правильности представляемых
решений несет Жюри. Все решения Жюри окончательны и обжалованию не подлежат.
Все возникающие вопросы направлять на SDASoft@tut.by.
*ЗАДАЧИ ТУРHИРА*
================
Участникам предлагается пять задач.
Задача 1 (10 баллов; 5 сек. на тест)
--------
Ввести K (Kя 30) одномерных массивов по n (nя 10000) чисел в каждом. Все
нечетные массивы отсортировать в порядке возрастания, а четные я в порядке
убывания значений элементов массива. Hайти сумму центральных значений всех
отсортированных массивов. Под центральным значением массива понимается:
центральный элемент, если количество элементов в массиве нечетно (например, для
массива 6, 3, 1, -2, -5 я центральное значение равно 1);
полусумма двух центральных элементов, если количество элементов в массиве четно
(например, для массива 1, 3, 8, 9, 12, 16 я центральное значение равно
(8+9)/2=8.5).
Входные значения находятся в файле IN.TXT со следующей структурой:
3 -я количество массивов
5 - количество элементов 1-го массива
2 3 7 4 6 -я элементы 1-го массива
4 -я количество элементов 2-го массива
6 3 5 2 - элементы 2-го массива
3 -я количество элементов 3-го массива
1 4 3 - элементы 3-го массива
Результат записывается в файл OUT.TXT в следующем формате:
11.00 я - сумма центральных значений (для данного примера 4+4+3=11)
Задача 2 (30 баллов; 5 сек. на тест)
--------
Hа плоскости заданы N (Nя<= 100) отрезков. Каждый отрезок задается координатами
начала и конца. Требуется определить количество точек взаимного пересечения
(соприкосновения) этих отрезков. Два отрезка считаются соприкасающимися, если
они отстоят друг от друга на расстоянии e <= 0.001.
Входные значения находятся в файле *IN.TXT* со следующей структурой:
3 я - количество отрезков
0.2 3.0 7.0 4.4 -я координаты 1-го отрезка
6.1 3.7 5.7 8.2 -я координаты 2-го отрезка
-0.1 3.1 -5.2 4.2 - координаты 3-го отрезка
Результат записывается в файл *OUT.TXT* в следующем формате:
1 -я количество пересечений
(если ответ некорректен, выдать -1)
*Задача 3* (30 баллов; 5 сек. на тест)
----------
Ввести координаты замкнутого пятиугольника и N (N <= 1000) точек на плоскости.
Определить, сколько точек принадлежат пятиугольнику (под многоугольником
понимается замкнутая ломаная и часть плоскости, ограниченная этой ломаной).
Входные значения находятся в файле *IN.TXT* со следующей структурой:
0.2 0.0 2.0 0.4 -1.1 -3.7 1.7 5.2 2.2 3.5 - координаты вершин пятиугольника
4 - количество точек на плоскости
0.1 1.1 1.2 -4.2 1.5 3.8 3.6 5.7 -я координаты точек
Результат записывается в файл *OUT.TXT* в следующем формате:
2 -я количество точек, принадлежащих пятиугольнику ((0.1 1.1) и (1.5 3.8))
*Задача 4* (40 баллов; 5 сек. на тест)
----------
Вокруг Земли по круговой орбите R=500 ед. со скоростью V=60 ед. движется спутник
в горизонтальной плоскости (координата z=0). Космический корабль, находящийся в
точке (100, 0, 300), выпускает ракету в момент времени, когда спутник находится
в точке (500, 0, 0). Определить, в какую точку должна быть направлена ракета,
чтобы поразить спутник, если диаметр спутника d=1.2 ед. Скорость ракеты вводится
из входного файла *IN.TXT* следующего формата:
50 - скорость ракеты
Результат записывается в файл *OUT.TXT* в следующем формате:
490 98 -я координаты точки (округлённые до целых)
*Задача 5* (40 баллов; 5 сек. на тест)
----------
В одном городе H шериф решил раздать каждому жителю по жетону с его
индивидуальным номером. Однако подчинённые при раздаче что-то напутали и раздали
жетоны всем жителям случайным образом. Для того чтобы получить свой номер жители
решили меняться жетонами друг с другом. Причём за один день житель может
обменяться только с одним. Hапишите программу, позволяющую посчитать: за какое
минимальное число дней жители получат жетоны с правильными номерами.
Входной файл *IN.TXT* имеет следующий формат:
5 -я количество жителей (максимальное число жителей 30000)
1 3 2 4 5 -я жетоны, которые получили жители
Результат записывается в файл *OUT.TXT* в следующем формате:
1 -я количество дней (округлённое до целых)
C уважением, Тигра <tigra@forest.od.ua> http://informatics.od.ua
--- GoldEd 3.0.1-asa9 SR1 & Fido Master 2000
* Origin: tigra@forest.od.ua http://tigra.forest.od.ua/ (2:467/106.60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
