Страница: << 2 3 4 5 6 7 8 >> Отображать по:
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-вверх и вправо-вверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. О том, что пешка может превращаться в ферзя Глеб не подозревает. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоят P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, их цель — побить все чёрные фигуры.

Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел побить белыми пешками все чёрные фигуры, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть, и, в случае успеха, выведите правильную последовательность ходов белых пешек.

Входные данные

Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ 1000, K ≤ (M - 1)N). Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — координаты (строки и столбцы) чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).

Выходные данные

Если пешки не смогут съесть все фигуры, выведите единственное слово NO.

В противном случае в первую строку выведите YES, вторая строка должна содержать суммарное число перемещений C, последующие C строк — описание ходов пешек, по одному ходу на каждую строку. Каждый ход задаётся двумя координатами r, c пешки (номерами строки и столбца), которая будет ходить, и символом m, принимающем три значения: L, R, F — побить вперед и влево, побить вперед и вправо, сделать шаг вперед соответственно. Данные о ходе следует выводить разделёнными одним пробелом, сначала координаты, потом тип хода.

Если последовательностей ходов несколько, выведите любой из них. Обратите внимание, что минимизировать количество перемещений не требуется.

Примеры
Входные данные
2 2 2 1
1 2
2 2
Выходные данные
YES
1
1 1 R
Входные данные
3 3 2 2
1 3
3 1
3 3
Выходные данные
NO
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Каждый раз, когда в мире происходит значимое событие, наша реальность разветвляется на несколько — в зависимости от исхода этого события. После этого существует уже не только наша основная реальность, но и ответвившиеся от неё в моменты появления разных исходов.

Однажды один архимаг решил сделать мир лучше. Такая грандиозная задача не под силу одному архимагу, поэтому он решил найти самого себя ещё в K реальностях и выполнить эту задачу вместе. Проведённое теоретическое исследование показало, что, кроме реальности, в которой находится именно он, существует ещё N - 1 реальностей. Для удобства они были занумерованы числами от 1 до N, при этом его собственная реальность имеет номер 1, а посетить ему необходимо реальности с номерами 2, 3, ..., K + 1.

Как уже говорилось, каждая реальность когда-то ответвилась от некоторой другой, за исключением одной Начальной реальности, которая существовала всегда (её номер может оказаться каким угодно; считается, что она появилась в момент времени 0). Исследование показало, что реальность с номером i ответвилась от реальности с номером Pi в момент времени Ti. Из каждой реальности с номером i архимаг может переместиться

  • в любую ответвившуюся от неё, то есть в любую j, такую что Pj = i;
  • в Pi, если i — не Начальная реальность.
Другими словами, возможны лишь переходы вида i <-> Pi. На каждый такой переход в любую сторону архимаг затрачивает Ti - TPi > 0 условных единиц энергии.

Требуется найти минимальное количество энергии, которое потребуется архимагу, чтобы, начав в реальности с номером 1, посетить все реальности с номерами от 2 до K + 1 (в любом порядке) и затем вновь вернуться в 1. Любую реальность при этом разрешается посещать сколько угодно раз.

Входные данные

Сначала вводятся два целых числа N и K (0 ≤ K < N ≤ 100 000): количество доступных реальностей и количество реальностей, которые необходимо посетить. Далее идёт N пар целых чисел, i-я пара — это Pi и Ti (1 ≤ Pi ≤ N, 0 ≤ Ti ≤ 106; для Начальной реальности Pi = Ti = 0).

Гарантируется, что ответвившаяся реальность появилась строго позже породившей (Ti > TPi), и что маг может при желании добраться до любой из N реальностей.

Выходные данные

 

Выведите единственное число E — минимальную возможную энергию, которая потребуется архимагу для путешествия.

Примеры
Входные данные
5 2
4 2
4 6
1 9
0 0
1 7
Выходные данные
30
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В первом классе Глеб увлекался шахматами. К тому моменту он знал только лишь как ходит пешка: она может бить по диагонали влево-наверх и вправо-наверх, и ходить на клетку вверх только если та клетка не занята другой фигурой. Поэтому он придумал свой вариант шахмат.

Игра идёт на доске с N строками и M столбцами (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) по следующим правилам. В нижней строке, имеющей номер 1, стоит P белых пешек, белых фигур на доске больше нет. На остальной части доски стоят разные чёрные фигуры (их названия Глеб не знает). Ходят только белые, цель — достичь хотя бы одной пешкой самой верхней строки, имеющей номер N (Глеб слышал, что в этой ситуации из пешки можно сделать ферзя, а с такой силой он безусловно сможет побить все остальные чёрные фигуры).

Как и в настоящих шахматах, если пешка Глеба бьёт чёрную фигуру, то она становится на её место, а побитая фигура убирается с доски. Считается, что Глеб выиграл, если он сумел достичь хотя бы одной пешкой самой верхней строки, в противном случае он проиграл. Помогите ему по заданной конфигурации всех фигур определить, сможет ли он выиграть.

Входные данные

Сначала вводятся четыре целых числа N, M, P, K (1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 0 ≤ P ≤ M, 1 ≤ K ≤ (N - 1)M. Далее записано P различных чисел — номера столбцов pj (1 ≤ pj ≤ M), в которых стоят белые пешки. Далее идут K различных пар целых чисел — номера строк и столбцов чёрных фигур ri, ci (2 ≤ ri ≤ N, 1 ≤ ci ≤ M).

Выходные данные

Если хотя бы одна пешка сможет достичь последнего ряда, выведите YES, в противном случае выведите NO.

Примеры
Входные данные
3 3 2 3
1 3
2 2
3 1
3 3
Выходные данные
YES
Входные данные
4 4 2 4
1 4
3 1
3 2
4 2
4 4
Выходные данные
NO
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Джон работает на огромной парковке. Парковка представляется собой прямоугольное поле \(n \times m\), разбитое на \(n \times m\) квадратных позиций размера \(1 \times 1\). Одну из угловых позиций занимает выезд с парковки.

Машин на парковке много и вывести машину не так уж просто. Единственное, что Джон может сделать — это переместить один из автомобилей на соседнюю позицию, если она свободна. Соседними считаются позиции, имеющие общую сторону. Однако задача усложняется наличием на парковке столбов. На позиции, где стоят столбы, нельзя поставить машину. Парковка вся занята машинами и столбами и единственное свободное место — выезд с парковки. Задача Джона — вывести с парковки один из автомобилей. Помогите ему узнать, какое минимальное число действий ему придется совершить.

Входные данные

В первой строке входного файла два целых числа \(n\) и \(m\) (\(1 \le n, m \le 50\)) — размеры парковки. Далее следуют \(n\) строк по \(m\) символов в каждой. Символ «.» означает пустую позицию, единственная пустая позиция — выезд с парковки. Символ «#» означает столб. Столбы нельзя перемещать и на место столба нельзя ставить автомобили. Символ «c» означает автомобиль. Символ «X» — автомобиль, который необходимо вывести с парковки. Автомобиль считается выведенным, как только он достигает выезда с парковки. Гарантируется, что хотя бы одно из чисел \(n\), \(m\) больше единицы и каждый из символов «.» и «X» встречается во входном файле ровно один раз. Символ «.» всегда располагается в верхнем левом углу парковки.

Выходные данные

Если машину вывести невозможно, выведите в выходной файл единственное слово «Impossible». Иначе в единственной строке выведите единственное число — минимальное количество действий для вывода автомобиля.

ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

2390 год. В заброшенном метрополитене города N-ска завелась громадная змея-мутант. Она ползает вдоль перегонов между станциями, повергая в ужас случайно забредающих под землю потомков людей. Размеры змеи настолько велики, что иногда голова появляется на той станции, вдоль которой еще ползет какая-то другая часть тела, и змея повергает в ужас сама себя. Чтобы избавиться от этой проблемы, змея поймала вас и потребовала написать для нее программу, которая может ей прокладывать кратчайший маршрут для головы от одной станции до другой, не проползая при этом по станциям, где находятся участки ее тела.

Будем называть маршрутом последовательность станций, каждые две последовательные из которых соединены перегоном.

Все перегоны в метрополитене имеют одинаковую длину, а змея имеет длину в \((l - 0.5)\) перегонов. Змея может ползти вдоль перегонов, переползая с одного на другой на станциях. Змея может ползти вдоль перегона только в один слой, а ее голова не может появляться на станции, если в этот момент по станции проползает другая часть ее тела. Змея умеет ползать только головой вперед.

С точки зрения теории графов метрополитен города N-ска является вершинным кактусом. Это означает, что ни одна станция не лежит на двух различных циклических маршрутах и никакие два перегона не соединяют одну и ту же пару станций, никакой перегон не соединяет станцию саму с собой, от каждой станции до любой другой до появления змеи можно было добраться по перегонам.

По заданным карте метрополитена, начальному положению змеи и станции, на которую змея хочет поместить свою голову, выясните, какое минимальное количество перегонов придется проползти змее.

Входные данные

В первой строке ввода записано два числа \(n\) и \(k\) — количество станций и количество перегонов в метрополитене (\(1 \le n, k \le 100\,000\)). В следующих \(k\) строках записано по два различных целых числа \(a\) и \(b\) — номера станций, соединенных соответствующим перегоном.

В следующей строке записано единственное число \(l\), характеризующее длину змеи. В следующей строке записано \(l + 1\) число: номера станций, на которых лежат последовательные части змеи, начиная с головы, а также номер станции, в перегоне к которой лежит хвост змеи длиной в \(0.5\) перегона. Исходно змея расположена таким образом, что ни в каком перегоне не находится одновременно две различных части змеи и змея не пересекает себя ни на какой станции.

В последней строке записано единственное целое число — станция, на которую змея хочет поместить свою голову.

Выходные данные

Если змея сможет выполнить свою задачу, выведите длину пути — количество перегонов, через которые необходимо проследовать голове змеи.

Если задача невыполнима, выведите единственное число \(-1\).


Страница: << 2 3 4 5 6 7 8 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест