Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 151 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников
    Муниципальный этап(80 задач)
    Окружная олимпиада(18 задач)
    Региональный этап(109 задач)
    Заключительный этап(97 задач)
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
#1202
Операции
  
#1203
Кенгуренок Лео
  
#1204
Студенческие годы Пекки
  

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

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

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

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

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

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

В первой строке входного файла записано количество вагонов в составах 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
Выходные данные
4
#1206
Газон
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
0 0 5 4
4 0 3
Выходные данные
14
#1207
Трамвай
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

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

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

Каждая из следующих N строк содержит информацию об очередном пассажире в виде четырех целых чисел ai, bi, ci, di:, где первые два числа определяют вклад в параметр счастья, третье – номер остановки, на которой пассажир садится в трамвай, и последнее – номер остановки, на которой он выходит из трамвая (−106 ≤ ai, bi ≤ 106; 1 ≤ ci < di ≤ P).

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

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

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

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

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

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

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

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

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

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

Примеры
Входные данные
4 2 4
10 -10 2 3
-1 -3 1 4
6 -6 1 3
7 4 2 4
Выходные данные
28
Страница: << 5 6 7 8 9 10 11 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест