Решение оценивается в 20 баллов.
Подзадача 4
1 ≤п ≤ 2, 2 ≤ т ≤ 105.
Решение оценивается в 12 баллов.
Подзадача 5
1 ≤п ≤ 150, 2 ≤ т ≤ 150.
Решение оценивается в 16 баллов.
Подзадача 6
1 ≤п ≤ 150, 2 ≤ т ≤ 5000.
Решение оценивается в 20 баллов.
Пример
Экскурсия
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 5 секунд
Ограничение по памяти: 256 мебибайт
Турагент хочет организовать экскурсию по одному из городов Приморского края. Этот город можно описать связным графом, где каждая вершина обозначает интересное место (музей или площадь), а каждое ребро – двухстороннюю дорогу. К сожалению, не все дороги одинаково хороши для проведения экскурсии: некоторые могут быть слишком разбиты из-за постоянных пробок.
Агент не хочет разочаровывать туристов посещением разбитых дорог и хочет выбрать самый интересный маршрут. Он присвоил каждой дороге некоторое целое число (показатель «качества»), и у лучших дорог это число больше. Также агент считает, что качество некоторого пути однозначно определяется показателем качества самой плохой дороги, входящей в этот путь.
На рисунке ниже показан граф города, имеющего четыре достойных для посещения места и четыре дороги. Каждому ребру этого графа соответствует некоторое значение, которое обозначает качество соответствующей дороги. Например, ребру (1, 2), представляющему дорогу между местами 1 и 2, соответствует показатель качества, равный 10; а ребру (3, 4) — равный 5.
Качество пути 1-2-4 — это минимум из показателей качества рёбер (1, 2) и (2, 4), то есть min{10, 20} = 10. Аналогично, качество пути 1-2-4-3 будет равно минимуму из качеств рёбер (1, 2), (2, 4) и (3, 4), то есть min{10, 20, 5} = 5.
Пусть в вершине 1 расположен отель, где будут проживать туристы. Для некоторой вершины X агент хочет найти путь с наивысшим качеством среди всех возможных путей из вершины 1 в вершину X. Агента не интересует сам путь — только его качество.
Предположим, что в примере выше туристы хотят посетить вершину 4. Среди всех путей из вершины 1 в вершину 4 наилучшим является путь 1-2-4 с качеством 10. С другой стороны, если они хотят посетить вершину 3, то лучший путь будет иметь качество 30.
Более того, турагенту мало знать лучший путь для единственного направления. У него есть список возможных вершин и он хочет для каждой из них получить качество наилучшего пути. Точнее, у него есть список из Q мест: Х1; Х2,..., Xq и он хочет узнать значение лучшего пути из вершины 1 в вершину Х1, пути из вершины 1 в вершину Х2 и так далее.
Формат входных данных
Первая строка входных данных содержит три целых числа— V, Е и Q, обозначающие соответственно число вершин, число рёбер и число интересующих турагента направлений. Вершины пронумерованы от 1 до V.
Далее следуют Е строк, каждая из которых содержит три числа а, b и q, где а и b обозначают концы ребра, a q — качество дороги (0 ≤ q ≤ 2·105). Далее идут Q строк, каждая из которых содержит номер X очередной интересующей ·турагента вершины (X ≠ 1). Гарантируется, что все интересные вершины различны.
Формат выходных данных
Для каждого направления выведите единственное число — наивысшее качество пути до соответствующей вершины из вершины 1.
Система оценки
Подзадача 1
Дороги образуют простой связный цикл, то есть из каждой вершины выходит ровно два ребра. V ≤ 100; Е ≤ 100; Q ≤ 50.
Решение оценивается в 16 баллов.
Подзадача 2
Дороги образуют связный граф. V ≤ 500; Е ≤ 4 000; Q ≤ 100.
Решение оценивается в 20 баллов.
Подзадача 3
Дороги образуют связный граф. V ≤ 5·104; Е ≤ 105; Q ≤ 104.
Решение оценивается в 24 балла.
Подзадача 4
Дороги образуют связный граф. V ≤ 5·105; Е ≤ 5·106; Q ≤ (V — 1).
Решение оценивается в 40 баллов.
Пример
Замечание
Следует обратить внимание на то, что входные файлы могут достигать существенных размеров и считывание некоторыми стандартными методами может занять существенное время.
CATS
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мебибайт
Эзотерические языки — это языки программирования, построенные вокруг странных и ужасных принципов, просто чтобы попробовать ограничения программирования на прочность или для смеха. Одним прекрасным днём, мистер Панда играл с языком под названием Counter and Two Stacks (CATS), чьё название прекрасно описывает его базовые концепции. В этом языке изменяется счётчик («COUNTER») и два стэка (S1 и S2), используя несколько базовых операций.
В CATS оба стэка инициализируются бесконечным числом нулей. Числа можно добавлять и удалять из стэков при помощи операций «PUSH» и «POP», соответственно. Дополнительная команда «ADD» вынимает два верхних элемента из одного стэка, складывает их и добавляет результат обратно в тот же стэк.
Мистер Панда (новичок в этом языке) попробовал придумать код, который бы по тройке чисел X, L и N возвращал Х-е кратное N большее L. В своём коде он использовал отрицательные числа и тесты, где L делится на N, мистер Панда для удобства не рассматривал.
К сожалению, программа мистера Панды не может выдавать правильный ответ. Более того, он не знает, что стэки в CATS не работают с отрицательными числами. Когда программа пытается добавить в стэк отрицательное число при помощи операции PUSH, число вообще не попадает в стэк. Вместо этого CATS делает странную вещь: у всех чисел в этом стэке меняется младший бит (обратите внимание, что в стэке бесконечное количество элементов). Например, 4 (бинарное представление— 100) превратится в 5 (бинарное представление— 101) и наоборот. Изменение последнего бита в числе эквивалентно операции (X xor 1) в языке Pascal или (X ^ 1) в C/C++.
К тому же, программа мистера Панды иногда выполняет некоторые операции дважды. К счастью, она может быть полностью описана псевдокодом, приведённым ниже. «Т1» и «Т2» обозначают верхние элементы стэков S1 и S2, соответственно.
Эта программа выполняется очень долго и из-за этого её сложно отлаживать.
Требуется написать программу, которая позволит быстро показать мистеру Панде вывод его программы.
Формат входных данных
На первой строке содержится целое положительно число Q — количество запросов. Каждая из следующих Q строк содержит три целых положительных числа — значения X, L и N, соответственно. Как уже говорилось выше, L не делится на N.
Формат выходных данных
Для каждого запроса необходимо вывести число, которое напечатает программа мистера Панды. Гарантируется, что она распечатает ровно одно число для каждого запроса.
Система оценки
Подзадача 1
Q = 1; X ≤ 106; L, N ≤ 20.
Решение оценивается в 16 баллов.
Подзадача 2
Q ≤ 50; X ≤ 106; L, N ≤ 50.
Решение оценивается в 16 баллов.
Подзадача 3
Q ≤ 500; X ≤ 106; L, N ≤ 80.
Решение оценивается в 16 баллов.
Подзадача 4
Q ≤ 103; X, L, N ≤ 106.
Решение оценивается в 16 баллов.
Подзадача 5
Q ≤ 104; X, L, N ≤ 230 – 1.
Решение оценивается в 16 баллов.
Подзадача 6
Q ≤ 105; X, L, N ≤ 260 – 1.
Решение оценивается в 20 баллов.
Пример
Пояснение к примеру
Далее будет рассмотрен первый запрос. Строчки ниже показывают значение COUNTER и значения в S1 при каждом повторе цикла WHILE. Для простоты, будут показаны только верхние четыре элемента S1. Левое значение в строке будет обозначать верхний элемент S1.
COUNTER: 4
S1: 0000...
COUNTER: 4
S1: 4411...
COUNTER: 4
S1: 8850...
COUNTER: 3
S1: 9411...
COUNTER: 2
S1: 5000...
COUNTER: 2
S1: 9911...
COUNTER: 1
S1: 8000...
На следующем шаге COUNTER достигнет нуля и будет распечатано число 8.
Задача D. Обелиск
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мебибайт
Строящееся здание состоит из К этажей, каждый из которых может быть представлен как бесконечная таблица. На каждом этаже, кроме нижнего, имеются квадратные отверстия размером 1×1 (одна клетка). На нижнем этаже имеется клетка, помеченная как X. Также имеется тяжёлый прямоугольный обелиск размером 1×1×М, изначально расположенный вертикально на верхнем этаже. Рабочие хотят переместить обелиск на нижний этаж так, чтобы одна из граней 1×1 была расположена внизу на таблице.
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
