| Максимальное время работы на одном тесте: | 2 секунды |
| Максимальный объем используемой памяти: | 64 мегабайта |
|
|
|
Вася — начинающий программист. Последней его идеей было написать графический редактор черно-белых изображений. К сожалению, вдохновения хватило только на один инструмент — заливку.
В окне редактора картинка отображается как прямоугольная таблица M × N клеток; каждая покрашена либо в чёрный, либо в белый цвет. Две клетки назовём соседними, если у них имеется общая сторона. Областью же будем называть максимальное подмножество клеток одного цвета, такое, что из каждой можно попасть в каждую, перемещаясь только по соседним клеткам этой области.
Заливка работает следующим образом: пользователь указывает на произвольную клетку таблицы, после чего вся область, содержащая данную клетку, перекрашивается в противоположный цвет.
Теперь Вася хочет научиться стирать изображения с помощью своего редактора. Картинка считается чистой, если она либо полностью чёрная, либо полностью белая. Определите минимальное число заливок, которое потребуется для того, чтобы сделать из данного изображения чистое.
Формат входных данных
Вводятся два натуральных числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — количество строк и столбцов у таблицы, соответствующей данному изображению. В следующих N строках содержатся по M символов. В i‑й строке и j-м столбце стоит 0, если соответствующая клетка белая, и 1, если чёрная.
Формат выходных данных
Выведите одно число — минимальное количество заливок, требуемых для стирания данной картинки.
Пример
| Входные данные | Выходные данные |
| 3 5 10101 01010 10101 | 3 |
Рассмотрим расписание движения электричек на некоторой железнодорожной линии. Нас будут интересовать только электрички, идущие в одном направлении.
Каждая электричка отправляется с некоторой станции и следует до некоторой другой станции со всеми остановками. При этом средняя маршрутная скорость у каждой электрички своя (будем считать, что весь маршрут электричка проходит с этой скоростью, временем стоянки на станциях пренебрежем). Поскольку на участке только один путь в данном направлении — электрички в процессе следования друг друга не обгоняют.
Требуется выпустить книжку-расписание электричек. Обычно такая книжка представляет собой таблицу, где в первом столбце перечислены все станции, а каждый следующий столбец соответствует электричке: если электричка проходит через станцию, то в соответствующей клетке указывается время прохождения этой электрички через эту станцию, и прочерк, если электричка через эту станцию не проходит.
Естественно, что в книжке-расписании нужно расположить электрички так, чтобы они были указаны в хронологическом порядке. А именно, если две электрички имеют хотя бы одну общую станцию (даже если она является начальной станцией для одной, и конечной — для другой электрички), электрички в расписании должны идти в том порядке, в каком они проходят через эту станцию (поскольку электрички не обгоняют друг друга, то это же будет справедливо для всех общих станций этих двух электричек). Если же электрички не имеют ни одной общей станции, то они могут быть указаны в любом порядке.
По данному расписанию движения электричек определите порядок, в котором электрички должны идти в книжке—расписании.
Сначала вводится целое число N (1 ≤ N ≤ 1000) — количество электричек. Далее идёт описание электричек: каждая электричка задается четырьмя числами Ai, Bi, Ci, Di (0 ≤ Ai < Bi ≤ 106, 1 ≤ Ci ≤ 100, 0 ≤ Di ≤ 10000), которые обозначают, что данная электричка отправляется со станции «Ai-й километр» и следует до станции «Bi-й километр». Электричка отправляется с начальной станции в момент Ci. Один километр электричка проезжает за Di секунд.
Гарантируется, что расписание можно составить корректно, в частности, никакая электричка не обгоняет другую.
Выведите последовательность из N номеров от 1 до N – номера электричек в том порядке, в котором они должны идти в книжке-расписании. Если возможных ответов несколько, выведите любой.
Комментарий к примеру тестов
Ответ 2 3 1 также будет верным.
3 1 10 3 4 3 5 3 4 10 11 10 1
3 2 1
В начале XIX века еще не было самолетов, поездов и автомобилей, поэтому все междугородние зимние поездки совершались на санях. Как известно, с дорогами в России тогда было даже больше проблем, чем сейчас, а именно на N существовавших тогда городов имелась ровно N-1 дорога, каждая из которых соединяла ровно два города. К счастью, из каждого города можно было добраться в любой другой (возможно, через некоторые промежуточные города). В каждом городе имелась почтовая станция (или, как ее называют, «ям»), на которой можно было пересесть в другие сани. При этом ямщики могли долго запрягать (для каждого из городов известно время, которое ямщики в этом городе тратят на подготовку саней к поездке) и быстро ехать (также для каждого города известна скорость, с которой ездят ямщики из него). Можно считать, что количество ямщиков в каждом городе не ограничено.
Если бы олимпиада проводилась 200 лет назад, то путь участников занимал бы гораздо большее время, чем сейчас. Допустим, из каждого города в Москву выезжает участник олимпиады и хочет добраться до Москвы за наименьшее время (не обязательно по кратчайшему пути: он может заезжать в любые города, через один и тот же город можно проезжать несколько раз). Сначала он едет на ямщике своего города. Приехав в любой город, он может либо сразу ехать дальше, либо пересесть. В первом случае он едет с той же скоростью, с какой ехал раньше. Решив сменить ямщика, он сначала ждет, пока ямщик подготовит сани, и только потом едет с ним (естественно, с той скоростью, с которой ездит этот ямщик). В пути можно делать сколько угодно пересадок.
Жюри стало интересно, какое время необходимо, чтобы все участники олимпиады доехали из своего города в Москву 200 лет назад. Все участники выезжают из своих городов одновременно.
В первой строке входного файла дано натуральное число N, не превышающее 2000 — количество городов, соединенных дорогами. Город с номером 1 является столицей.
Следующие N строк содержат по два целых числа: Ti и Vi — время подготовки саней в городе i, выраженное в часах, и скорость, с которой ездят ямщики из города i, в километрах в час (0 ≤ Ti ≤ 100, 1 ≤ Vi ≤ 100).
Следующие N–1 строк содержат описания дорог того времени. Каждое описание состоит из трех чисел Aj, Bj и Sj, где Aj и Bj — номера соединенных городов, а Sj — расстояние между ними в километрах (1 ≤ Aj ≤ N, 1 ≤ Bj ≤ N, Aj ≠ Bj, 1 ≤ Sj ≤ 10000). Все дороги двусторонние, то есть если из A можно проехать в B, то из B можно проехать в A. Гарантируется, что из всех городов можно добраться в столицу.
Сначала выведите одно вещественное число — время в часах, в которое в Москву приедет последний участник.
Далее выведите путь участника, который приедет самым последним (если таких участников несколько, выведите путь любого из них). Выведите город, из которого этот участник выехал первоначально, и перечислите в порядке посещения те города, в которых он делал пересадки. Последовательность должна заканчиваться столицей.
При проверке ответ будет засчитан, если из трех величин «время путешествия по выведенному пути», «выведенное время» и «правильный ответ» каждые две отличаются менее чем на 0.0001.
Комментарий к примеру тестов
1. Участник из города 1 уже находится на своем месте и тратит на дорогу 0 часов. Участник из города 2 ждет 10 часов ямщика в своем городе, а затем проезжает 300 км от города 2 до города 1 за 10 часов, т.е. тратит на дорогу 20 часов. Участник из города номер 3 ждет ямщика 5 часов, а затем доезжает до города 1 за 10 часов, т.е. тратит на дорогу 15 часов. Участник из города 4 может доехать до города 1 с ямщиком из города 4 за 1 + 40 = 41 час или доехать до города номер 2 за 1 + 10 = 11 часов, прождать там 10 и доехать до столицы за 10 часов. Таким образом, он может добраться до города 1 минимум за 31 час. Это и есть самое большое время и ответ к задаче.
2. Участнику из города 2 выгоднее добраться сначала до третьего города, где ездят быстрее, а потом поехать в столицу, не делая пересадки в своём городе.
4 1 1 10 30 5 40 1 10 1 2 300 1 3 400 2 4 100
31.0000000000 4 2 1
3 1 1 0 10 0 55 1 2 100 2 3 10
3.0000000000 2 3 1
Зал Большого галактического театра состоит из \(S\) рядов, по \(S\) мест в каждом ряду.Продажа билетов на каждый спектакль происходит по следующему принципу: первые \(S^2 - N\) ценителей прекрасного приобретают билеты на любые места по их вкусу, а оставшиеся \(N\) кресел администрация бесплатно выделяет студентам, отдавая дань сложившимся традициям.
Во избежание обвинений в дискриминации по половому признаку, рассаживать студентов по этим \(N\) местам необходимо таким образом, чтобы:
Каждое место в зале определяется двумя числами от 1 до \(S\) - номером ряда и номером самого места в этом ряду. Студенческое кресло номер \(i\) расположено в \(a_i\)-м ряду и имеет в нём номер \(b_i\). Поскольку ценители прекрасного могли занять совершенно любые места, числа \(a_i\) и \(b_i\) могут принимать любые значения от 1 до \(S\). В частности, может оказаться так, что в каком-нибудь ряду не будет ни одного студенческого места.
Ради упрощения работы билетёров администрация обращается к вам с заданием написать программу, которая автоматизирует процесс распределения студенческих мест на мужские и женские.
Сначала вводятся два целых числа \(S\) и \(N\) (\(1 \le S \le 100\,000\), \(1 \le N \le \min\{100\,000, S^2\}\)). Далее расположены \(N\) пар натуральных чисел \((a_i, b_i)\), не превосходящих \(S\). Гарантируется, что все места различные.
Если искомого способа не существует, выведите Impossible.Иначе выведите единственную строку из \(N\) символов ‘M’ (мужское) и ‘W’ (женское). Символ на \(i\)-й позиции соответствует статусу \(i\)-го места в той же нумерации, в которой они были перечислены во входных данных.
Тесты состоят из четырёх групп.
2 2 2 1 1 2
MW
3 5 1 2 2 3 1 3 2 1 1 1
WMWWM
В государстве Древоландия есть \(N\) крупных городов, соединенных \(N - 1\) двухсторонними дорогами, причем из любого города можно добраться по этим дорогам до любого другого города. Экономика страны находится в зачаточном состоянии, а Владислав - один из первых бизнесменов в этой стране. В данный момент он подумывает о том, чтобы перевозить крупные партии товаров из одного города в другой.
Совсем недавно на дорогах страны появились \(M\) полицейских постов (они могут быть не на каждой дороге, и их может быть несколько на одной дороге). Все посты разбиты на \(P\) категорий, на одной дороге бывают посты только различных категорий. Полицейские очень любят переписываться с коллегами своей категории, а электронной почты в стране еще не существует, поэтому для передачи писем они используют проезжающих. Проезжая пост категории \(i\) без письма для полицейских этой категории, Владислав обязательно берет на посту письмо. Проезжая через очередной пост категории \(i\), Владислав обязательно отдает это письмо, причем новое письмо на этом посту он не получает. К концу поездки у Владислава не должно остаться ни одного письма.
Кроме того на дорогах страны попадаются разбойники и странники. Каждому разбойнику придется отдать одну монету, чтобы откупиться от него, а каждый странник заплатит одну монету за подвоз вдоль дороги на некоторое расстояние (но число странников на дороге от этого не меняется).
Для любой дороги Владислав знает, сколько разбойников и странников находится на ней в первый год его предпринимательства, и сколько новых будут появляться каждый год (это фиксированные числа, свои для каждой дороги). Владиславу также известно расположение всех полицейских постов и категория каждого их них. Заниматься бизнесом он планирует в течение \(K\) лет.
Помогите Владиславу для каждого года выбрать такой маршрут, чтобы он, перевезя груз из начала в конец, передал все врученные ему по пути письма и при этом получил максимальную прибыль (прибылью называется разница между деньгами, полученными от странников, и отданными разбойникам, в убыточные годы "прибыль" будет отрицательной). Каждый маршрут должен соединять два различных города, и в целях экономии времени не должен проходить по одной дороге дважды. От года к году маршрут может меняться (при этом маршрут в следующем году не обязан начинаться в том городе, в котором закончился маршрут в предыдущем году).
В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(K\). В следующей \((N - 1)\) строке идут описания каждой из дорог. Дорога сначала описывается четырьмя целыми числами \(S_i\), \(F_i\) - номера городов, которые эта дорога соединяет (\(1 \le S_i \le N\), \(1 \le F_i \le N\)), \(A_i\) - число странников на этой дороге в первый год, \(B_i\) - число разбойников на этой дороге в первый год, \(C_i\), \(D_i\) - ежегодные прирост числа странников и числа разбойников соответственно. Затем идет число \(E_i\) - количество постов на этой дороге, а после него \(E_i\) различных натуральных чисел, не превосходящих 20, обозначающих категории постов. Все числа целые и неотрицательные.
Гарантируется, что общее количество всех постов равно \(M\), а также что в течение этих \(K\) лет количество как странников, так и разбойников на каждой дороге не превзойдет \(10\,000\).
Выведите \(K\) чисел - максимальную прибыль, которую можно получить в каждый из \(K\) годов (в том числе отрицательную для убыточных годов). В случае, если в какой-то из годов нет ни одного маршрута, на котором Владислав мог бы передать все врученные ему письма, выведите "Sadness!" (без кавычек).
Тесты состоят из четырех групп.
2 2 2 2 1 7 1 6 10 2 1 2
Sadness! Sadness!
5 5 10 3 2 2 4 8 4 0 4 1 3 10 8 7 2 2 1 4 5 6 8 8 10 2 1 2 1 3 2 5 6 1 1 1
-2 2 6 10 14 18 22 26 30 34
14 14 2 1 3 48 28 23 0 1 1 4 5 25 20 25 7 1 4 3 2 23 16 100 50 1 4 11 9 179 2 57 54 1 2 13 7 30 4 27 23 1 2 10 1 23 6 63 70 2 4 1 3 8 17 7 10 5 0 12 13 34 17 43 67 1 4 4 3 10 4 1 6 1 2 6 1 23 11 38 38 2 2 4 9 8 50 13 0 0 1 1 8 13 43 15 18 19 1 2 10 14 14 40 50 1 1 2
67 111