Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Потоки
    Алгоритм Форда-Фалкерсона(4 задач)
---> 2 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 Отображать по:
#1650
Живопись
  
Темы: [Потоки]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Формат входных данных

Первая строка входного файла содержит пять натуральных чисел N, M, w, b, g. 1≤N, M≤70 – высота и ширина картины, 1≤w,b,g≤1000 – цена рисования одного белого единичного квадрата, черного единичного квадрата и серой линии единичной длины, соответственно. Далее следует N строк, каждая из которых состоит из M литер. Литера B соответствует черному квадрату, а W – белому.

Формат выходных данных

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

Примеры
Входные данные
3 2 10 12 1
BW
WB
BW
Выходные данные
7
#1932
Дракончики
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Петя занимается разведением дракончиков. У него есть \(M\) зеленых дракончиков и \(K\) желтых. У Пети есть \(N\) двухместных аквариумов для дракончиков и \(M+K–2N\) одноместных.

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

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

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

Вводятся числа \(M, K, N\) (\(M ≥ 1, K ≥ 1, N ≥ 0, N ≤ M, N ≤ K, M + K ≤ 200\)). Будем считать, что зеленые дракончики пронумерованы числами от \(1\) до \(M\), а желтые – числами от \(M+1\) до \(M+K\).

Далее идет число \(T\) (\(0 ≤ T ≤ MK\)) – количество пар дракончиков, про которых известно, что они не переносят друг друга. Далее идет \(T\) пар чисел, описывающих номера не переносящих друг друга дракончиков (первое число каждой пары описывает зеленого дракончика, второе – желтого). Далее идет число \(Q\) (\(0 ≤ Q ≤ M + K\))– количество дракончиков, не переносящих одиночества. Далее идет \(Q\) чисел, задающих номера этих драконов.

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

В случае если разместить дракончиков по аквариумам требуемым образом нельзя, выведите единственное слово NO. В противном случае первая строка должна содержать YES. В следующие \(N\) строк выведите \(N\) пар чисел, задающих номера дракончиков, которых нужно поместить в двухместные аквариумы.

Примеры
Входные данные
2 1 1
1
1 3
1
1
Выходные данные
NO
Входные данные
2 2 1
1
1 3
1
2
Выходные данные
YES
2 4
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест