#1203

Кенгуренок Лео

Темы: [Обход в ширину] [Способы задания графа]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача B ]

#1204

Студенческие годы Пекки

Темы: [Сортировка записей] [Быстрая сортировка]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Окружная олимпиада, 2006, 2 тур, Задача C ]

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

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

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

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

Считается, что:

Все вагоны одинаковой длины.
Каждому типу товара соответствует определенное слово — его название (“Oil”, “Wood” и т. д.)
Количество разгружаемых вагонов первого состава с товарами любого типа совпадает с количеством загружаемых вагонов второго состава для товаров такого же типа.
Может быть несколько вагонов первого состава с одинаковым типом товара. При этом любой из них можно перегружать в соответствующие вагоны второго состава (но только полностью).
Если вагон первого состава с определенным типом товара встал рядом с вагоном второго состава, предназначенного для данного типа груза, то Пекка может как осуществить перегрузку, так и отказаться от нее
Изначально составы стоят таким образом, что первый вагон первого состава стоит рядом с первым вагоном второго состава, а последний вагон первого состава — рядом с последним вагоном второго состава.

Формат входного файла

В первой строке входного файла записано количество вагонов в составах N (1 ≤ N ≤ 100 000). Далее следуют N строк, описывающих вагоны первого состава в порядке, в котором они соединены в состав. В каждой строке записано название груза, находящегося в соответствующем вагоне. Название содержит от одной до десяти больших и маленьких букв латинского алфавита. Названия считаются одинаковыми, если они совпадают с учетом регистра (например, “Oil” и “oil” — разные грузы). Затем записаны N строк, аналогичным образом описывающих вагоны второго состава.

Формат выходного файла

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

Группы тестов:

Группа 0 : Тест из условия (тест 1). 0 баллов.
Группа 1 : N ≤ 10 (тесты 2-6). 30 баллов.
Группа 2 : Ответ на задачу не превосходит 100 (тесты 7-11). 30 баллов.
Группа 3 : Дополнительных ограничений нет (тесты 12-50). 40 баллов.

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

Примеры

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

3
Oil
Wood
Grain
Wood
Grain
Oil

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

#1205

Черно-белая графика

Темы: [Двумерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 1 день, Задача A ]

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной w и высотой h, разбитых на w×h единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

Во многих областях очень часто возникает задача комбинации изображений. Одним из простейших методов комбинации, который используется при работе с черно-белыми изображениями, является попиксельное применение некоторой логической операции. Это означает, что значение пиксела результата получается применением этой логической операции к соответствующим пикселам аргументов. Логическая операция от двух аргументов обычно задается таблицей истинности, которая содержит значения операции для всех возможных комбинаций аргументов. Например, для операции «исключающее ИЛИ» эта таблица выглядит так.

Первый аргумент	Второй аргумент	Результат
0	0	0
0	1	1
1	0	1
1	1	0

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

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

Первая строка входного файла содержит два целых числа w и h (1 ≤ w, h ≤ 100). Последующие h строк описывают первое изображение и каждая из этих строк содержит w символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка входного файла содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента – нули, второе – результат в случае, если первый аргумент – ноль, второй – единица, третье – результат в случае, если первый аргумент – единица, второй – ноль, а четвертый – в случае, если оба аргумента – единицы.

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

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

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-26 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп. При выставлении баллов за отдельные тесты каждый тест (кроме тестов из условия) оценивается в 4 балла.

Примеры

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

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

11110
11100
11110

#1206

Газон

Темы: [Пересечение множеств] [Задачи на моделирование] [Двумерные массивы]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 1 день, Задача B ]

Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы.

В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x₁, y₁) и (x₂, y₂). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены.

Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x₃, y₃) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x₃, y₃) не превышало r.

Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?

Требуется написать программу, которая позволит дать ответ на вопрос Ивана.

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

В первой строке входного файла содержатся четыре целых числа x₁, y₁, x₂, y₂ (−100 000 ≤ x₁ < x₂≤ 100 000; −100 000 ≤ y₁ < y₂≤ 100 000).

Во второй строке входного файла содержатся три целых числа x₃, y₃, r (−100 000 ≤ x₃, y₃ ≤ 100 000; 1 ≤ r≤ 100 000)

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

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

Иллюстрация к примеру

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-21 — дополнительных ограничений нет. Группа тестов оценивается в 100 баллов.

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.

Примеры

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

0 0 5 4
4 0 3

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

#1207

Трамвай

Темы: [Двоичное дерево поиска] [Сканирующая прямая] [Задачи на моделирование]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, 2009, 1 день, Задача C ]

С окраины в центр города каждое утро по одному маршруту едут в трамвае N человек. За долгое время поездок они достаточно хорошо узнали друг друга. Чтобы никому не было обидно, они захотели решить, кто из них и между какими остановками маршрута должен сидеть, а кто должен стоять. Все остановки пронумерованы от 1 до P.

Один из пассажиров оказался знатоком теории математического моделирования. Он предложил рассмотреть значение суммарного удовлетворения пассажиров. Для каждого i-го пассажира он оценил две величины — a_i и b_i. Если в течение одного переезда между остановками пассажир сидит, то к суммарному удовлетворению прибавляется a_i, если же он стоит, то прибавляется b_i.

Всего в трамвае M сидячих мест. Вставать и садиться пассажиры могут мгновенно на любой остановке. Кроме того, некоторые пассажиры предпочитают ехать стоя, даже если в трамвае есть свободные места (для них a_i < b_i).

Требуется написать программу, которая вычисляет значение максимально достижимого суммарного удовлетворения, если для каждого i-го пассажира известны величины a_i и b_i, а также номера остановок, на которых он садится и выходит из трамвая.

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

Первая строка входного файла содержит разделенные пробелом три целых числа N, M и P — число пассажиров, число сидячих мест и число остановок на маршруте соответственно (1 ≤ N, M, P ≤ 100 000; 2 ≤ P).

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел a_i, b_i, c_i, d_i:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−10⁶ ≤ a_i, b_i ≤ 10⁶; 1 ≤ c_i < d_i ≤ P).

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

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

Комментарий к примеру тестов

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

Разбалловка для личной олимпиады

Тест 1 — из условия. Оценивается в 0 баллов.

Тесты 2-31 — числа M, N, P не превосходят 100. Группа тестов оценивается в 60 баллов.

Тесты 32-41 — число P не превосходит 100. Группа тестов оценивается в 20 баллов (вместе с предыдущей группой — 80 баллов).

Тесты 42-51 — дополнительных ограничений нет. Группа тестов оценивается в 20 баллов (вместе с предыдущими группами — 100 баллов).

Баллы начисляются за прохождение всех тестов группы и всех тестов предыдущих групп.

Примеры

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

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