|
| |||||
|
|
|
||||
|
ЗАДАЧА 1. Секреты генетики (3 сек.) В опытной лаборатории ученые-генетики вывели новую породу мышей. Они назвали ее Serus-Burus-Malinas-Levus-Pravas Mouse. Отличительной чертой этой породы является врожденный инстинкт, который проявляется при выборе направления движения. Ученые обнаружили, что если такую мышку запустить в лабиринт, она начнет двигаться по странному закону: мышь движется прямо до тех пор, пока не встретит на пути стенку или развилку (развилка - это место в лабиринте, из которого существует более двух направлений движения). Очутившись в таком положении, она выбирает направление своего дальнейшего движения согласно удивительной способности - врожденному приоритету. Приоритет описывается последовательностью, состоящей из четырех литер 'L','R','U','D', которые обозначают направления дальнейшего движения мыши. Взаимное расположение литер задает последовательность, в которой мышь будет эти направления выбирать. Например, если мышь имеет приоритет LRUD, то она будет действовать следующим образом. L В первую очередь она проверит, есть ли проход в левую сторону относительно ее движения, если такой проход есть, то она двинется туда, если его нет, то R она проверит, есть ли проход в правую сторону, и при его наличии она сделает поворот направо и пойдет в этом направлении, иначе U мышь попробует двинуться прямо, и только потом в случае неудачи D повернет обратно. Ученые ставят следующий опыт. Одновременно в лабиринт запускают несколько мышей с различными приоритетами и наблюдают, какая из них придет к выходу первой. Известно, что мыши двигаются с одинаковыми скоростями и друг другу не мешают. Каждый такт времени мыши передвигаются на одну клетку. Время, затрачиваемое на повороты, не учитывается. В начальный момент времени все мыши стоят на одной клетке и имеют одинаковое направление движения. Напишите программу, которая определит, какая из мышей придет к выходу первой. Входные данныеВ первой строке находится одно целое число N (0 < N < 25) - количество мышей. Вторая строка содержит одну из литер W, S, N, E, обозначающих первоначальное направление движения мышей по лабиринту (W- на запад, S - на юг, N - на север, E - на восток). В следующих N строках дается описание каждой мыши - 4 символа через пробел, задающие ее приоритеты (R - направо, L - налево, U - прямо, D - назад). Далее описывается лабиринт. Сначала идет строка, в которой задаются два целых числа K и L (2 < K < 50 и 2 < L < 50) - размеры лабиринта. Затем K строчек по L цифр, разделенных пробелами, описывают сам лабиринт (0 - проход, 1 - стена, 2 - вход, 3 - выход). Следует отметить, что коридоры в лабиринте имеют ширину, равную 1 клетке. Выходные данныеВ выходной файл нужно записать одно число - номер мыши, достигшей выхода первой. Если никто до выхода не дошел, то выдать число 0. Если до выхода добралось несколько мышей одновременно, то выдать минимальный номер. Примеры
ЗАДАЧА 2. Скорость звука (5 сек.) Всем известно, что скорость звука при 20 градусах Цельсия на поверхности суши составляет 330 м/сек. Между тем, даже Книга рекордов Гиннеса не дает ответа на вопрос, какова скорость звука в горах на разных высотах. Кроме того, интересно было бы получить как можно более точные оценки, причем на разных высотах. Молодые ученые Иван и Петр задались целью вписать в Книгу рекордов Гиннеса как можно более точное решение этой проблемы. Они уже нашли огромное количество гор и других возвышенностей, включая самые высокие многоэтажки. Их каталог насчитывает таких точек 89346 (И где они столько их нашли!). Измерительные приборы им удалось заполучить на очень малое время. Поэтому для достижения наибольшей точности измерения скорости звука им бы хотелось выбрать две точки, расстояние между которыми максимальное. Помогите им в этом. Входные данныеВ первой строке входного файла находится целое число - количество точек N (2 <= N <= 105). Каждая из следующих N строк содержит целочисленные координаты X и Y соответствующей точки ( 0 <= X, Y <= 500 ).
Выходные данныеПервая строка выходного файла должна содержать искомое расстояние с точностью до 3-х знаков после десятичной точки. Во второй строке должны быть записаны два целых числа - номера выбранных точек. Если есть несколько решений, выведите любое из них. Пример
ЗАДАЧА 3. Фанаты (3 сек.) Фанаты таблицы ASCII на некоторых картах из N карточных колод (по 36 карт в каждой) (N <= 100000) написали по одному символу (с кодами >32). Не поможете ли вы любопытному ASCII-фану расположить все помеченные карты так, чтобы из написанных на них символов получился палиндром (слово, которое читается одинаково как слева направо, так и справа налево, например ШАЛАШ, 123##321 и т.д.). Входные данныеВходной файл содержит одну непустую строку, длина которой не превышает 36 * N, состоящую из символов, написанных на картах. Выходные данныеВ выходной файл следует записать полученный из этих символов палиндром. Если палиндромов несколько, то выдать первый в лексикографическом порядке. Если палиндром получить невозможно, то выдать #0. Примеры
ЗАДАЧА 4. Пуговки (10 сек.) Декоратор должен купить пуговицы для выполнения заказа весьма привередливой клиентки. Она требует, чтобы пуговицы были пришиты на концы изображенных на ткани завитушек. Причем пришить их надо как можно больше, и все пуговицы пришить необходимо одной имеющейся цельной декоративной нитью заданной длины, при этом нить нельзя обрывать. Чтобы пуговица держалась на ткани, требуется определенное количество нити. Декоратор хочет знать, сколько пуговиц удастся пришить. Входные данныеВ первой строке входного файла находятся три натуральных числа: N, L, M. N - количество мест на ткани, куда можно пришивать пуговицы (N <= 10), L - длина нити (0 <= L <= 100000), M - длина нити, затрачиваемая на пришивание одной пуговицы (0 < M <= 1000). Далее находится N строк, в каждой строке два целых числа 0 <= x <= 1000 и 0 <= y <= 1000 - координаты точек, куда может быть пришита пуговица. Выходные данныеВ выходном файле должно быть записано одно целое число - максимальное количество пуговиц, которое может быть пришито. Пример
ЗАДАЧА 5. Телемания (15 сек.) В провинциальном городе Нске счастливые жители долго не знали, что такое телевидение. Но на последних выборах мэра победу с подавляющим преимуществом (99,9 % голосов) одержал Василий Иванович Пупкин. В его предвыборной программе была обещана постройка телебашни. В настоящее время Василий Иванович как раз занят этой проблемой. Посоветовавшись со специалистами, он выбрал место для постройки башни, такое, что мощности передатчика хватит, чтобы в его зоне действия оказался весь Нск, расположенный в квадрате со стороной <= 6000, центр которого имеет координаты (0, 0). В городе есть N домов, имеющих разную высоту. Жители каждого дома смогут смотреть по телевизору телепрограммы, если с крыши их дома будет видна вершина телебашни. Если два дома имеют одинаковую высоту, то считается, что они друг другу не мешают. Известно, что высота телебашни не должна быть меньше высоты любого дома. Стоимость постройки башни составляет 9999,99 $ за 1 метр высоты. Господин Пупкин - бережливый мэр, и он не хочет попусту тратить средства горожан. Помогите ему определить минимальную высоту башни, достаточную для того, чтобы жители всех домов смогли смотреть телевизор. Входные данныеВ первой строке входного файла находится одно целое число N - количество домов в городе (0 < N <= 2000). Во второй строке записаны два целых числа x0, y0 - координаты передатчика. Далее идут N строк, каждая из которых содержит по три целых числа xi, yi, hi - координаты i-го дома и его высота (0 <= i <= N, 0 <= hi <= 3000). Все числа в пределах одной строки разделены пробелами. Координаты башни не совпадают с координатами какого-либо дома. Выходные данныеВ единственной строке выходного файла должно находиться одно вещественное число с тремя цифрами после десятичной точки - минимальная высота, которую должна иметь телебашня, чтобы во всех домах можно было смотреть телепередачи. Пример
ЗАДАЧА 6. Потерянная таблица (3 сек.) Рассмотрим один многоалфавитный шифр замены, который был описан в 1585 году французским дипломатом Блезом де Виженером. Шифрование производится с помощью, так называемой, таблицы Виженера. Здесь показана лишь часть таблицы для того, чтобы изложить лишь идею метода. Каждая строка в этой таблице соответствует одному шифру простой замены (типа шифра Цезаря). При шифровании сообщения его записывают в строку, а под ним помещают ключ. Если ключ оказывается короче сообщения, то ключ циклически повторяют. Шифровку получают, находя символ в матрице букв шифрограммы. Символ шифрограммы находится на пересечении столбца с буквой открытого текста и строки с соответствующей буквой ключа. Предположим, что нужно зашифровать сообщение "ГДЕАББА". В качестве ключа выберем слово "ДЕВА". Получим:
В результате преобразований получится шифровка: "ЯЯГАЭЪЮ". Ваша задача написать программу, которая по известным исходным и зашифрованным сообщениям и известному ключу максимально полно восстановит таблицу Виженера (на месте неизвестных символов поставить , на месте известных - соответствующий символ в верхнем регистре). Ширина таблицы - максимальный порядковый номер буквы русского алфавита (без учета регистра) в исходном сообщении, высота - то же для ключа. Например, ключ содержит букву <Е>, но не содержит букв больше, чем <Е>, поэтому высота таблицы - 6 строк. Входные данныеВходной файл содержит три строки. Первая строка - исходное сообщение. Его длина не превосходит 25000 символов. Во второй строке приводится это же сообщение в зашифрованном виде. Оно имеет такую же длину. В третьей строке задается ключ шифра. Длина ключевой строки £ 255. Каждая строка содержит, по крайней мере, один символ. Все буквы в строках даны в верхнем регистре. Все сообщения зашифрованы корректно и не содержат пробелов. Выходные данныеВ выходной файл следует записать таблицу, построенную по правилам, описанным выше. Соседние символы в строках таблицы должны разделяться одним пробелом Пример
ЗАДАЧА 7. Конвейер (3 сек.) Однажды маленький мальчик гулял ночью по остановленному машиностроительному заводу и, что-то там нажав, случайно запустил конвейер. Сначала он испугался, но потом заметил, что на конвейере можно кататься. Это ему понравилось. Однако он вскоре устал бегать каждый раз от конца конвейера до его начала и решил, что для развлечения ему хватит и части конвейера. Этот конвейер был довольно извилист. На нем можно было найти два места, расположенные сравнительно недалеко друг от друга. Мальчик забирался на конвейер в первом месте, доезжал до второго, слезал с конвейера и добегал до первого места по земле, не вставая на конвейер. Завод, на котором развлекался маленький мальчик, расположен на плоской поверхности. Если посмотреть на его карту, то можно заметить, что она разбита на квадраты: серые квадраты - это элементы конвейера, а светлые - пустые места. Конвейер представляет собой одну сплошную незамкнутую ленту, он сделан без самопересечений и разрывов. Любой элемент конвейера, за исключением двух крайних, соприкасается с соседними только двумя гранями. И, соответственно, к любому элементу можно подойти с двух сторон. Конвейер может менять свое направление только на 90 градусов. Мальчик выбирает начальный и конечный квадраты пути, исходя из того, что разность пути, который он проезжает и пути, который проходит, максимальна, причем бегать от одной клетки конвейера до другой он может тоже, только меняя направление движения на 90 градусов. Требуется найти длину (количество квадратов) того пути, который мальчик проезжает. Входные данныеВ первой строке входного файла input.txt записаны через пробел два целых числа W и H - ширина и длина карты завода (1< W <= 20, 1< H <= 20), затем в следующих H строках, состоящих из W символов, задается сама карта. Конвейер на карте обозначается буквой K(латинской), пустое место - точкой. Выходные данныеВыходной файл output.txt должен содержать только одно целое число - длину пути, который проезжает мальчик, при способе выбора маршрута, описанном выше. Считается, что квадрат конвейера, на который он заскакивает и квадрат, с которого соскакивает, различны, и он их все-таки проезжает. Если есть несколько вариантов движения, при которых получается максимальная разность между длиной пути, который мальчик проезжает, и длиной пути, который он пробегает, то выбирается тот, при котором мальчику приходится меньше всего бегать. Пример
ЗАДАЧА 8. Система тестирования (5 сек.) На Всесибирской олимпиаде школьников 2010 года впервые было разрешено использовать для решения задач язык программирования D#. Все участники решили использовать компилятор этого языка MacroHard Visual D#++.DA, поскольку он был гибким и мощным, позволял решать олимпиадные задачи, без написания кода вручную. К сожалению, этот компилятор требовал для своего запуска операционную систему MacroHard Doors 2011, которая могла работать только на компьютерах с процессором Floatel Sixtium IV. К разочарованию участников, таких компьютеров в компьютерном классе не нашлось, поэтому компилировать программы пришлось на компиляторе GNU D#, который работал на старом добром Lunix 4.2, который не имел встроенного отладчика, но зато работал даже на стареньком MAD i8x86. Вася Пупкин, ученик 12 <А> класса, решил перехитрить всех и написать программу, проверяющую, все ли участки программы он уже протестировал. Потратив 4 часа из 5 на раздумья над тем, как это сделать, он понял, что без вашей помощи он не обойдется. Помогите Васе выиграть олимпиаду! Синтаксис языка написан в виде набора выражений. Выражение вида <A> ::= <B> означает, что элементы A и B равнозначны. <A> ::= <B><C> показывает, что A состоит из последовательно расположенных элементов B и C. Запись вида (<A>)* следует понимать, что выражение A может встречаться сколько угодно раз, в том числе и ноль. <A> ::= <B>|<C> означает, что выражение A может состоять либо из выражения B, либо из выражения C, но не из обоих сразу. В угловых скобках будут задаваться понятия языка. Служебные слова языка выделены жирным шрифтом. Синтаксис языка D#: <распечатка> ::= (<функция>)* (<сообщение>)* <функция> ::= function <имя>(<оператор>|<вызов>)* end<eol>(<eol>)* <оператор> ::= <текст><eol> <вызов> ::= call <имя> <eol> <сообщение> ::= lines from <номер> to <номер> are tested <eol> где <текст> - произвольный текст, не начинающийся на "call", "end" или "function", пустая строка считается допустимым текстом, <имя> - произвольная последовательность латинских букв, цифр и символов '_' длиной не более 16 символов, начинающаяся с буквы или символа '_', <номер> - целое число, <eol> - конец строки. Между элементами описания допускается произвольное количество пробелов и символов табуляции. Итак, Вася имеет файл input.txt, выданный компилятором, в формате, описанном выше, содержащий элемент <распечатка>. Поскольку компилятор не умеет работать с большими файлами, то количество строк N <= 10000. Каждый элемент <функция> описывает функцию с именем <имя> и телом, состоящим из всех строчек функции, вплоть до строки со словом "end". Количество функций M <= 1000. Кроме того, длина строки входного файла не превосходит 80 символов. Элемент тела функции <вызов> означает вызов функции <имя>. Предполагается, что все такие элементы будут вызывать только функции, уже определенные выше в тексте программы. Функция не может вызывать сама себя. Кроме того, вложенность вызовов функций в программе не может превышать 100. Элемент <сообщение> задает номера A и B, означающие, что Васей протестированы строки, начиная со строки с номером A и до строки с номером B ( строка с номером В не включается). Каждый промежуток полностью содержится в теле функции. Всего промежутков не более 5000. Программа протестирована полностью, если Васей протестированы все строки функции с именем main. Строка протестирована, если она протестирована Васей явно, либо если строка является вызовом функции, и все строки этой функции протестированы, либо если строка является пустой. Вам нужно написать программу, которая бы определяла, является ли данная программа полностью протестированной. Если это так, то в выходной файл output.txt следует выдать строку "YES", в противном случае - "NO". Если программа содержит непротестированные строчки, то вы должны также выдать в выходной файл все номера непротестированных строк, упорядоченные по возрастанию, каждое число на отдельной строке. Входные данные:Входной файл содержит последовательность строк, образованных по правилам, описанным выше. Выходные данные:В выходной файл нужно вывести строку YES, если все строки программы протестированы, иначе нужно вывести в первую строку слово NO, а затем вывести в порядке возрастания номера всех строк, не протестированные Васей. Каждое число нужно выводить на отдельной строке. Пример:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| |