Задача 1. Рекурсивный лабиринт
Имя входного файла: | input. txt |
Имя выходного файла: | output. txt |
Ограничение по времени: | 2 секунды на тест для задач на Java - 3 секунды на тест |
Ограничение по памяти: | 64 Мб |
Однажды Петя очнулся в странном сооружении. Он не помнил, что было вчера, но этому обстоятельству Петя совсем не удивился. Удивительной же была обстановка вокруг. Петя ходил по длинным коридорам, которые постоянно разветвлялись; в них не было никакого порядка и казалось, что так бродить в одиночестве придется вечно.
Однако через какое-то время (через какое именно, Петя не знал, ведь часов у него не было, а увидеть солнце тоже не представлялось никакой возможности). Петя встретил своего недавно исчезнувшего друга Васю. Оказывается, Вася находился здесь значительно дольше, и ему посчастливилось на своём пути найти зарисовку плана лабиринта.
На плане были обозначены коридоры и какие-то белые квадратики. Петя сначала подумал, что квадратики означают комнаты, но ведь ни одной комнаты Петя на своём пути еще не встречал. Вася объяснил, что лабиринт вовсе не так прост. Оказывается, каждый белый квадратик обозначает не комнату, а точную копию всего лабиринта! Разумеется, в каждой такой копии также присутствовали копии лабиринта, и так продолжалось до бесконечности. Слева дан пример плана лабиринта, где вложенная копия лабиринта обозначена квадратом с номером 1.
Ключевой составляющей лабиринта являются порталы. Порталы позволяют переходить между лабиринтами, вложенными друг в друга. Есть два вида порталов: ведущие внутрь вложенного лабиринта (входы) и ведущие наружу в лабиринт, в который вложена данная его копия (выходы). По краям каждой копии расположено определенное количество выходов, а у кажд
ого белого квадратика есть точно такое же количество входов. Заходя в какой-то вход с номером j на некотором квадратике, мы попадаем в копию всего лабиринта в место соответствующее выходу j. И наоборот, если мы выходим через выход j при условии, что в данную копию мы попали через квадратик с номером i, то мы окажемся в копии окружавшей данную в месте соответствующей входу j белого квадратика с номером i.
Васе известно, что у самой внешней копии лабиринта какие-то из выходов выводят из лабиринта в нормальный мир. Остальные являются тупиками. Так как с тех пор, как он нашел план, Вася отслеживал по нему свой маршрут, то сейчас он точно знает, в каком месте карты они находятся. На рисунке это место отмечено. Также он понял, что они находятся как раз на самом верхнем уровне лабиринта.
Наконец, Вася проделал некоторый анализ карты и объединил в группы те входы и выходы, между которыми можно пройти, не переходя ни наружу, ни во внутренние лабиринты. То есть, между двумя различными порталами можно пройти, не покидая текущую копию лабиринта, тогда и только тогда, когда существует хотя бы одна группа, в которой они оба будут присутствовать. На рисунке, например, можно выделить две группы. Первая образована выходом 1 и входом 2 в квадратик 1. Вторая образована выходами 2 и 3, а также входом 3 в квадратик 1. Заметим, что если есть два коридора, ведущих к одному порталу, то можно перейти из одного в другой, не попадая через портал на другой уровень.
Ваша задача — помочь ребятам определить, до каких выходов самой внешней копии они смогут добраться.
Входные данные
В первой строке входного файла через пробел записаны четыре целых числа: K— количество выходов лабиринта, M — количество белых квадратиков плана, G — количество групп, выделенных Васей, S — номер группы, в которой сейчас находятся Петя и Вася (1 ≤ K ≤ 100, 0 ≤ M ≤ 1000, 1 ≤ G ≤ K×(M+1), 1 ≤ S ≤ G).
Далее следуют 2×G строк, для каждой из G групп порталов записано по две строки. В первой строке первое число означает количество выходов, принадлежащих данной группе. Вслед за ним через пробел перечислены номера соответствующих выходов.
Во второй строке первое число задает количество входов, достижимых из данной группы. Вслед за этим числом через пробелы расположено соответствующее количество пар чисел m и k, где m— номер белого квадратика, k— номер входа в него (1 ≤ m ≤ M, 1 ≤ k ≤ K).
Суммарное количество элементов всех групп не превосходит 106.
Выходные данные
В выходной файл нужно через пробел в возрастающем порядке записать номера выходов из самой внешней копии лабиринта, в которые могут попасть Петя и Вася, или слово NOTHING, если достижимых выходов нет.
Примеры
input. txt | output. txt |
|
1 1 1 1 2 2 2 3 1 1 3 | 1 2 3 |
|
0 | NOTHING |
Задача 2. КУБ
Имя входного файла: | input. txt |
Имя выходного файла: | output. txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 64 Mb |
В трехмерном пространстве заданы куб и плоскость. Требуется определить количество вершин многоугольника, образованного границей области их пересечения.
Куб задаётся тремя своими вершинами, у которых все расстояния друг между другом попарно различны. Плоскость задаётся тремя своими точками, не лежащими на одной прямой.
Входные данные
Входной файл содержит шесть строк. В каждой строке записано по три целых числа — x-, y - и z - координаты точек.
В первых трех строках записаны координаты трех вершин куба, все расстояния между которыми попарно различны.
В следующих трёх строках записаны координаты трёх различных, не лежащих на одной прямой точек плоскости.
Все заданные координаты лежат в пределах от 0 до 255 включительно.
Вычисления производить с точностью до 10–6.
Выходные данные
В выходной файл необходимо вывести одно число — количество вершин многоугольника, образованного границей области пересечения заданных куба и плоскости. Точка считается многоугольником с одной вершиной, отрезок — многоугольником с двумя вершинами. Если пересечения нет, вывести 0.
Пример
input.txt | output. txt |
0 0 0 2 2 2 2 0 2 0 0 1 1 1 1 2 0 1 | 4 |
Задача 3. Жертвы рекламы
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды на тест для задач на Java - 3 секунды на тест |
Ограничение по памяти: | 64 Мб |
После фиаско с сеятелем, разбрасывающим облигации государственного займа, Великий комбинатор отнюдь не отчаялся, а решил еще подзаработать на рекламной стезе. Деньги были крайне необходимы — стулья-то уплывают, и пришлось взяться за первое попавшееся задание.
Сибирской мясо-гороховой корпорации потребовалась рекламная гирлянда из сосисок, и Киса с Осей нанялись ее связать. Им была выдана гора картонных сосисок, на каждой из которых был написан слоган, превозносящий несравненное качество сей корпорации. Понятно, что концессионеры стремились минимизировать свою работу, и на связывание N – 1 сосиски потратили ровно N веревок. Причем на всех концах сосисок, которые не были связаны с другими сосисками, веревки завязали бантиками. За дело они взялись сразу же, а поскольку происходило это глубокой ночью, гирлянду вязали наощупь. Естественно, результат был примерно такой же, как и в предыдущий раз, в случае с сеятелем. За какую бы веревку гирлянду не подвешивали, хотя бы одна из рекламных сосисок висела вверх ногами. Но на сей раз дело было вполне поправимо — надо только лишь перевернуть надписи на некоторых сосисках. При этом количество сосисок, на которых нужно перевернуть надписи, зависит от веревки, за которую подвешивается гирлянда.
Ваша задача — помочь концессионерам минимизировать количество переворачиваний надписей.
Входные данные
В первой строке входного файла записано целое число N — количество веревок (3 ≤ N ≤ 100000). Все веревки перенумерованы числами от 1 до N.
В следующих строках записано по два целых числа Ui и Vi — номера веревок, которые привязаны к разным концам одной i-ой сосиски. Надпись на сосиске направлена от веревки с номером Ui к веревке с номером Vi (1 ≤ i ≤ N–1). К каждой сосиске привязано ровно две веревки c разными номерами.
Выходные данные
В выходной файл необходимо вывести одно целое число — минимальное количество разворотов надписей. Необходимо добиться того, чтобы все надписи при подвешивании за какую-то веревку шли сверху вниз.
Примеры
input. txt | output. txt |
4 1 2 4 2 2 3 | 1 |
5 1 2 2 4 2 3 3 5 | 0 |
Задача 4. Пестрая лента
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды на тест для задач на Java - 3 секунды на тест |
Ограничение по памяти: | 64 Мб |
Жители одного городка решили попасть в Книгу рекордов Гиннеса. Так как в данной местности все занимались ткачеством, то они решили соткать из шелка очень длинную ленту. Лента получилась очень длинная, но неяркая. Тогда ее разметили на квадратики и покрасили каждый квадратик в свой цвет. Так как красок было гораздо меньше, чем квадратиков, то цвета могли повторяться. После того, как все измерения были проведены, победа была отпразднована, ткачи решили разрезать ленту и взять себе по кусочку на память. Но, никого не хотелось обидеть, поэтому решили вырезать из ленты куски равной длины с одинаковой раскраской.
В городе K ткачей. Помогите им узнать, можно ли разрезать ленту не менее чем на K равных кусков максимальной длины с одинаковой последовательностью цветов. Также необходимо эту последовательность определить.
Входные данные
В первой строке входного файла записано целое положительное число K — количество ткачей.
В следующей строке записана строка длины L (1 ≤ L ≤ 50000). Эта строка задает последовательность цветов на ленте. Каждый цвет закодирован буквой латинского алфавита (большие и маленькие буквы считать различными) или цифрой.
Гарантируется, что K ≤ L.
Выходные данные
В выходной файл необходимо вывести строку, которая кодирует искомую последовательность цветов. Если такой последовательности не существует, то нужно вывести NO. Если равных по длине ответов несколько, нужно вывести наименьший из них в лексикографическом порядке.
Примеры
input. txt | output. txt |
2 aaabbbabababaaabbabab | bbabab |
2 abcdefg1 | NO |
Задача 5. Судейство в массы!
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 3 секунды на тест для задач на Java - 4 секунды на тест |
Ограничение по памяти: | 64 Мб |
Для того чтобы судейство в фигурном катании было объективным, решили привлечь к нему всех желающих: соревнования транслируются по Интернету в режиме реального времени, зрители выставляют оценки (в соответствии с правилами), а в зачет фигуристу идет среднее арифметическое всех зрительских оценок. Особое табло отображает итоговую зрительскую оценку.
Необходимо написать программу, которая подсчитывала бы изменение среднего балла по мере поступления оценок очередного зрителя.
Напомним, что по правилам Федерации фигурного катания, выступление фигуриста оценивается так: за каждый технический элемент, выполненный спортсменом, N судей выставляют N оценок, затем одна самая высокая и одна самая низкая оценки удаляются, для остальных N–2 оценок вычисляется среднее арифметическое. Сумма средних баллов по всем техническим элементам является итоговой оценкой выступления.
Входные данные
В первой строке входного файла записано два целых числа S и N, где S — количество технических элементов в программе фигуриста, а N — количество судей (1 ≤ S ≤ 12, 3 ≤ N ≤ 5×104). В каждой из следующих N строк содержится по S натуральных чисел, записанных через пробел, каждое из диапазона от 1 до 9 — оценки одного зрителя. Первая оценка соответствует первому техническому элементу, вторая – второму и так далее.
Подсчет оценок начинается с момента, когда судей станет трое.
Выходные данные
В выходной файл необходимо вывести N–2 строки по S+1 числу в каждой: последовательность итоговых средних баллов за каждый технический элемент и за все выступление в целом, отображаемых на табло по мере поступления зрительских оценок. Каждый средний балл – это действительное число, записанное с точностью до 0.01.
Пример
input. txt | output. txt |
3 6 1 2 1 3 3 3 9 9 8 8 6 7 5 8 9 2 2 2 | 300 5.00 5.00 4.25 |
Задача 6. Башня
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 64 Мб |
Во двор дома привезли много кирпичей. Пока эти кирпичи не были использованы по назначению, юные строители Петя и Вася решили построить из них очень высокую башню. Первый кирпич они положили на ровный участок земли. Второй кирпич положили на первый, стараясь совместить края кирпичей, но все-таки они могли допускать некоторый сдвиг по длинной стороне кирпича. На второй кирпич положили третий, и продолжали так укладывать кирпичи до тех пор, пока башня не стала разваливаться.
Ваша задача определить номер самого нижнего кирпича, который первым начал опрокидываться. В расчет не берутся те кирпичи, падение которых могло быть вызвано обрушением верхней части башни.
Верхняя часть башни опрокинется, начиная с некоторого кирпича, если центр тяжести этой части окажется за пределами того кирпича, на который она поставлена.
Все кирпичи — одинаковые по размерам прямоугольные параллелепипеды, имеющие равномерную одинаковую плотность.
Входные данные
В первой строке входного файла записано два целых числа N и L , где N— количество кирпичей (1 ≤ N ≤ 500), L — размер длинной стороны одного кирпича (1 ≤ L ≤ 10000) .
В следующих N–1 строках дается сдвиг левого края очередного кирпича относительно левого края предыдущего, начиная со второго. Все сдвиги — вещественные числа, по модулю не превосходящие L, не более чем с двумя знаками после десятичной точки. Если левый край кирпича сдвинулся вправо, то сдвиг положительный, иначе — отрицательный.
Выходные данные
В выходной файл необходимо вывести одно целое число — номер самого нижнего кирпича, который начнет опрокидываться первым. Если башня устоит, и все кирпичи будут использованы, то нужно вывести число 0.
Пример
input. txt | output. txt |
3 2 1 1 | 2 |
Задача 7. Васины победы
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 64 Мб |
Вася уже давно играет в свою любимую компьютерную игру, достиг в этом деле больших успехов. Его результаты в игре на столько стабильны, что исход любой игры не зависит ни от времени суток, ни от Васиного настроения или здоровья, ни от начальных условий в игре, ни даже от погодных условий, а зависит только от потраченного Васей времени на игру. При этом Васины результаты, полученные в течение какого-то промежутка времени, не зависят от результатов, достигнутых на любом другом временном интервале. Вася установил очень интересную закономерность. Он заметил, что если он играет M минут, то выигрывает с вероятностью P хотя бы один раз в течение этого периода.
Интересно, с какой вероятностью он будет выигрывать, если будет играть m минут?
Входные данные
Во входном файле в одной строке записаны три вещественных числа M, P и m (1 £ m, M £ 60, 0 £ P £ 1). Все числа заданы не более чем с двумя знаками после десятичной точки.
Выходные данные
В выходной файл нужно вывести одно вещественное число — искомую вероятность с двумя знаками после десятичной точки.
Пример
input. txt | output. txt |
30 75 15 | 0.50 |
Задача 8. Статический анализ
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды на тест |
Ограничение по памяти: | 64 Мб |
Юный Вася решил открыть свою фирму по производству программного обеспечения. Завоевывать мир он решил с помощью своей гениальной среды разработки для своего же гениального языка. И решил он начать с разработки анализатора ошибок. Для этого ему понадобился алгоритм для вычисления возможных значений переменной в некоторой точке программы. Вам предлагается помочь Васе решить эту забавную задачу.
Ниже приводится формальное описание синтаксиса языка. Описание состоит из правил. В левой части правила в угловых скобках дается определяемое понятие, затем разделитель “::=”, в правой части — само определение этого понятия. Слова и символы, не заключенные в угловые скобки (для наглядности они выделены жирным шрифтом), являются служебными словами языка. Вертикальная черта ‘|‘ в правой части означает "или".
<программа> ::= <операторы> <конец программы>
<операторы> ::= <пусто> |
<оператор> |
<оператор> <операторы>
<оператор> ::= <блок> |
<условный> |
<присваивание> |
<печать>
<блок> ::= begin <список идентификаторов><кс> <операторы> end <кс>
<кс> ::= конец строки
<список идентификаторов> ::= <пусто> |
<идентификатор> |
<идентификатор> <список идентификаторов>
<идентификатор> ::= слово длиной не более десяти символов, содержащее латинские буквы и знаки подчеркивания
<условный> ::= if <кс> <операторы> end <кс>
<присваивание> ::= <идентификатор> = <выражение> <кс>
<выражение> ::= <идентификатор> |
<число>
<число> ::= произвольное целое число
<печать> ::= print <идентификатор> <кс>
<пусто> ::=
<конец программы> ::= <кс>
В операторе присваивания переменной, стоящей слева от знака ‘=’, присваивается значение переменной или числа, в зависимости от того, что было записано в правой части оператора.
Последовательность идентификаторов, расположенная после слова begin в заголовке блока, задает список локальных переменных блока. Локальные переменные действительны только внутри блока, и после окончания его работы перестают быть доступными.
Если до блока присутствовали строки с использованием какие-либо переменных из списка, то внутри блока значения этих переменных не будут доступны. В этом случае в блоке будут использоваться другие переменные с теми же именами.
Если для переменной, использованной в блоке, до блока не встречалось строк с ее использованиями, то она тоже считается локальной.
Если же внутри блока производятся операции с переменной, уже использованной до блока и этой переменной не было в списке аргументов, то операции с ней производятся как обычно.
Конструкция языка <печать> является специальной. В действительности в ходе выполнения программы она не исполняется, а обрабатывается позже.
Для каждой строки программы, содержащей конструкцию <печать>, необходимо вывести в выходной файл возможные при исполнении данной строки значения переменной, указанной в качестве аргумента.
Условный оператор с вероятностью 
может быть выполнен, а может быть не выполнен при исполнении программы.
Изначально все переменные имеют значение 0. Использованием переменной считается присваивание переменной некоторого значения или участие ее в качестве аргумента в заголовке блока после слова begin. Участие переменной в конструкции print использованием не считается.
Концом программы считается пустая строка.
Входные данные
Входной файл содержит синтаксически корректную программу на описанном языке. Максимальная длина программы 2500 строк. Максимальный размер входного файла 1 Mb. Остальные числа в программе лежат в диапазоне [–109, 109]. Количество аргументов в заголовке блока после слова begin не превышает 100. Регистр имен конструкций и идентификаторов во входном файле имеет значение.
Выходные данные
Для каждой инструкции print нужно вывести в выходной файл строку в следующем формате: имя переменной и затем перечисленные через пробел ее возможные значения в порядке возрастания. Инструкции print должны быть обработаны в порядке перечисления их в тексте программы.
Пример
input. txt | output. txt |
a=6 if a=5 end print a begin a a=42 print a end print a | a 5 6 a 42 a 5 6 |
Задача 9. Дорогу автомобилистам!
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 64 Мб |
Администрация города Энска решила положить конец бесконечным автомобильным пробкам на дорогах своего города следующим оригинальным способом. Было решено ввести абонентскую плату за пользование дорогами, причем различным участкам дорог, в зависимости от их загруженности, сопоставлялась различная ежемесячная стоимость их использования. Если автомобилист платит за пользование автомобильными дорогами, например, R условных рублей ежемесячно, то он имеет право ездить только по тем дорогам, стоимость пользования которыми не превышает R у. р. Путем грамотного подбора тарифов за пользование отдельными участками дорог, администрация города Энска надеется более или менее равномерно распределить автомобильный трафик по дорогам города и, тем самым, решить проблему пробок на дорогах.
В связи с такими неприятными нововведениями механик Василий, будучи законопослушным и очень экономным человеком, стал соображать, как ему более рационально добираться из дома на работу на своей машине. Он составил карту дорог города Энска, перенумеровал перекрестки числами от 1 до N, а каждому участку дороги, напрямую соединяющему два перекрестка, сопоставил два числа: средний ежемесячный расход на бензин, который он тратил бы, пользуясь данным участком дороги, и введенную администрацией ежемесячную абонентскую плату за пользование этим участком дороги. Теперь по заданным местоположениям своего дома и офиса своей работы Василий хотел бы у вас узнать, как ему определить оптимальный путь, при котором ежемесячная сумма затрат на бензин и абонентской платы за пользование дорогами была бы минимальной. Известно, что на машине всегда можно доехать от дома до работы и обратно.
Входные данные
В первой строке входного файла заданы три целых числа: N — количество перекрестков, S — номер перекрестка, ближайшего к Васиному дому, и D – номер перекрестка, ближайшего к офису Васиной работы (2 £ N £ 100; 1 £ S, D £ N; S ≠ D). В каждой последующей строке описываются участки дорог четырьмя целыми числами: начальный перекресток, конечный перекресток, средний ежемесячный расход на бензин в у. р., минимальный размер ежемесячной абонентской платы в у. р., дающий право использовать данный участок дороги (все числа целые, неотрицательные и не превышают 100000). В городе Энск все дороги с двусторонним движением.
Выходные данные
В первую строку выходного файла нужно вывести одно число — минимальную ежемесячную сумму затрат на бензин и абонентской платы в у. р. Во второй строке нужно вывести путь, на котором достигается этот минимум (формат выходного файла дан в примере). Если существует несколько таких путей, вывести любой.
Пример
input. txt | output. txt |
9 1 5 | 87 1->3->9->8->7->6->4->5 |
