Пятачок и Винни-Пух каждое утро ходят пить чай в гости к Кролику. Естественно, самым коротким путем.
К сожалению, однажды Винни-Пуху пришла в голову идея вырыть ловушку для Слонопотама.
Самое обидное, что они с Пятачком ее даже вырыли.
Поэтому теперь каждое утро, идя в гости к Кролику, они боятся в нее провалиться.
Напишите программу, которая посчитает длину самого короткого безопасного пути от
домика Винни-Пуха до домика Кролика.
Ловушка для Слонопотама представляет собой яму абсолютно круглой формы.
Путь является безопасным, если он не проходит по ловушке (но может проходить по ее границе).
Формат входного файла
Во входном файле записаны сначала координаты домика Винни-Пуха XВ YВ,
затем - координаты домика Кролика XК YК, а затем - координаты центра и радиус ловушки XЛ YЛ RЛ.
Все координаты - целые числа из диапазона от -32000 до 32000.
Радиус ловушки - натуральное число, не превышающее 32000.
Домики Винни-Пуха и Кролика не могут находиться внутри ловушки, но могут находиться на ее границе.
Формат выходного файла
Выведите в выходной файл одно число - длину самого короткого безопасного пути от домика Винни-Пуха
до домика Кролика с тремя знаками после точки.
Папа Карло сменил работу: теперь он работает в мастерской, и целый рабочий день занимается тем,
что забивает гвоздики. Чтобы ему было не скучно, у него в мастерской стоит постоянно работающий телевизор.
К сожалению, производительность папы Карло напрямую зависит от его настроения, а оно,
в свою очередь, — от того, что в данный момент показывают по телевизору.
Правда, пока папа Карло забивает гвоздик, он не обращает ни малейшего внимания на телевизор,
и поэтому скорость его работы зависит только от того, что показывали по телевизору в тот момент,
когда он только начал забивать этот гвоздик.
Забив очередной гвоздик, он обязательно мельком смотрит в телевизор
(его настроение, естественно, меняется), и после этого он может либо сразу начать забивать следующий гвоздик,
либо отдохнуть несколько секунд или даже минут, смотря телевизор.
Папа Карло начинает работу ровно в 9 часов. С 13 часов у него начинается обеденный перерыв.
При этом если он незадолго до обеда хочет начать вбивать гвоздик, но понимает,
что до перерыва он не закончит эту работу, то он и не начинает ее.
Аналогично в 14 часов он вновь приступает к работе, а в 18 уходит домой.
Это значит, что в 9:00:00 (аналогично, как и в 14:00:00) он уже может начать забивать гвоздик.
Если, например, в 12:59:59 (аналогично, в 17:59:59) он хочет начать вбивать гвоздик,
и на это у него уйдет 1 секунда, то он успевает вбить гвоздик до обеда (до окончания работы соответственно),
а если 2 — то уже нет.
Известна программа телевизионных передач и то, как они влияют на папу Карло.
Требуется составить график работы и маленьких перерывчиков папы Карло так,
чтобы за рабочий день он вбил максимально возможное количество гвоздей.
Формат входного файла
Во входном файле записано расписание телевизионных передач с 9:00:00 до 18:00:00 в следующем формате.
В первой строке число N — количество телевизионных передач в этот период.
В каждой из последующих N строк записано описание одной передачи: сначала время ее начала в формате ЧЧ:ММ:СС
(ЧЧ — две цифры, задающие часы, ММ — две цифры, задающие минуты начала,
СС — две цифры, задающие секунды начала).
А затем через один или несколько пробелов число Ti — время в секундах,
которое папа Карло будет тратить на забивание одного гвоздика,
если он перед этим увидит по телевизору эту передачу.
Передачи записаны в хронологическом порядке. Первая передача всегда начинается в 09:00:00.
Можно считать, что последняя передача заканчивается в 18:00:00.
Формат выходного файла
В первую строку выходного файла требуется вывести максимальное количество гвоздиков,
которое папа Карло успеет вбить за рабочий день.
Из правил проведения студенческого командного чемпионата мира по программированию ACM:
Когда команда считает, что она решила задачу, она может послать свое решение на проверку.
Решение проверяется на наборе секретных тестов. Если хотя бы один из тестов не проходит,
команде сообщается причина (неверный ответ, превышение предела времени и т.д.).
Такое решение считается неверным и на результат команды никак не влияет.
Если же решение проходит все тесты, то данная задача считается решенной,
и команде начисляется некоторое количество штрафного времени.
Штрафное время — это время в минутах от начала тура до момента посылки
правильного решения этой задачи на проверку плюс по 20 штрафных минут за каждую
неверную попытку по этой задаче (до тех пор, пока решение не прошло все тесты,
никакого штрафного времени за задачу не начисляется).
Команды ранжируются по числу решенных задач, а при одинаковом их числе — по штрафному времени
(чем штрафное время меньше, тем лучше).
Задача:
Жюри точно уверено, что команда "Super solvers", известная своей непобедимостью,
все равно за тур успеет решить все задачи, и, скорее всего, каждую из задач — с первой же попытки
(то есть штрафное время за каждую задачу будет равно времени от начала тура до момента ее посылки на проверку).
Конечно, жюри может попытаться усложнить задачи, однако оно не хочет этого делать, так как опасается,
что в этом случае из остальных команд вообще никто ничего не решит.
Сама команда тоже прекрасно понимает, что ей по силам решить все задачи, поэтому ей все равно,
в каком порядке решать задачи - и команда решила, что будет решать задачи по порядку, начиная с первой.
Среди членов жюри есть тренер этой команды.
Он прознал про тактику, которой решила придерживаться команда, а также может примерно оценить время,
которое потребуется команде для решения каждой задачи.
Жюри прекрасно понимает, что уже никак не может повлиять на число решенных командой задач, но зато,
учитывая тактику команды, жюри может влиять на штрафное время, которое получит команда,
располагая задачи в разном порядке.
В самом деле, если на тур предлагается две задачи, и на решение одной из них команда тратит 10 минут,
а на решение второй - 20, то штрафное время команды, если задачи расположить именно в таком порядке,
будет равно 40 минутам (первую задачу команда сдает на 10-й минуте тура, вторую - на 30, 10+30=40).
Если же задачи расположить в обратном порядке, то штрафное время будет равно 50
(сначала команда потратит 20 минут, потом еще 10, то есть пошлет задачи на 20-й и 30-й минутах,
и штрафное время будет равно 20+30=50).
Жюри хочет, чтобы штрафное время команды "Super solvers" было как можно больше
(быть может, это даст хоть какой-то шанс другим командам).
Помогите членам жюри расположить задачи в таком порядке.
Формат входного файла
Во входном файле записано сначала число N — количество задач на тур.
Затем идет N натуральных чисел, каждое из которых не превышает 300.
i-ое из этих чисел задает количество минут, которое (по прогнозу тренера) команда "Super solvers"
потратит на решение задач номер i.
Формат выходного файла
В выходной файл выведите N чисел, задающих номера задач в той нумерации,
которая есть у жюри в данный момент, в том порядке, в каком задачи должны быть расположены на олимпиаде.
Под дворцом царя Миноса размером N × M построен одноэтажный лабиринт размером N × M × 1.
Некоторые из кубов 1 × 1 × 1 в этом лабиринте пустые, а некоторые — гранитные
(сквозь них ходить нельзя). Количество пустых кубов в лабиринте S.
Минотавр, гуляя в этом лабиринте только по пустым кубам,
может дойти от любого пустого куба до любого другого пустого.
К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать.
Для того, чтобы этого избежать, фирма "Минос, минотавр and Co" закупила ковролин,
которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно.
Рулон ковролина имеет размеры 1 × S.
Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина
(разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).
Напишите программу, вычисляющую это минимальное число разрезов.
Формат входного файла
Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта.
Далее идет N строк, по M чисел в каждой, задающих лабиринт.
Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.
Формат выходного файла
В выходной файл выведите одно число — минимальное возможное количество разрезов,
которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.
На Chess доске стоит несколько офицеров и ладей.
Требуется посчитать количество свободных клеток, которые не находятся под боем ни одной из фигур.
Замечание для тех, кто не умеет играть в Chess:
Chess доска имеет размеры 8\times8. Ладья бьет все клетки горизонтали и вертикали, проходящих через клетку, где она стоит,
до первой встретившейся фигуры. Офицер бьет все клетки обеих диагоналей, проходящих через клетку, где он стоит,
до первой встретившейся фигуры.
Формат входного файла
В первых восьми строках входного файла описывается Chess доска. Первые восемь символов каждой из этих строк описывают состояние
соответствующей горизонтали: символ B (заглавная латинская буква) означает, что в клетке стоит офицер, символ R - ладья, символ
* - что клетка пуста. После описания горизонтали в строке могут идти пробелы, однако длина каждой строки не превышает 250 символов.
После описания доски в файле могут быть пустые строки.
Формат выходного файла
В выходной файл выведите количество пустых клеток, которые не бьются ни одной из фигур.
Сначала он платит вступительный взнос за игру и в обмен на деньги получает право играть. Более того, за уплаченные деньги он сразу получает X очков.
На автомате, в который он играет, есть три кнопки. Когда он нажимает первую, к его очкам добавляется A очков.
Когда нажимает вторую - добавляется B. Когда нажимает третью - добавляется C очков.
Ему разрешается сначала несколько раз (или ни разу) нажать третью кнопку, и затем несколько раз (или ни разу) - первую. Нажимать вторую кнопку Васе запрещено.
Если после этого он набрал ровно Y очков, то Вася считается выигравшим, и ему выплачивается премия. Если же Y очков набрать не удается,
Вася считается проигравшим, и ничего не получает.
Если Вася выиграл, то считается, что он разгадал одну из волшебных последовательностей нажатий, которые приводят к выигрышу.
Он имеет право и дальше играть в эту игру, и искать другие такие последовательности, которые X очков превращают в Y, но ему категорически
запрещено использовать одну и ту же выигрышную последовательность более одного раза.
Напишите программу, которая посчитает, сколько различных выигрышных последовательностей существует,
то есть сколько раз Вася может выиграть в эту замечательную игру.
Формат входного файла
Во входном файле записаны числа X, A, B, C, Y. Каждое из этих чисел - целое из диапазона [-109, 109].
Формат выходного файла
В выходной файл выведите одно число - количество различных выигрышных последовательностей. Если таких последовательностей бесконечно много, выведите -1.
Радиолокационная станция (РЛС) состоит из нескольких передатчиков (не более 5). К сожалению, их нельзя ставить рядом — они друг для друга создают помехи.
Каждый передатчик состоит из квадратных модулей, которые располагаются вплотную друг к другу.
Вам дана карта района, в котором расположена РЛС. Вся карта для удобства разбита на квадраты, и для каждого квадрата известно,
располагается в нем какой-то из модулей одного из передатчиков РЛС или нет.
Требуется оградить забором (или несколькими заборами) минимально возможной суммарной длины все передатчики РЛС.
Забор — это произвольная ломаная (ее элементы не обязаны идти по сторонам клеток). Одним забором могут быть огорожены сразу несколько передатчиков.
В примере на рисунке РЛС состоит из 5 передатчиков. Длина забора вокруг передатчика 1 равна 9.236.
Передатчики 2 и 3 окружены общим забором длины 6.828, и передатчики 4 и 5 окружены общим забором длины 10.828.
Формат входного файла
Во входном файле записаны два числа N и M, задающие размеры района, в котором расположена
РЛС (1 \le N \le 20, 1 \le M \le 20). Далее идет N строк, по M чисел в каждой, задающих карту района.
Каждое из этих чисел 0 или 1 — 1 означает, что в этом квадрате находится один из модулей передатчика РЛС, а 0 - что в этом квадрате ничего ценного нет.
Общее количество передатчиков РЛС не превышает 5. Каждый передатчик - это связанная группа модулей (модули называются связанными,
если они располагаются в квадратах карты, у которых есть общая граница, либо связаны через какие-то другие модули).
Ограничения на число модулей нет.
Формат выходного файла
В выходной файл выведите одно число - минимально возможную длину забора с тремя значащими цифрами после точки.
На зараженной радиацией планете некоторые точки соединены между собой гипер-каналами.
Когда человек заходит в гипер-канал в одной точке, он мгновенно оказывается в другой.
Все гипер-каналы двусторонние — то есть их можно использовать для перемещения в обоих направлениях
(как из первой точки во вторую, так и из второй в первую).
К сожалению, гипер-каналы платные - каждый проход через гипер-канал стоит 10 у.е.
Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).
Напишите программу, которая определит, какой минимальной суммой у.е. должен располагать путешественник, чтобы добраться из одной точки в другую, не рискуя своим здоровьем.
Формат входного файла
Во входном файле записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки,
куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0 \le N \le 500).
Затем идет N описаний гипер-каналов.
Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек,
последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.
Формат выходного файла
В выходной файл запишите одно число - минимальную сумму, которой должен располагать путешественник для достижения цели.
Если, не рискуя здоровьем, он не сможет добраться до конечной точки, запишите в выходной файл число 171717
(столько стоит лечение лучевой болезни на этой планете).
