XІV Всеукраїнська комплексна олімпіада з математики, фізики та інформатики

"Турнір чемпіонів"2007 р.

Задания по информатике

Задача Забор (FENCE)

Усадьба пана Дивака отделена от улицы забором, который состоит из отдельных столбиков. Все столбики расположены на одной прямой.

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

Бульдозер ломает все столбики, которых он касается. Если бульдозер задевает какой-то столбик своим краем, то этот столбик также ломается. Цель пана Ковтуна – сломать как можно больше столбиков.

Известны количество столбиков и их координаты, а также ширина бульдозера. Ваша задача – определить, какое наибольшее количество столбиков может сломать пан Ковтун, врезавшись на бульдозере в забор один раз.

Формат ввода/вывода:

Напишите программу FENCE, которая читает входные данные из файла FENCE.DAT и записывает результат в файл FENCE.SOL.

Первая строка файла FENCE.DAT содержит целое число – количество столбиков. Следующие строк содержат по целому числу – координату -го столбика . Последняя строка содержит натуральное число – ширину бульдозера.

Единственная строка файла FENCE.SOL должна содержать одно число – наибольшее возможное количество сломанных столбиков.

Ограничения:

, , .

Пример:

FENCE.DAT: 4 70 0 100 15 20

FENCE.SOL: 2

Задача Кузнечик (HOPPER)

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

Длинную ленту разбили на клеток одинакового размера и на первую клетку посадили кузнечика. Цель кузнечика – достичь последней клетки ленты.

Часть клеток ленты закрашены в красный цвет, которого кузнечик боится – на такие клетки он становиться не может. Известно, что первая и последняя клетки ленты никогда не закрашиваются в красный цвет.

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

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

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

Формат ввода/вывода:

Напишите программу HOPPER, которая читает из файла HOPPER.DAT исходные данные и записывает результат в файл HOPPER.SOL. Первая строка файла HOPPER.DAT содержит число – количество клеток в ленте. Вторая строка файла HOPPER.DAT содержит последовательность из нулей и единиц, разделенных пробелами, которая показывает, как раскрашена лента. При этом означает обычную клетку, а – закрашенную в красный цвет. Единственная строка файла HOPPER.SOL должна содержать одно число – наименьшее количество прыжков, необходимое кузнечику, чтобы достигнуть последней клетки ленты, или число , если это невозможно.

Ограничения: .

Пример:

HOPPER.DAT: 13 0 0 0 0 1 1 0 1 0 0 1 0 0

HOPPER.SOL: 5

Задача Печенье (COOKIES)

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

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

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

Формат ввода/вывода:

Напишите программу COOKIES, которая читает из файла COOKIES.DAT размеры пласта теста, а также положение и размеры вырезанных заготовок и выводит в файл COOKIES.SOL радиус максимальной по размеру заготовки, которую еще можно вырезать из этого пласта теста.

В первой строке файла COOKIES.DAT находится действительное число – радиус пласта теста. Считается, что центр пласта находится в начале координат – в точке с координатами . Вторая строка содержит число – количество уже вырезанных заготовок. Следующие строк содержат по 3 действительных числа – координаты центра и радиус очередного выреза .

Единственная строка файла COOKIES.SOL должна содержать искомый радиус максимальной по размеру заготовки, которую еще можно вырезать из пласта теста. Ответ не должен отличаться от правильного больше, чем на .

Ограничения: , .

Пример: (смотри рисунок справа)

COOKIES.DAT: 1.01 3 0.0 0.83333 0.166667 0.72169 -0.416667 0.166667 -0.72169 -0.416667 0.166667

COOKIES.SOL: 0.666666

Памятка участника.Решения задач - файлы с текстами программ, должны быть записаны на диск под именами fence, hopper, cookies. Расширение файлов должно быть одним из следующих: pas, cpp, pp, cc. Решения будут откомпилированы различными компиляторами в зависимости от расширения файла с исходным текстом: pas Borland Pascal 7.0 cpp Borland C 3.1 pp Free Pascal 2.0 cc GNU C++ 3.4 Программы должны читать входные данные из текстовых файлов с расширением dat и записывать результаты в файлы с расширением sol, которые находятся в текущем каталоге. Программа не должна ничего выводить на экран и не должна ждать ввода с клавиатуры! Программа должна завершаться с кодом выхода 0. Решения проверяются автоматически на наборе тестов. В текст программ изменения не вносятся и сам он не оценивается.

 

 

 

 

 

 

 

Задача Трещины (CRACKS)

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

Каждая трещина представляет собой прямолинейный отрезок. Никакие две трещины не пересекаются и не касаются друг друга. Никакая трещина не касается границ плиты.

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

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

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

Определите длину пробиваемой части оптимального разлома.

Формат ввода/вывода:

Напишите программу CRACKS, которая читает входные данные из файла CRACKS.DAT и записывает ответ в файл CRACKS.SOL. В первой строке файла CRACKS.DAT находятся два действительных числа – ширина и высота плиты. В выбранной системе координат, плита представляет собой прямоугольник с вершинами в точках , , и . Во второй строке находится число – количество трещин. В следующих строках находятся по 4 числа – координаты концов трещин .

Файл CRACKS.SOL должен содержать единственное число – суммарную длину пробиваемой части оптимального разлома. Ответ не должен отличаться от правильного больше, чем на .

Ограничения: , , .

Пример:

CRACKS.DAT 8.0 7.0 4 1.0 2.0 2.0 5.0 2.0 3.0 5.0 2.0 6.0 2.0 6.0 4.5 7.0 4.0 7.9 3.0

CRACKS.SOL 3.73245553203

Задача Колокол (BELL)

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

Формат ввода/вывода:

Напишите программу BELL, которая читает числа , и из файла BELL.DAT и записывает ответ в файл BELL.SOL.

В единственной строке файла BELL.DAT записаны через пробел три действительных числа — , и (измеренные в кг, м и кг/м³ соответственно).

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

Ограничения: , , .

Пример:

BELL.DAT: 20.0 1.0 1000.0

BELL.SOL: 0.267301

Задача Число (NUMBER)

Каждое целое число единственным образом можно записать в виде последовательности цифр с ненулевой первой цифрой, перед которой может стоять знак “минус”. Исключение составляет число ноль, которое записывается в виде “0”. Такое представление будем называть стандартной математической записью.

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

 

Формат ввода/вывода:

Напишите программу NUMBER, которая читает содержимое карточек из файла NUMBER.DAT и записывает в файл NUMBER.SOL наименьшее целое число в стандартной математической записи.

В первой строке файла NUMBER.DAT содержится число – количество карточек. В каждой из последующих строк записано содержимое очередной карточки.

В файл NUMBER.SOL должно быть записано наименьшее целое число в стандартной математической записи, которое можно получить из заданного набора карточек. Если из набора карточек нельзя составить ни одного числа в стандартной математической записи, файл NUMBER.SOL должен содержать строку Error.

Ограничения: , каждая карточка содержит до 25000 символов.

Пример:

NUMBERS.DAT: 4 380 003 12 9

NUMBERS.SOL: 120033809