Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 25 26 27 28 29 30 31 >> Отображать по:
#1386
Праздничные открытки
  

Петя с Васей решили поздравить всех своих одноклассниц с Международным Женским Днем. Важной частью любого праздника являются открытки. Купив их достаточно, друзья сели писать пожелания. Подписанные открытки они складывали на специальный стол, расчерченный в квадратную клетку параллельно краям стола так, что длина и ширина его составляли N и M клеток соответственно. По удивительному совпадению каждая открытка была размером точь-в-точь с две клетки стола. Петя настоял на том, чтобы класть подписанные поздравления строго по линиям сетки — горизонтально или вертикально, накрывая одной открыткой ровно две клетки.

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

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

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

В первой строке входного файла записаны два целых числа N и M (1 ≤ N, M ≤ 700) — длина и ширина стола. Гарантируется, что хотя бы одно из N, M четное. Будем считать, что все открытки занумерованы числами от 1 до NM. Следующие 2N строк содержат по M чисел: первые N строк описывают нижний слой, следующие N строк — верхний слой. Число k в i-й строке j-м столбце нижнего или верхнего слоя означает наличие на этой позиции одной из половинок открытки номер k.

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

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

В выходной файл запишите единственное слово NO, если не существует способа извлечь половину открыток нужным образом. В противном случае в первую строку выведите YES, во вторую — последовательность из NM/2 номеров открыток, которые надо достать, в правильном порядке. У каждой из них на момент извлечения хотя бы одна из половинок должна находиться сверху. Если искомых последовательностей несколько, выведите любую из них.

Частичные ограничения

Первая группа состоит из тестов, в которых произведение NM ≤ 24.

Вторая группа состоит из тестов, в которых N, M ≤ 100.

Примеры
Входные данные
2 2
1 1
3 2
4 2
4 3
Выходные данные
YES
4
2
Входные данные
2 3
1 1 4
2 3 4
2 6 5
3 6 5
Выходные данные
YES
2
6
5
#1472
Игрушечный лабиринт
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий – выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).

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

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

В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.

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

Выведите единственное число – минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.

Примеры
Входные данные
4 5
0 0 0 0 1
0 1 1 0 2
0 2 1 0 0
0 0 1 0 0
Выходные данные
3
#1574
Годовой отчет
  
Темы: [Потоки]
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В некоторой организации компьютеры пользователей объединены в локальную сеть. Также в этой организации есть несколько сетевых принтеров. В конце года пользователи начинают активно печатать различные годовые отчеты и делать это практически одновременно. Системный администратор знает схему сети и пропускную способность каждого кабеля. Пропускная способность измеряется в Мбит/с. Требуется по заданной схеме и пропускной способности определить максимальный поток данных, который может обработать данная локальная сеть. Считается, что во время годового отчета пользователи настолько заняты, что передают данные только на принтеры (не скачивают файлы из Интернета или с компьютеров других пользователей).

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

Сначала вводится число \(N\) (натуральное, не превышает 100) – количество объектов в сети. Затем следует \(N\) чисел, задающих вид каждого объекта: 1 – компьютер, 2 – принтер, 3 – хаб. Затем следует \(N\) строк по \(N\) чисел в каждой – пропускная способность проводов, соединяющих объекты сети. Число 0 означает отсутствие провода между какими-то объектами. Пропускная способность существующего провода – натуральное число, не превышает 1000. Гарантируется, что в сети есть хотя бы один компьютер и хотя бы один принтер.

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

Выведите единственное число – максимальный поток данных, который может передаваться по данной сети.

Примеры
Входные данные
3 1 2 3
0 0 10
0 0 20
10 20 0
Выходные данные
10
Входные данные
4 1 3 3 2
0  10 0 0
10 0  5 0
0  5  0 10
0  0 10 0
Выходные данные
5
#1625
Санная трасса
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Как известно, к северу от Москвы находится много горнолыжных трасс, расположенных на холмах Клинско-Дмитровской гряды. Один из курортов в связи с финансовым кризисом решил расширить спектр услуг, предлагая трассы для катания не только на лыжах и сноубордах, но и санные трассы.

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

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

На приведенном рисунке пунктирной линией показана наилучшая трасса для \(K\) = 4. Разница высот в ней составляет 68.

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

Сначала вводятся два натуральных числа \(C\) (1 ≤ \(C\) ≤ 2 000) — количество окружностей и \(K\) (1 ≤ \(K\) ≤ 2 000) – максимальное количество окружностей, которое может пересечь трасса.

Далее идут описания окружностей, каждое из которых состоит из четырех целых чисел: \(X\), \(Y\) (–2000 ≤ \(X\) ≤ 2000, –2000 ≤ \(Y\) ≤ 2000) – координаты центра окружности, \(R\) (1 ≤ \(R\) ≤ 2000) — радиус окружности и \(A\) (–1000 ≤ \(A\) ≤ 1000) — высота местности, касающейся внутреннего края окружности.

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

Выведите одно число — максимальный перепад высот на трассе.

Пример

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

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

10 4

38 61 2 73

69 34 3 15

61 59 4 30

40 60 5 66

58 44 6 30

71 34 6 -2

47 21 6 45

41 58 8 52

41 57 11 37

48 40 33 10

68
#1637
Домино
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Набор домино состоит из прямоугольных костяшек, каждая из которых разделена на две половинки линией, параллельной более короткой стороне. На каждой из половинок нарисованы точки, количество которых соответствует числу от 0 до \(M\) включительно. На костяшках полного набора домино обозначены все возможные различные пары чисел, например, если M равно 3, то полный набор содержит 10 костяшек: (0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3).

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

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

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

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

В первой строке входного файла содержится одно целое число \(M\) (0≤\(M\)≤100), которое соответствует максимально возможному количеству точек на половинке костяшки. Во второй строке записано одно целое число \(N\), равное количеству костяшек, удаленных из полного набора. Каждая \(і\)-я из последующих \(N\) строк содержит по два числа \(A_i\) и \(B_і\). Это количества точек на половинках \(i\)-й удалённой костяшки.

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

Единственная строка выходного файла должна содержать одно целое число \(L\) – минимальное количество цепочек.

Примеры
Входные данные
7
2
7 5
3 4
Выходные данные
2
Страница: << 25 26 27 28 29 30 31 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест