Задачи 3 тура NetOI-2018.

Решения принимаются до 0 часов 26 января 2019

Задача Typo. На компьютерах серии "Буг" каждая буква задается матрицей в N строк и M столбцов, каждый пиксель которой или черный, или белый. Введем понятие кернинга между соседними символами. Кернингом назовем сумму расстояний (то есть количество белых пикселей) между самой левой черным пикселем правой буквы и самый правый черным пикселем левой буквы по каждой строке. К примеру, пусть N = M = 3 и мы рассматриваем два соседних символа. В данном случае в первой строке расстояние равно 1, во втором 2, в третьем 1, поэтому суммарно имеем 4 и ,следовательно, кернинг будет 4.

Вам данные очерки N символов (причем каждый символ содержит хотя бы один черный пиксель в каждой строке). Нужно определить, можно ли из них составить последовательность (возможно, с повторами) так, чтобы сумма кернингом между всеми парами соседних букв составляла ровно X. В пустого строке суммой кернингом будет 0. Поскольку это очень важная задача, мы попросим вывести ответ для многих запросов.

 Технические условия. Программа Typo читает с устройства стандартного ввода 3 целых числа N, M, K (1 ≤ N, M, K ≤ 100) - размеры матрицы, задающие каждый символ и количество символов. Далее следуют K * N строк по M символов, причем каждые N последовательных строк задают очерк определенного символа. "#" (Символ решетки) при этом означает черный пиксель, '.' (Символ точки) - белый. Далее следует число Q- количество запросов, после чего следуют Q целых неотрицательных чисел (каждое не превышает 109) - собственно, запросы. Программа должна вывести ровно Q символов "Y" в случае, если соответствующий запрос ответ "да" (то есть можно составить последовательность из символов с соответствующим кернингом) или "N" в противном случае.

Пример

Ввод           

3 3 2

.##

##.

.##

.#.

.#.

.#.

3

4 5 2

Вывод

YYN

Задача Travel2018. В большом городе все жители ездят только автобусами. Жители вынуждены тратить время, экономя деньги - одноразовые билеты дорогие. Поэтому пассажиры пытаются планировать поездки так, чтобы пересаживаться с маршрута на другой как можно меньшее количество раз. Хорошо, что в городе на каждой остановке висит расписание движения автобусов по всем маршрутам. Напишите программу, которая поможет доехать из одной выбранной остановки на другую, используя минимальное количество одноразовых билетов.

 Технические условия. Программа Travel2018 читает из стандартного устройства ввода в первой строке четыре целых числа, разделенные пробелами: количество автобусов N, количество остановок в городе M, число A - остановка, где пассажир начинает поездку и число В - остановка, куда хочет доехать пассажир. Автобусы нумеруются от 1 до N, остановки - от 1 до M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 1000, 1 ≤ A, B ≤ M; A ≠ B.) Следующие М строк содержат списки остановок автобусов. (I + 1) -й строку описывает i-ю остановку: первое целое число Li (1 ≤ Li ≤ N) - количество автобусов, останавливающихся на ней, а далее Li целых чисел, разделенных пробелами - номера маршрутов этих автобусов. Гарантируется, что решение существует. Программа выводит на стандартный вывод одно целое число K - минимальное количество одноразовых билетов, чтобы доехать от А до B. 

Задача Cezar. Над строкой из N букв латинского алфавита немного поиздевались. Сначала пронумеровали все суффиксы от 1 до N, начиная слева направо. Например, в строке "abc" суффикс "abc" - первый, суффикс "bc" - второй, суффикс "c" - третий. Далее отсортировали суффиксы в алфавитном (лексикографическом) порядке. После этого все суффиксы заменили их номера. Полученную последовательность назовем характеристической для этой строки.
К сожалению, начальная строка была потеряна, но к счастью, осталась характеристическая последовательность и другую строку из N букв латиницы. Кроме того, в вашем распоряжении имеется шифратор. Этот автомат принимает на вход две строки - один из N букв (источник), другой ровно с 26 букв (ключ). Шифратор заменяет все вхождения буквы "a" в источнике на первую букву из ключа, все вхождения буквы "b" на вторую букву ключа (всего все вхождения i-той буквы латиницы в источнике на i-й символ в ключе). Необходимо найти такой ключ с 26 букв, который бы в паре с данным в условии источником из N букв давал строку с данной характеристической последовательностью. При этом искомый ключ должен быть перестановкой букв латинского алфавита, то есть каждая буква должна встречаться там ровно один раз.
Технчични условия. Программа Cezar читает с устройства стандартного ввода натуральное число N (не превышает 100 000) - количество символов во входной строке. С другой строке программа имеет читать перестановку из N натуральных чисел - характеристическую последовательность. В третьей строке ровно N маленьких символов латиницы - источник.
Программа выводит на устройство стандартного вывода ровно 26 символов латиницы в случае, если существует некоторое ключ, который мог бы в паре с источником при преобразовании в шифраторе дал бы строчку, характеристическая последовательность которой указана во второй строке входных данных. Если таких ключей несколько, выведите лексикографически минимальный. Если ни одного возможного ключа нет, выведите IMPOSSIBLE.

Комментарий ко второму примеру: при замене буква "a" перейдет в "c", буква "b" перейдет сама в себя, а буква "c" перейдет в букву "a". Соответственно, по лексикографическим порядком, "abc" < "bc" < "c", то есть суффиксы отсортированы как 1 2 3.

Задача Lib2019. В поисках задач для третьего тура олимпиады NetOI-2018 два члена жюри решили посетить помещение, где хранятся бумажные архивы старых олимпиад «догугливской» эпохи. Архив размещен в просторном зале в форме многоугольника без самопересечений (но не обязательно выпуклый). Коллеги решили, что безопаснее будет не терять друг друга из виду. На каком максимальном расстоянии могут находиться коллеги, чтобы не терять друг друга из виду и не выходить за пределы архива? Члены жюри видят друг друга, если между ними можно провести отрезок, ни одна из точек которого лежала бы извне архива.

Технические условия. Программа Lib2019 читает с клавиатуры число N (3 ≤ N ≤ 300) количество вершин многоугольника. Далее следуют N пар целых чисел (каждое из которых не превышает 1000 по абсолютной величине) - координаты вершин многоугольника в порядке обхода по или против часовой стрелки. Многоугольник не имеет ни самопересечений, ни самокасаний. Программа должна вывести единственное число - ответ на задачу с точностью не менее 5 знаков после запятой.

Пример

Задача Words2018. Квадратная таблица размеров NxN заполняется заглавными буквами латинского алфавита Первую букву алфавита вставляют в любую свободную ячейку, затем вторую и т.д. После последней буквы алфавита (если есть еще пустые ячейки), буквы снова начинаются от начала алфавита. Данo слово. Напишите программу, которая будет находить маршрут в таблице от верхнего левого поля до правого нижнего, где каждая буква из данного слова появится на пути хотя бы один раз. Порядок букв на маршруте не имеет значения. Длина маршрута (количество посещенных клеток, включая х начальной и конечной) должна быть минимальной. Если ячейка несколько раз входит в маршрут, то она подсчитывается столько же раз. Возможно переходить из одной ячейки в другую, если они имеют общую сторону, но нельзя переходить «снизу вверх», то есть нельзя вернуться на предыдущую строку. Гарантируется, что решение всегда существует.

Технические условия. Программа Words2018 читает с устройства стандартного ввода целое число N в первой строке - это размер таблицы, во втором - слово, которое мы ищем. N> 5, K> 0, N*K≤81. здесь K - количество букв в слове. Далее программа читает таблицу букв в следующих N строках. Каждая строка содержит N букв без пробелов. Предполагается, что строки нумеруются (начиная с единицы) сверху вниз, столбцы (начиная с единицы) - слева направо. Программа выводит на устройство стандартного вывода единственное число - минимальную длину пути. Сам путь выводить не нужно.