Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 74 задач <---
Страница: << 8 9 10 11 12 13 14 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В Шахматной Стране всегда пользовались популярностью различные спортивные соревнования: ферзебол, рокировочная борьба, эндшпилевые бега. Но наибольшую популярность в этом году получила спортивная игра «обмен королей».

Суть её заключается в следующем. Двух королей (белого и чёрного) ставят на прямоугольное шахматное поле, некоторые клетки которого отмечены как недостижимые. По правилам игры короли делают ходы по очереди (сначала белый, а затем чёрный), не наступая на недостижимые клетки. Игра считается успешно законченной, если черный и белый короли поменялись местами. В соревновании побеждает та пара королей, которая смогла поменяться местами за минимальное количество ходов.

Напомним, что в шахматах король имеет право переместиться из своей клетки в любую из 8 соседних по вертикали, диагонали или горизонтали, при условии, что она не является соседней для другого короля.

Напишите программу, которая по информации о доске найдет минимальное количество ходов, необходимое для успешного окончания игры.

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

В первой строке входных данных даны целые числа N и M (1 ≤ N, M ≤ 8) — размеры доски по вертикали и по горизонтали, соответственно. В следующих N строках даны M символов — состояние доски в начале игры. Символ «.» обозначает пустую клетку, символ «*» — недостижимую клетку, символ «W» — белого короля, «B» — черного короля. Гарантируется, что символы «W» и «B» встречаются на поле ровно по одному разу, и короли не находятся в соседних клетках изначально.

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

В выходной файл необходимо вывести минимальное количество ходов, которое потребуется для того, чтобы белый король поменялся местами с чёрным. В случае, если поменять королей местами невозможно, требуется вывести «Impossible» без кавычек.

Примеры тестов

Входные данные
4 3
*.*
W.B
...
*.*
Выходные данные
8
Входные данные
2 3
W..
..B
Выходные данные
Impossible

Примечание

Последовательность ходов, необходимая для обмена королей в первом тесте, приведена на рисунке:

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

В стране Триландии близятся выборы новых столиц. Столицы в Триландии необычные, поскольку ими являются одновременно сразу три различных города. Такая идея размещения столиц основана на исследованиях эффективности управления страной, выполненных ведущими экономистами Триландии.

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

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

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

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

Первая строка входного файла содержит два разделенных пробелом целых числа: количество городов в Триландии n и требуемое время в пути между столицами d (\(3 \leq n \leq 10^5\), \(1 \leq d < n\)). Каждая из последующих (n – 1) строк содержит описание одной дороги: пару разделенных пробелом различных целых чисел \(a_i\) и \(b_i\) — номера городов, которые соединены двусторонней дорогой (\(1 \leq a_i \leq n\), \(1 \leq b_i \leq n\), \(a_i \ne b_i\)). Каждая пара городов соединена не более чем одной дорогой.

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

Выходной файл должен содержать одно целое число — количество подходящих троек городов, которые могут быть выбраны столицами. В случае, если нужных троек городов не окажется, выходной файл должен содержать ноль.

Пояснения к тестам

В первом примере существует единственный способ выбрать три столицы: города под номерами 2, 3 и 4. Рисунок, соответствующий первому примеру, приведен ниже.

Во втором примере существует четыре варианта выбора трёх столиц из четверки городов: 2, 3, 4 и 5. Можно также выбрать столицами города с номерами 1, 6 и 7. Рисунок, соответствующий второму примеру, приведен ниже.

Система оценивания

Правильные решения для тестов, в которых 3 ≤ n ≤ 50, будут оцениваться из 20 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 500, будут оцениваться из 40 баллов.

Правильные решения для тестов, в которых 3 ≤ n ≤ 5000, будут оцениваться из 60 баллов.

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

Фирма, в которой работает ваш друг, решила воспользоваться удобным моментом и купила компанию, занимающуюся пригородными автобусными пассажирскими перевозками. Таким образом, фирма вашего друга расширяет область деятельности и будет теперь обслуживать и некоторые внутриобластные автобусные маршруты.

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

Система дорог в области устроена следующим простым образом. Есть \(N\) населённых пунктов, некоторые из которых соединены дорогами. Между каждой парой пунктов существует не более одной дороги, и более того, для каждой пары населённых пунктов есть ровно один способ добраться из одного в другой (возможно, через промежуточные посёлки).

В каждом населённом пункте можно разместить ремонтную подстанцию. В принципе, фирма может размещать как крупные подстанции, которые даже в одиночку смогут обслуживать всю область, но при этом будут требовать больших расходов на содержание, так и небольшие станции, которые будут обслуживать лишь прилегающие населённые пункты, но при этом будут обходиться намного дешевле. Фирма уже определила, что каждую подстанцию можно характеризовать параметром “мощность”, которая может принимать значения, являющиеся целыми положительными числами (равна нулю мощность быть не может). Подстанция с мощностью \(k\) будет обслуживать населённый пункт u, в котором она расположена, и все другие населённые пункты, до которых можно добраться из u, использовав не более k дорог (т.е. при \(k\)=1, например, подстанция обслуживает свой населённый пункт и все, которые напрямую соединены с ним дорогой). Стоимость содержания такой подстанции пропорциональна её мощности.

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

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

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

В первой строке входного файла находится одно число \(N\) — количество населённых пунктов в области (1<=\(N\)<=300). Далее следуют \(N\)−1 строка, описывающая дороги. Каждая строка содержит два числа — номера населённых пунктов, которые соединяет эта дорога. Населённые пункты нумеруются от 1 до \(N\).

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

В первую строку выходного файла выведите одно число — оптимальную суммарную мощность подстанций. Далее выведите \(N\) чисел, описывающих какое-нибудь оптимальное решение. \(i\)-ое из этих чисел должно быть равно мощности подстанции, которую в вашем решении надо расположить в пункте \(i\), или 0, если в населённом пункте \(i\) не должна находиться подстанция.

Примеры
Входные данные
5
1 2
1 3
1 4
1 5

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

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

Маленький Петя очень любит компьютеры и хочет научиться программировать.

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

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

Перед тем как сесть составлять порядок посещения кружков, Петя внимательно перечитал условия обучения и обнаружил ещё один важный пункт. Оказывается, для привлечения школьников, во всех кружках действует система поощрения учеников конфетами. Это означает, что по окончании очередного кружка ученику выдают несколько коробок конфет, всё больше и больше с каждым пройденным кружком. С другой стороны, в каждом кружке количество конфет в коробке своё, зависящее от сложности курса. Более конкретно — за прохождение i-го по счёту кружка, если этот кружок идёт в общем списке под номером j, ученику выдают аж Ni - 1·j конфет — такие щедрые люди программисты.

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

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

В первой строке входного файла содержится целое число N (1 ≤ N ≤ 100 000) — количество кружков в Маховниках.

В последующих N строках идут описания входных требований кружков, в порядке их следования в общем списке. В i-ой строке сначала записано целое число ki (0 ≤ ki ≤ N - 1) — количество кружков, в которых нужно отучиться перед записью в i-й кружок, а потом ki номеров этих кружков.

Сумма ki не превосходит 200 000.

Гарантируется, что возможно посетить все эти кружки в некотором порядке, не нарушая условия посещения.

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

Выведите N номеров, разделённых пробелами — порядок, в котором Пете надо посещать кружки, чтобы съесть как можно больше конфет.

Примеры тестов

Входные данные
6
1 2
0
1 2
3 1 2 5
1 2
4 1 3 4 5
Выходные данные
2 1 3 5 4 6

Примечание

Пояснение к примеру. Посещая кружки в указанном порядке, Петя получит 60·2 + 61·1 + 62·3 + 63·5 + 64·4 + 65·6 = 2 + 6 + 108 + 1080 + 5184 + 46656 = 53036 конфет.

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

Сеть компьютерных салонов «ХТТП» представлена в городе Н. двумя магазинами. Руководство Н-ского отделения сети решило реорганизовать витрины, на которых представлены ноутбуки. В каждом из двух магазинов на витрине должны быть представлены \(N\) моделей ноутбуков, выставленные в ряд от касс вглубь помещения магазина. Маркетологи каждого из магазинов уже определили порядок, в котором на витрине должны быть расположены эти модели (эти порядки в двух магазинах, конечно же, могут быть разными).

На витрины надо выставлять специальные, выставочные, образцы ноутбуков, с соответствующим программным обеспечением, показывающим рекламу, и т.д. В распоряжении администрации компьютерных салонов есть две версии специализированного ПО: работающие под управлением операционных систем Windows и Linux. Соответственно, каждый из выставочных образцов ноутбуков должен иметь предустановленной ровно одну из этих систем.

Для снижения затрат было принято решение закупить по два идентичных экземпляра каждой модели ноутбуков (т.е. с одинаковыми предустановленными операционными системами), отправить по одному экземпляру в каждый из магазинов сети, и расставить их на витрине в соответствии с порядком, определенным маркетологами того магазина.

Но при этом возникла проблема. По требованиям Федеральной антимонопольной службы, компьютерные салоны не должны предоставлять преимущества ни одной из операционных систем. Начальство сети «ХТТП» знает, как проходит проверка на соответствие этой норме законодательства. Инспектор антимонопольной службы идет по магазину начиная от касс вдоль витрины с ноутбуками, считает отдельно количество встреченных ноутбуков с Windows и Linux, а также модуль разности этих чисел (т.е. на сколько ноутбуков с одной системой он встретил больше, чем ноутбуков с другой системой). В некоторый момент он останавливается и говорит: «Ага!». Это значит: слишком у вас большой дисбаланс между операционными системами, поэтому платите штраф. Размер штрафа пропорционален разнице (взятой по модулю) количества ноутбуков с разными системами, которые увидел инспектор.

Естественно, руководство сети не в состоянии предсказать, в какой из магазинов пойдет инспектор, а также сколько ноутбуков он просмотрит. Тем не менее, они хотят минимизировать штраф, который им будет выписан в худшем случае. Помогите им.

Например, пусть \(N=5\): в магазинах должны быть выставлены пять моделей ноутбуков. Будем нумеровать модели ноутбуков от 1 до 5. Пусть в первом магазине маркетологи определили, что оптимальный порядок ноутбуков следующий (от касс вглубь зала):

2 4 1 3 5,

а во втором магазине —

3 1 2 5 4.

Тогда, если закупить ноутбуки моделей 1, 3 и 4 с операционной системой Windows, а 2 и 5 — с Linux, то порядок операционных систем в магазинах будет следующий (от касс вглубь зала):

L W W W L,

W W L L W.

Тогда, если, например, инспектор придет в первый магазин и просмотрит первые четыре ноутбука, то он скажет: «Ага!», и выпишет штраф за то, что он увидел Windows-ноутбуков на два больше, чем Linux. Аналогичный результат будет, если он придет во второй магазин и просмотрит только первые два ноутбука.

А если закупить ноутбуки 2 и 3 с системой Linux, а 1, 4, 5 — с Windows, то порядок операционных систем будет следующий:

L W W L W,

L W L W W,

и в какой бы магазин не пришел инспектор, и сколько бы ноутбуков он не посмотрел, разница Windows- и Linux-ноутбуков не будет превосходить по модулю 1, и это и будет оптимальным вариантом для руководства сети. (Напомним, что инспектор всегда начинает осмотр магазина от касс и идет вглубь магазина вдоль ряда с ноутбуками).

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

В первой строке входного файла записано одно число \(N\) (\(1\leq N\leq 10^5\)) — количество моделей ноутбуков, которые должны быть представлены на витрине. Модели ноутбуков нумеруются от 1 до \(N\).

Далее следуют две строки по \(N\) чисел в каждой — порядки моделей ноутбуков на витрине, определенные маркетологами первого и второго магазина, от касс вглубь зала. Гарантируется, что порядки корректные, т.е. что в каждой из этих строк все числа находятся в интервале от 1 до \(N\) и никакое из чисел не встречается в одной строке дважды.

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

В выходной файл выведите строку из \(N\) символов, описывающих необходимую конфигурацию ноутбуков. А именно, \(i\)-ый символ должен быть “W” (без кавычек), если \(i\)-ую модель ноутбуков надо закупать с предустановленной системой Windows, и “L” для Linux.

Если есть несколько оптимальных решений, выведите любое.

Примеры
Входные данные
5
2 4 1 3 5
3 1 2 5 4
Выходные данные
WLLWW
Входные данные
5
1 4 2 3 5
5 1 3 4 2
Выходные данные
WLWLL

Страница: << 8 9 10 11 12 13 14 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест