Принцесса и принц не могут пройти путь, если на нём есть хотя бы одна освещенная комната, при этом начальная и конечная комната считаются частью пути.
Формат выходных данных
Для каждого запроса с a = 1 необходимо вывести на отдельной строке единственное целое число, равное минимальному числу переходов из комнаты в комнату, которое нужно совершить принцессе и принцу для встречи, либо —1, если встреча не может произойти.
Примеры
Задача D. Простыни
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 128 мебибайт
По просьбе мамы Миша постирал свои простыни и пошел на улицу, чтобы повесить их сушиться. Сильный ветер, однако, повредил верёвку для развешивания белья, и Миша временно разложил простыни на траве.
Травяное поле можно рассматривать как бесконечную квадратную сетку, где каждый квадрат размером 1x1 может быть задан парой координат. Простыни — это прямоугольники на сетке. Стороны этих прямоугольников параллельны осям координат. Прямоугольники, соответствующие простыням, могут перекрывать друг друга.
Чтобы починить веревку, Миша вбил колышек в центр квадрата с координатами (0,0). Дальше последовал совершенно неожиданный поворот событий. Из земли брызнула нефть, и от шока Миша упал в обморок. Пока Миша лежал без сознания, нефть распространялась, загрязняя его простыни.
Считается, что отсчет времени начинается с момента, когда нефть начала распространяться. В момент времени равный 0 только квадрат с координатами (0, 0) был покрыт нефтью. Нефть распространяется со скоростью один квадрат в секунду во всех восьми направлениях, как показано на рисунке ниже. Когда нефть появляется в каком-либо квадрате, она загрязняет этот квадрат ткани на всех простынях, покрывающих этот квадрат на поле.
Требуется написать программу, которая по М моментам времени вычисляет суммарную площадь загрязнённой ткани на всех простынях для каждого из заданных моментов времени.
Формат входных данных
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 100 000) —количество простыней.
Каждая из последующих N строк содержит четыре целых числа х1, у1, х2 и у2
(-1 000 000 ≤ х1 ≤ х2 ≤ 1 000 000, -1 000 000 ≤ у1 ≤ у2 ≤ 1 000 000). Координаты (х1, у1) и (х2, у2) задают диагонально противоположные углы простыни (это координаты квадратов, а не точек). Никакая из простыней не покрывает квадрат (0, 0).
Следующая строка содержит целое число М (1 ≤ М ≤ 100 000)—количество моментов времени.
Следующая строка содержит М целых чисел от 0 до 1 000 000 — моменты времени, заданные в строго возрастающем порядке.
Формат выходных данных
В выходных данных для каждого заданного момента времени отдельная строка должна содержать общую площадь загрязнённой поверхности ткани на всех простынях. Порядок вывода должен соответствовать порядку следования моментов времени во входных данных.
Примеры
10. Описание заданий для десятого интернет-тура
На десятом туре было предложено 4 задачи: задача A «Эволюционные деревья», задача B «Еноты», задача C «Овцы на корабле» и задача D «Игра в тетрис». Тексты задач представлены ниже.
Задача A. Эволюционные деревья
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунды
Ограничение по памяти: 256 мебибайт
Случается так, что эволюционные деревья на самом деле не деревья, а ациклические ориентированные графы. Причина этого в том, что британские учёные не всегда наверняка уверены, что вид А произошёл от вида В. Бывает так, что известен только список кандидатов в родители этого вида — В1, В2,... , Вk. Наверняка британские учёные знают только одно — всё в этом мире произошло от некого Изначального Вида.
Для построения верных теорий британским учёным нужно больше точных знаний. Например, недавно они заинтересовались следующим вопросом: каков ближайший точный предок вида А? В этом и будет заключаться решаемая задача.
Для понимания задачи рассмотрим следующий граф эволюции, представленный на рисунке ниже:
Изначальный Вид (Root)—вершина, из которой достижимы все остальные. У вида С возможен только один родитель: учёным точно известно, что D — родитель С. Вершина D является ближайшим точным предком С. Вид А мог произойти от одного из двух других, от какого — точно неизвестно. Зато можно наверняка сказать, что вне зависимости от пути, по которому проходила эволюция, вид X является предком вида А (в данном случае ближайшим точным предком). Для вида В точный предок только один — это вид Root.
Требуется написать программу, которая для каждой вершины графа эволюции определяет вершину ближайшего точного предка.
Формат входных данных
Во входных данных задан ориентированный ациклический граф.
В первой строке входных данных записаны числа п и m (1 ≤ п ≤ 100 000, 0 ≤ m ≤ 100 000) — количество вершин и рёбер в графе соответственно.
Последующие m строк содержат описания рёбер графа. Каждое ребро описывается парой чисел а и b (1 ≤ a, b ≤ п). Наличие ребра (а, b) означает, что вид а мог быть родителем b. Кратных рёбер и петель не бывает.
Изначальный Вид всегда соответствует вершине с номером 1. Гарантируется, что из неё достижимы все остальные вершины.
Формат выходных данных
В выходных данных каждой из вершин графа должно соответствовать одно число — номер ближайшего точного предка этой вершины.
Пример
Задача B. Еноты
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 Мебибайт
В тёмном лесу со старыми дуплистыми деревьями живут еноты. Недавно главный енот предсказал скорый конец света. Было принято решение воспрепятствовать этому с помощью магии, ведь еноты — носители тайного знания!
Еноты улеглись на полянке в лесу, при этом каждый енот улёгся в форме квадрата со сторонами, расположенными под 45° к сторонам света. Для завершения ритуала всем енотам нужно вытянуть лапки так, чтобы до i-го енота могло дотянуться не менее кi других енотов. Оказалось, что размаха лапок енотов недостаточно, поэтому главный енот приказал всем енотам тренироваться ежедневно.
Изначально размах лапок всех енотов был очень мал, и енот мог дотянуться только до точки, совпадающей с его центром. На следующий день это уже были все точки, удалённые от центра не более чем на 1 по каждой из координат. За один день тренировок все еноты увеличивают размах лапок на 1, таким образом, на i-й день енотам доступны все точки, удалённые не более чем на i по каждой из осей. Считается, что енот А способен дотянуться до енота В, если размаха лапок енота А достаточно, чтобы дотянуться до всех точек енота В.
Требуется написать программу, которая определяет минимальное количество дней тренировок, которое необходимо для выполнения приказа главного енота.
Формат входных данных
Первая строка ввода содержит единственное целое число п — количество енотов
(1 ≤ п ≤ 500 000). Далее следуют п строк, каждая из которых содержит по четыре целых числа— координаты соответствующего енота xi, yi, его размер si и магическое число кi
(-105 ≤ xi, yi ≤ 105, 1 ≤ si ≤ 105, 1 ≤ кi ≤ п). Таким образом, i-й енот лежит в форме квадрата с координатами (xi - si, yi), (xi, yi - si), (xi + si, yi), (xi, yi + si).
Формат выходных данных
Выходные данные должны содержать одно целое число — минимальное количество дней тренировок.
Пример
Задача C. Овцы на корабле
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунды
Ограничение по памяти: 256 мебибайт
Корабль, перевозящий огромное количество овец, сбился с курса и проводит в открытом море уже не первую неделю. Неудивительно, что овцы нервничают и блеют. Но дела шли не так уж и плохо, пока не появилась паникующая овца. Её блеяние может вызвать общую панику, которая в аварийной ситуации может оказаться фатальной.
Единственный способ избежать неприятных последствий — переселить овцу-паникёршу в клетку, где её не услышат. Все клетки с овцами на корабле представляют собой кубы равного размера 1x1x1. Все клетки составляют один общий куб размером п х п х п. Будем считать, что овца внесёт меньше всего суматохи, если громкость блеяния в той клетке, где она окажется, будет больше, чем во всех клетках, имеющих с ней общую стенку, пол или потолок. Необходимо найти такую клетку.
Задача осложняется тем, что количество времени ограничено, а используемый аппарат для измерения громкости блеяния способен работать ещё в четыре раза медленней, чем предыдущая его версия. Поэтому количество измерений, которое доступно, ограничено числом 5·п2.
Формат входных данных
В этой задаче вам потребуется реализовать интерактивное общение с проверяющей программой. В первой строке входных данных будет задано целое число п (п = 100)—размеры отсека с овцами. Далее ваша программа может подавать запросы по измерению уровня громкости блеяния в формате «? х у z», где х, у, z (1 ≤ x,y,z ≤ п)—координаты клетки, которую необходимо исследовать. В ответ на этот запрос ваша программа получит на стандартный ввод значение громкости в этой клетке.
Гарантируется, что все значения громкостей на корабле — различные целые числа от 1 до 109.
Формат выходных данных
Когда нужная клетка будет найдена, необходимо вывести в качестве запроса «! х у z», где х, у, z — её координаты.
Количество запросов типа «?» ограничено значением 5п 2. Запрос типа «!» необходимо сделать один раз, после чего программу следует завершить.
Следует обратить внимание на то, что из-за особенностей буферизации необходимо вызывать функцию flush(output) (Pascal), fflush(stdout) (C/C++) или cout. flushO (C++) после вывода каждого запроса.
Пример
Система оценки
На каждом тесте решение, выдающее верный ответ и делающее менее 0,5n2 запросов «?», получает полный балл. Решение, делающее от 0,5п2, но не более 5п2 запросов «?», получает половину баллов за этот тест.
Задача D. Игра в тетрис
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунды
Ограничение по памяти: 256 мебибайт
В процессе игры в Тетрис фигуры полиомино (т. е. связные фигуры, если идти по четырём направлениям) падают вниз в колодец из N строк и 20 столбцов. Каждая фигура помечена уникальной буквой английского алфавита от “А” до “Z”.
Требуется написать программу, которая должна по описанию колодца определять, в каком порядке падали блоки.
Формат входных данных
Первая строка входного файла содержит целое число N (0 ≤ N ≤ 50) — количество строк в колодце. Каждая из последующих строк содержит по 20 символов, каждый из которых — это либо буква от “А” до “Z”, либо символ “.” (ASCII 46), соответствующий пустой клетке.
Формат выходных данных
Выходные данные должны содержть строку букв, обозначающую порядок, в котором фигуры падали в колодец. Если есть более одного порядка, необходимо вывести такой порядок, при котором выведенная строка будет лексикографически минимальной. Гарантируется, что хотя бы один порядок всегда существует.
Подзадача 1
Дополнительные упрощения: не более 2 фигур.
Решение оценивается в 25 баллов.
Подзадача 2
Дополнительные упрощения: не более 7 фигур.
Решение оценивается в 25 баллов.
Подзадача 3
Дополнительные упрощения отсутствуют.
Решение оценивается в 50 баллов.
Пример
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
