Представьте, что вы состоите на службе во внешней разведке Межгалактического Альянса Республиканских Сил (МАРС). Одному из агентов разведки крупно не повезло, и он был захвачен на засекреченной космической базе. К счастью, внешней разведке МАРС удалось заполучить план этой базы. И вот теперь вам поручено разработать план побега.
База представляет собой прямоугольник размером NхM, со всех сторон окружённый стенами, и состоящий из квадратных отсеков единичной площади. База снабжена K выходами, до одного из которых агенту необходимо добраться. В некоторых отсеках базы находятся стены. Ваш агент может перемещаться из отсека в любой из четырех соседних с ним, если в том отсеке, куда он хочет переместиться, нет стены.
Кроме того, база снабжена системой гипертуннелей, способных перемещать агента из одного отсека базы (вход в гипертуннель) в другой (выход из гипертуннеля). Когда агент находится в отсеке, где есть вход в гипертуннель, он может (но не обязан) им воспользоваться.
Начальное положение вашего агента известно. Вам необходимо найти кратчайший путь побега (то есть путь, проходящий через минимальное количество отсеков).
В первой строке входного файла записаны числа N и M (2≤N≤100, 2≤M≤100), задающие размеры базы: N — количество строк в плане базы, M — количество столбцов. Во второй строке записаны начальные координаты агента XA,YA (1≤XA≤N, 1≤YA≤M). Первая координата задает номер строки, вторая — номер столбца. Строки нумеруются сверху вниз, столбцы слева направо.
Далее следуют N строк по M чисел, задающих описание стен внутри базы: 1 соответствует стенке, 0 — её отсутствию.
Далее в отдельной строке записано число H (0≤H≤1000) — количество гипертуннелей. В последующих H строках идут описания гипертуннелей. Каждый гипертуннель задается 4 числами: X1, Y1, X2, Y2 (1≤X1,X2≤N; 1≤Y1,Y2≤M) — координатами входа и выхода гипертуннеля. Никакие два гипертуннеля не имеют общего входа.
После этого в отдельной строке следует число K (1≤K≤10) — количество выходов с базы. В последующих K строках идут описания выходов с базы. Каждый выход задается двумя координатами X и Y (1≤X≤N; 1≤Y≤M).
Гарантируется, что начальные координаты агента не совпадают ни с одним из выходов и он не стоит в отсеке, занятом стеной. Никакие входы и выходы гипертуннелей, а также выходы с базы не находятся в отсеках, занятых стенами. Никакой вход в гипертуннель не совпадает с выходом с базы
Если побег невозможен, выведите единственную строку с надписью "Impossible". В противном случае в первой строке выдайте число L - количество отсеков в кратчайшем пути побега. В последующих L строках последовательно выведите координаты отсеков кратчайшего пути побега. Если решений несколько, то выведите любое из них.
4 5 2 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 2 1 4 3 1 1 4 1 2 4
4 2 1 3 1 1 4 2 4
В государстве алхимиков есть N населённых пунктов, пронумерованных числами от 1 до N, и M дорог. Населённые пункты бывают двух типов: деревни и города. Кроме того, в государстве есть одна столица (она может располагаться как в городе, так и в деревне). Каждая дорога соединяет два населённых пункта, и для проезда по ней требуется Ti минут. В столице было решено провести 1-ю государственную командную олимпиаду по алхимии. Для этого во все города из столицы были отправлены гонцы (по одному гонцу на город) с информацией про олимпиаду.
Напишите программу, которая посчитает, в каком порядке и через какое время каждый из гонцов доберётся до своего города. Считается, что гонец во время пути не спит и нигде не задерживается.
Во входном файле сначала записаны 3 числа N, M, K — количество населенных пунктов, количество дорог и количество городов (2N1000, 1M10000, 1KN). Далее записан номер столицы C (1CN). Следующие K чисел задают номера городов. Далее следуют M троек чисел Si, Ei, Ti, описывающих дороги: Si и Ei — номера населенных пунктов, которые соединяет данная дорога, а Ti — время для проезда по ней (1Ti100).
Гарантируется, что до каждого города из столицы можно добраться по дорогам (возможно, через другие населенные пункты).
Выведите в выходной файл K пар чисел: для каждого города должен быть выведен его номер и минимальное время, когда гонец может в нем оказаться (время измеряется в минутах с того момента, как гонцы выехали из столицы). Пары в выходном файле должны быть упорядочены по времени прибытия гонца.
5 4 5 1 1 2 3 4 5 1 2 1 2 3 10 3 4 100 4 5 100
1 0 2 1 3 11 4 111 5 211
5 5 3 1 2 4 5 2 1 1 2 3 10 3 4 100 4 5 100 1 5 1
5 1 2 1 4 101
Чтобы поднять в свой офис на N-м этаже небоскреба новый сейф, Вите опять пришлось прибегнуть к помощи грузчиков. Но за это время система оплаты изменилась. Теперь за подъем по лестнице на один этаж требуется заплатить U рублей, за спуск по лестнице на один этаж — D рублей, за внос в лифт — I рублей, за вынос из лифта — J рублей.
В офисе имеется L лифтов, каждый из которых останавливается лишь на определенных этажах.
Помогите Вите разработать маршрут подъема сейфа с первого этажа, стоимость которого наименьшая.
В первой строке входного файла записаны целые числа N, U, D, I, J, L. Каждая из следующих L строк описывает соответствующий лифт. Она начинается с числа Ki — количества этажей, на которых останавливается i-й лифт, за которым следует Ki натуральных чисел — этажи, на которых останавливается этот лифт (этажи для каждого лифта задаются в возрастающем порядке). 0≤U≤1000, 0≤D≤1000, 0≤I≤1000, 0≤J≤1000, 0≤L≤500, 1≤N≤1000000, 2≤Ki≤1000, K1+K2+…+KL≤100000. Количество этажей в небоскребе не превосходит 1000000.
В выходной файл выведите одно число — минимальную стоимость подъема сейфа.
Группы тестов:
10 1 1 1 1 1 2 3 7
7
10 1 1 3 2 1 2 3 7
9
20 100 0 1 1 2 2 5 7 2 8 17
804
Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).
Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.
Например, если N=5. Тогда изначально Васей выписана последовательность
1 2 3 4 5
Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.
Например, он может последовательно получить следующие последовательности:
2 1 3 4 5 (поменяв числа на 1 и 2 местах)
2 5 3 4 1 (поменяв числа на 2 и 5 местах)
5 2 3 4 1 (поменяв числа на 1 и 2 местах).
Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.
От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).
Напишите программу, которая поможет Пете справиться с этой задачей.
Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).
Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).
В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).
В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.
5 5 2 3 4 1 2 1 2 2 5
YES 3 1 2 2 5 1 2
5 2 3 4 5 1 2 1 2 2 5
NO
«Не плюй в телепорт: вылетит — не поймаешь!»
На зараженной радиацией планете некоторые точки соединены между собой гипер-каналами. Когда человек заходит в гипер-канал в одной точке, он мгновенно оказывается в другой. Все гипер-каналы двусторонние — то есть их можно использовать для перемещения в обоих направлениях (как из первой точки во вторую, так и из второй в первую).
К сожалению, гипер-каналы платные — каждый проход через гипер-канал стоит 10 у.е.
Перемещаться по поверхности планеты из одной точки в другую, не используя гипер-каналы, чревато для здоровья (радиация, однако!).
Напишите программу, которая определит, какой минимальной суммой у.е. должен располагать путешественник, чтобы добраться из одной точки в другую, не рискуя своим здоровьем.
Во входном файле записаны сначала два числа — начальные координаты расположения путешественника, затем еще два числа — координаты точки, куда ему надо попасть. Затем записано число N — количество гипер-каналов на планете (0N500). Затем идет N описаний гипер-каналов. Каждый гипер-канал описывается четверкой чисел. Первые два задают координаты одной из соединяемых гипер-каналом точек, последние два — координаты другой. Все координаты — целые числа, не превышающие по модулю 1000000.
В выходной файл запишите одно число — минимальную сумму, которой должен располагать путешественник для достижения цели. Если, не рискуя здоровьем, он не сможет добраться до конечной точки, запишите в выходной файл число 171717 (столько стоит лечение лучевой болезни на этой планете).
10 10 -10 -10 3 -10 -10 -10 -10 -10 -10 1 1 10 10 1 1
20