Задача 1. Японский кроссворд
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
“Я взял папку, положил ее к себе на колени и развязал тесемочки. Мне и самому было интересно. Материалы эти я знал с детства. Мой дядя, малоизвестный специалист по Японии, затеял некогда книгу под странным названием "Спруты и люди". Его обуревала идея, что головоногие с незапамятных времен имели весьма тесные контакты с людьми. Чтобы обосновать эту мысль, он перекопал кучу книг, архивов, записал множество японских легенд и все самое интересное, с его точки зрения, перевел на русский и собрал в эту папку. Книгу написать ему не удалось: он увлекся диссертацией на тему "Предательство японской либеральной буржуазией интересов японского рабочего класса”.
Вот одна из легенд, рассказанных спрутом Спиридоном.
“Однажды некий японский император Нихринато Ниришите поспорил со своим шутом Косоряхо на харакири, что ни один человек в мире не способен решить 50 любимых японских кроссвордов императора за время от заката солнца и до его восхода. Если Косоряхо сможет найти такого человека, то по правилам спора ему будет позволено совершить харакири мечом императора. А если не найдет — то позволено не будет… И пошёл Косоряхо к морю, и вылез на берег ика, и решил он все кроссворды. Но император отказал шуту, ведь ика не человек: ика имеет восемь ног и короткое туловище, ноги собраны около рта, и на брюхе сжат клюв… И пошёл Косоряхо к морю ещё раз, и вылез на берег ика, и попросил тогда шут, чтобы тот научил его решать кроссворды.”
И поскольку летопись умалчивает об окончании этой поучительной истории, следует промоделировать ее вероятный исход.
Японский кроссворд представляет собой таблицу клеток. В результате разгадывания японского кроссворда каждая ячейка приобретает ровно один из двух статусов: “пустая” или «закрашенная». Изначально каждая линия (т. е. строка или столбец) имеет свой код — непустую конечную последовательность положительных чисел. Каждое число из кода линии определяет количество слитно закрашенных клеток (группу клеток) в этой линии. Порядок следования групп в линии определяется последовательностью чисел (слева направо и сверху вниз). Между соседними группами должно быть не менее одной пустой клетки. Например, последовательность “2 1” означает, что сначала в линии может быть ноль и более пустых клеток, затем группа из двух закрашенных клеток, затем одна и более пустых клеток, затем одна закрашенная клетка, и, наконец, ноль и более пустых клеток.
Как известно, в число любимых кроссвордов императора входили только детерминированные кроссворды, которые:
- имеют ровно одно решение;
- в любом промежуточном («неразгаданном») состоянии, не противоречащем конечному решению, верно следующее: существует линия, для которой по ее коду и текущему состоянию можно указать статус некоторых неопределенных клеток этой линии.
Входные данные
В первой строке входного файла указаны два числа N и M — количество строк и колонок в таблице (0 < N, M < 64). В последующих N строках файла следует коды строк таблицы — разделенные пробелами положительные числа, по одному коду в каждой строке. Далее в M строках файла аналогично определены коды столбцов таблицы.
Выходные данные
Выходной файл должен состоять из N строк по M символов, изображающих решение кроссворда. Каждый символ обозначает статус соответствующей клетки таблицы: пустые клетки обозначаются символом ‘.’, закрашенные — символом ‘#’.
Пример
input. txt | output. txt |
8 6 3 1 1 1 1 1 1 5 1 1 1 1 2 1 1 5 2 1 1 1 1 1 8 | ...### ..#..# ..#..# .#...# .##### .#...# .#...# ##...# |
Задача 2. Диверсия
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
Для того, чтобы починить реморализатор, Эдику Амперяну требовалось какое-то время. При этом было желательно, чтобы Тройка не принимала решений во время ремонта. И тогда было принято решение провести диверсию. Птеродактиль Кузьма сумел добраться до стеллажа с учётными делами на экспонаты Колонии. В стеллаже N ячеек и N дел, пронумерованных от 1 до N. В каждой ячейке лежит одна папка с делом. Изначально номер каждого дела совпадает с номером ячейки, в которой лежит папка с этим делом. Кузьма может выполнять следующую операцию: взяв пару (i, j) из заранее фиксированного набора из M допустимых пар, поменять местами папки, стоящие на месте i и на месте j. Вам требуется определить, сможет ли птеродактиль достичь заданного Эдиком конечного расположения дел по ячейкам путём многократного применения данных операций.
Входные данные
Первая строка входного файла содержит числа N и M (1 ≤ N, M ≤ 105). На следующей строке задано конечное расположение дел: N чисел, i-е из которых — номер дела, стоящего на i-м стеллаже. В следующих M строках заданы допустимые пары, по одной на строке.
Выходные данные
В первую строку выходного файла выведите YES, если требуемого расположения папок можно достичь, и NO — в противном случае.
Примеры
input.txt | output. txt |
3 2 2 1 3 1 2 3 1 | YES |
4 2 1 2 3 4 | NO |
Задача 3. Дорвались!
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 30 секунд на тест |
Ограничение по памяти: | 128 Мб |
После того, как Тройка была изгнана, Кристобаль Хозевич Хунта в сопровождении Привалова и Амперяна проследовал в музей Колонии. Оказалось, что рачительный Зубо запаковал все ценные экспонаты в N пронумерованных коробок одинакового размера (1´1´1 м3), но разной массы.
Судя по прилагавшейся инструкции, коробки нужно составить в один ряд вдоль стены длины L. Коробки можно ставить (переставлять) друг на друга, но верхняя коробка должна быть легче нижней. Коробки не должны быть подняты выше, чем на H метров.
Составленные коробки надо распаковать в порядке возрастания их номеров, начиная с первой. Для распаковки можно брать только коробки, на которых ничего не стоит, при этом распакованная коробка убирается. Также коробки, на которых ничего не стоит сверху, можно переставлять на свободные места вдоль стены или на другие коробки, соблюдая правила.
Так как тратить время на перекладывание коробок, осознавая, насколько интересные вещи могут оказаться внутри, глупо, то ваша задача — составить коробки таким образом, чтобы за минимальное количество перестановок можно было бы распаковать все коробки.
Входные данные
В первой строке входного файла задаются три натуральных числа N, L, H (1 ≤ N ≤ 16, 1 ≤ L, H ≤ 4).
В следующей строке задано N целых чисел, записанных через пробел — массы коробок в порядке возрастания номеров коробок, масса каждой коробки не превосходит 100. Массы всех коробок попарно различны.
Выходные данные
В выходной файл нужно вывести одно целое число — минимальное количество перестановок. Если расставить коробки невозможно, то вывести число –1.
Пример
input.txt | output.txt |
3 2 2 10 8 6 | 1 |
Задача 4. Регата
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
После неудачного рассмотрения дела номер восемь (относительно плезиозавра Лизки) тьмускорпионским яхтенным клубом было принято решение, пока плезиозавр спит, провести на озере регату имени Тройки. План был одобрен лично товарищем Вунюковым, на официальные посты Директора, Председателя Оргкомитета и Главного Судьи были назначены члены Тройки, а гоночные инструкции составлял профессор Выбегалло — заместитель Главного Судьи. Приз — внеочередное рассмотрение запроса победителя Тройкой.
Саша Привалов, имевший небольшой опыт в водном спорте, решил победить в гонке. Получив за день до нее гоночную инструкцию, он пошел к своему знакомому метеорологу и под большим секретом выпросил у него точный 
прогноз направления и силы ветра на следующий день.
Гоночная инструкция представляет собой карту моря с указанными контрольными знаками, через которые должна пройти яхта. Контрольные знаки нужно обходить в порядке, который задан в инструкции. Последовательность контрольных знаков, задающая порядок обхода их яхтой, может содержать один и тот же знак в нескольких местах, но два или более раз подряд один знак встречаться в инструкции не может. Гонка начинается на первом знаке из последовательности и заканчивается на последнем.
Саша решил разработать маршрут таким образом, чтобы пройти его за минимально возможное время.
Важно помнить, что яхта никогда не ходит прямо против ветра. Практически большинство яхт не могут удерживать курс под углом меньше 45° навстречу ветру, поэтому для достижения цели, лежащей в пределах этого сектора, называемого мертвой зоной, надо сделать серию зигзагообразных маневров по отношению к ветру (известных, как хождение галсами, или лавировка). Сашу учили, что, если яхта может идти прямо к нужной цели (ветер позволяет это делать), то нужно идти по прямой, а если такому движению мешает ветер, то тогда нужно лавироваться, причем стараться это делать оптимально и выполнять при этом только один поворот. Вам предстоит помочь Саше посчитать, за какое минимальное время он сможет, следуя этим правилам, пройти дистанцию
Скорость яхты зависит от силы и направления ветра, и определяется по приведенной ниже формуле. Обозначим через v — скорость яхты, V — скорость ветра в м/сек, a — угол в градусах направления движения яхты относительно направления ветра (0°£ | a | £ 135°), k — коэффициент, зависящий от конструкции яхты (0 < k £ 0.25), тогда
v = 0.5 k V (5 + 3sin(|a|)) при 0°£ | a |£ 90°, и
v = 2 k V (2 – 
sin(|a|– 90)) при 90° < | a |£ 135°.
Входные данные
В первой строке входного файла через пробел записаны три числа k, F и V: вещественное число k — коэффициент, зависящий от конструкции яхты (0 < k £ 0.25), целое число F — направление ветра в градусах относительно оси OX (0 £ F < 360), целое число V — скорость ветра в м/сек. (1 £ V £ 20).
Во второй строке записано одно целое число N — количество различных контрольных знаков (2 £ N £ 100). В следующих N строках даны координаты контрольных знаков. В каждой строке через пробел записано по два целых числа — X- и Y-координаты, соответственно (–10000 £ X, Y £ 10000).
Далее в двух строках дана гоночная инструкция. В первой строке записано одно число М — количество контрольных знаков, которые нужно пройти (2 £ M £ 1000), а во второй — записаны через пробел M целых чисел (номера контрольных знаков). Они указаны в том порядке, в каком их нужно пройти по условиям гонки. Гонка проводится далеко от суши, поэтому берега не должны мешать движению. Время на повороты не учитывается.
Выходные данные
В выходной файл нужно вывести одно число — минимальное время в секундах, которое потребуется Саше, чтобы закончить гонку. Время нужно выводить с точностью до одного знака после десятичной точки.
Пример
input.txt | output.txt |
0 3 0 0 1000 0 1 4 | 2414.2 |
Задача 5. Минное поле чудес
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
— Дело номер 239, — произнёс Зубо, — «Минное поле чудес».
— Предлагаю ввиду очевидной важности данного явления для обороны проверить допуск всех присутствующих к гостайне, — предложил Фарфуркис.
У Выбегалло допуск оказался просроченным, и временно исполняющим обязанности научного консультанта предложили назначить Сашу Привалова.
— Гррм… А теперь выслушаем суть дела, — решил Лавр Федотович.
«Минное поле чудес» находилось на окраине Тьмускорпиони. Его карта представляла собой прямоугольник из клеток. В каждой клетке может находиться либо не находиться одна мина. При подрыве какой-нибудь мины поле возвращается в нетронутое состояние — с другим расположением мин.
На данный момент поле было частично исследовано — то есть про некоторые клетки известно, есть там мина или нет. При отсутствии мины в клетке известно общее количество мин в соседних (по стороне или по углу) клетках. Также известно общее количество мин на поле.
— Надо бы рационализировать, — неуверенно заметил Хлебовводов, поглядывая на коменданта.
— Уже который раз рационализируем, а оно снова и снова восстанавливается, — недовольно проворчал Фарфуркис.
— Надо бы сначала посчитать вероятности, а потом уже и планировать рационализацию явления, — заявил врио научного консультанта Саша Привалов.
В данной задаче по заданной начальной ситуации вы должны определить вероятности нахождения мин в неоткрытых клетках. Под вероятностью того, что в данной клетке находится мина, понимается отношение количества возможных вариантов расстановки мин, при которых в данной клетке находится мина, к общему количеству вариантов.
При подсчете количества вариантов, мы должны считать только те расстановки, которые согласуются с заданной начальной ситуацией.
Гарантируется, что начальная ситуация задана корректно, то есть существует по крайней мере одна расстановка мин, с ней согласующаяся. Также гарантируется, что количество клеток, соприкасающихся с открытыми клетками, не превышает 25.
Входные данные
В первой строке входного файла записаны через пробел три целых числа: N, M и K. Числа M и N задают размеры поля (2 £ N, M £ 20), а K — общее количество мин (0 £ K £ N ´ M).
В последующих N строках задается само поле. Каждая строка состоит из M символов, каждый из которых описывает клетку поля. Символы ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’ обозначают количество мин в соседних клетках. Прописная латинская буква ‘X’ обозначает неоткрытую клетку. Прописная латинская буква ‘M’ обозначает клетку, в которой точно есть мина.
Выходные данные
В выходном файле должны быть записаны вероятности нахождения мин во всех клетках поля. В первой строке выходного файла должны быть записаны те же самые числа N, M и K. В последующих N строках должны быть записаны M вещественных чисел, каждое из которых — вероятность нахождения мины в соответствующей клетке. Каждая вероятность должна быть указана с точностью до четырёх знаков после десятичной точки.
Пример
input.txt | output.txt |
5 5 4 1XXXX XXX21 XXX10 XXX21 XXXXX | 5 5 4 0 0.3 0.3 |
Задача 6. Пирамида из труб
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
В начале своего пребывания в институте, ещё будучи представителем коммунхоза, Лавр Федотович Вунюков для ремонта канализации на четвёртом этаже в отделе Выбегалло заказал N водопроводных труб одинаковой ненулевой длины и различного диаметра. Из-за обычной в таких делах волокиты трубы доставили с запозданием, и по месту пребывания заказчика и подрядчика, то есть в Тьмускорпионь, на 76-й этаж НИИЧАВО.
В связи с тем, что необходимости в ремонте труб в Тьмускорпиони не было, Выбегалло предложил построить из труб пирамиду, которая превышала бы пирамиду Хеопса и служила бы примером здоровой сенсации. Руководить строительством доверили коменданту колонии тов. Зубо.
Комендант поставил перед рабочими трудную задачу: так расположить трубы, чтобы они лежали параллельно друг другу, но получить пирамиду максимальной высоты. Похоже, что рабочие без вас не обойдутся. Помогите им определить максимальную высоту пирамиды, которую можно сложить из привезенных труб.
Трубы можно класть либо на плоскую площадку, либо на другие трубы. Рабочих немного, поэтому они могут складывать трубы последовательно — одну за другой. Первую трубу можно положить в любое место на площадке. Если уже сложено какое-то количество труб, то на площадку нужно класть трубу так, чтобы она плотно касалась одной из уже сложенных труб. Если трубу хотят положить на другие трубы сверху, для того, чтобы она лежала и не скатывалась вниз, должны быть выполнены следующие условия:
- труба опирается не менее чем на две другие трубы; центр тяжести трубы находится не ниже линий соприкосновения с этими трубами, проекция центра тяжести трубы на плоскость не должна попадать вне промежутка между проекциями линий соприкосновения труб.
Входные данные
В первой строке входного файла записано одно число N — количество труб (1 £ N £ 7).
В следующей строке через пробел записаны N целых чисел — радиусы труб (числа изменяются в диапазоне от 1 до 100).
Выходные данные
В выходной файл необходимо вывести одно вещественное число с точностью до 10–6 — высоту максимальной пирамиды, которую можно сложить из данных труб.
Все вычисления производить с точностью до 10–6.
Примеры
input.txt | output.txt |
3 1 1 1 | 3.732051 |
4 7 | 102.828368 |
Задача 7. Заколдованное место
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
При повторном рассмотрении дела о заколдованном месте Выбегалло сделал предложение: «Противопоставить магии природы магию науки» — то есть пусть, дескать, товарищи Амперян и Привалов попробуют изучить это явление теоретически, а далее — пуркуа бы не па — и подготовить предложения по рационализации и утилизации.
Исследовав поведение магического поля на территории Заколдованного места, Амперян нашёл, что лучшим методом обхода Заколдованного места будет фрактальный обход вдоль силовых линий.
Для исследования Заколдованного места, план которого представляет собой квадрат, было набрано N добровольцев.
Первый доброволец обходит квадрат простейшим способом: разбивает его на четыре вдвое меньших квадрата и обходит их по часовой стрелке (см. рисунок слева).
Второй доброволец обходит квадрат потщательнее (см. рисунок справа). А именно, он разбивает каждый квадрат на четыре еще меньших квадратика, и проходит через центр каждого из них. При этом порядок обхода квадратов 2´2 у него такой же, как у первого.
Затем идёт третий доброволец. Он каждый квадрат разбивает еще на четыре, и проходит через каждый из них, придерживаясь того же порядка обхода этих квадратов, что и второй (см. рисунок ниже).
 |
Аналогично строятся траектории каждого следующего добровольца. Передвигаются между квадратами исследователи только по вертикали и горизонтали, каждый из них начинает свой маршрут с левого квадратика, ближайшего к центру нижней стороны квадрата, а заканчивает в соседнем с ним правом квадратике. Естественно, участники Тройки очень хотят знать, в каком квадратике исследователи будут находиться через заданное число шагов, но самостоятельно определить это не могут.
Входные данные
В единственной строке входного файла записаны через пробел два целых числа N и K. N — это номер добровольца, K — количество шагов, которые он успел сделать (1 £ N £ 12, 1 £ K £ 22N).
Выходные данные
В выходной файл необходимо вывести через пробел два целых числа — x - и y - координаты квадратика, в котором находится данный доброволец на K-м шаге. Все квадратики имеют сторону 1, левый нижний квадратик имеет координаты (1, 1), квадратик справа от него — (2, 1) и т. д.
Пример
input.txt | output. txt |
2 14 | 4 2 |
Задача 8. Спрямление трека GPS
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 2 секунды на тест |
Ограничение по памяти: | 16 Мб |
«Лавр Федотович закурил первую сегодня "герцеговину флор", Хлебовводов тихонько затянул какую-то ямщицкую песню, комендант подремывал, прижимая к груди папку с делами, и только Фарфуркис после короткой борьбы нашел в себе силы справиться с изнеженностью. Развернув карту Тьмускорпиони с окрестностями, он деятельно наметил маршрут, который, впрочем, оказался никуда негодным, потому что Фарфуркис забыл, что у нас автомобиль, а не вертолет. Я предложил ему свой вариант: озеро – болото – холм»
Лавр Федотович очнулся и произнёс:
— Есть предложение принять вариант, предложенный товарищем Приваловым. А также поручить ему, как (тут он запнулся на малознакомом слове) программисту автоматизировать процесс определения маршрута Тройки.
По сути дела, требовалось написать тьмускорпионскую GPS (Global Positioning System). Саша Привалов взял на себя реализацию основной части проекта, вам же требуется реализовать функцию спрямления трека для этой системы.
Замером координат называется пара вида (момент времени, точка плоскости). Говорят, что замер координат произведён в такой-то точке в такой-то момент времени.
Треком называется такое множество замеров координат, что в каждый момент времени произведено не более одного замера координат.
Спрямлением трека T называется любое непустое подмножество T, содержащее самый ранний и самый поздний замеры координат трека T.
Расстоянием от замера координат (t, p) до трека T называется расстояние от p до отрезка, соединяющего точки, в которых произведены замеры координат из трека T в ближайшие к t моменты времени (последний момент не позднее t и первый момент не раньше t).
Отклонением трека T1 от трека T2 называется наибольшее из расстояний от замеров координат из трека T1 до трека T2.
Дан трек T и неотрицательное число d. Требуется найти такое спрямление Tbest трека T, что отклонение T от Tbest не превосходит d и число замеров в Tbest минимально.
Входные данные
В первой строке входного файла содержатся целые числа N и d (N — число замеров времени в треке; 1 ≤ N ≤ 600, 0 ≤ d ≤ 20000).
Остальные строки файла хранят по одному замеру координат в формате
< момент времени > <пробел> < Х-координата > <пробел> < Y-координата >
Моменты времени задаются целыми числами от 0 до 10000. Координаты задаются целыми числами от –20000 до 20000. Замеры координат отсортированы по времени.
Выходные данные
В первой строке выходного файла должно содержаться одно число M — количество замеров координат в оптимальном спрямлении. Вторая строка должна содержать номера замеров координат, образующих оптимальное спрямление. Эти номера должны располагаться по возрастанию. Замеры координат нумеруются от 1 до N с шагом 1 в порядке их следования во входном файле (то есть замер из второй строки входного файла получает номер 1, замер из третьей строки — номер 2, и т. д.).
Пример
input.txt | output.txt |
7 0 0 0 0 1 5 5 2 10 10 3 15 15 4 10 10 5 5 5 6 0 0 | 3 1 4 7 |
Задача 8. Нумерология
Имя входного файла: | input.txt |
Имя выходного файла: | output.txt |
Ограничение по времени: | 1 секунда на тест |
Ограничение по памяти: | 16 Мб |
— Дело номер 366, — начал было Зубо...
остановил его.
— Гррм... Почему у Вас номера дел какие-то странные? Общественность этого не поймёт. В таком номере, знаете ли, можно увидеть совсем нездоровые намёки...
— Да и запутаться с этими номерами можно. Ещё бы миллионами дела нумеровали..., — угодливо заметил Хлебовводов.
— Вообще, Лавр Федотович точно заметил. 366 — то есть получается, что в Тройке двое "шестёрок"? За такие намёки, товарищ Зубо... — грозно сказал Фарфуркис.
— Христом-богом, Лавр Федотович... я без умысла. Могу на 355 исправить, — начал оправдываться комендант.
— Тройка пятится назад? А это уже явный оппортунизм, — Хлебовводов уловил линию и пытался ей следовать.
В результате было принято решение переименовать дело 366 в дело 333+33. Более того, по инициативе Выбегалло было предложено в дальнейшем все дела нумеровать только числами, представимыми в виде суммы чисел, запись которых в десятичной системе состоит исключительно из троек. Причём общее число этих троек не должно было быть больше девяти — чтобы не запутаться в нумерации. Рассмотрение же дел с другими номерами отложить на неопределённый срок.
Вам дан номер дела. Выясните, будет ли это дело отложено или нет. А если не будет, (то есть представление в требуемом виде существует) укажите, какое минимальное число "плюсов" потребуется для такого представления.
Входные данные
Во входном файле задано натуральное число N, не превышающее .
Выходные данные
В выходной файл нужно вывести минимальное число "плюсов", которое надо использовать, чтобы записать N в виде суммы чисел, составленных только из троек, с использованием не более, чем 9 троек. Если такого представления не существует, то нужно вывести –1.
Примеры
input.txt | output. txt |
30 | -1 |
6 | 1 |
33 | 0 |
