Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(10 задач)
    Динамическое программирование: один параметр(49 задач)
    Динамическое программирование: два параметра(183 задач)
    Динамическое программирование в играх(9 задач)
    Динамическое программирование на графах(25 задач)
    Динамическое программирование по профилю(20 задач)
    Динамика по подмножествам(13 задач)
---> 85 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
#111518
Расписание маршруток
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

В автопарке компании есть \(n\) маршруток, \(i\)-ая маршрутка номинально вмещает \(a_i\) пассажиров. По договору с департаментом транспорта города компания обязана обслуживать \(m\) маршрутов. Накопленная статистика говорит, что оптимальнее всего, если \(j\)-ый маршрут обслуживает такси номинальной вместимостью \(b_j\) пассажиров. Каждая маршрутка приписывается не более чем к одному маршруту, каждому маршруту приписывается не более одной маршрутки.

Разумеется, каждый уважающий себя диспетчер при назначении маршруток на маршруты старается минимизировать потери, которые бывают следующими:

  • если \(i\)-ая маршрутка обслуживает \(j\)-ый маршрут, то компания теряет \(|a_i-b_j|\) у.е., так как чем меньше заполнено такси, тем больше не используются его возможности, а чем больше переполнено такси, тем чаще его приходится ремонтировать;
  • от каждой простаивающей маршрутки, то есть такой, которой не назначен ни один маршрут, компания несет убыток \(p\) у.е.;
  • компании приходится платить штраф \(q\) у.е. департаменту транспорта за каждый не обслуживаемый маршрут.

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

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

В первой строке входного файла находятся четыре целых числа — \(n\), \(m\), \(p\), \(q\) (\(1\leq n,m \leq 10^3\), \(0 \leq p,q \leq 10^4\)).

Во второй строке через пробел указаны целые числа \(a_1\), ..., \(a_n\) (\(1\leq a_i \leq 10^4\)).

В третьей строке через пробел указаны целые числа \(b_1\), ..., \(b_m\) (\(1\leq b_j \leq 10^4\)).

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

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

Примечание

В примере 1 первая маршрутка назначена на второй маршрут с потерями \(|22-20|=2\) у.е., вторая маршрутка назначена на первый маршрут с потерями \(|12-11|=1\) у.е.. Итого: потери 3 у.е..

В примере 2 одна из маршруток назначается на единственный маршрут с нулевым штрафом, а вторая вынуждена простаивать. Итого: потери 100 у.е.

Примеры
Входные данные
2 2 100 100
22 12
11 20
Выходные данные
3
Входные данные
2 1 100 500
13 13
13
Выходные данные
100
#111523
Руммикуб
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

В игре «Руммикуб» используются фишки, которые бывают четырех различных цветов, и на каждой из которых написано одно натуральное число от 1 до 13. Для каждого числа и для каждого цвета в наборе фишек есть ровно две соответствующие фишки, т.е. всего в наборе \(8\cdot 13 = 104\) фишки.

Число, написанное на фишке, будем называть ее достоинством; цвета будем обозначать латинскими буквами A, B, C и D, и каждую фишку будем обозначать, записывая сначала ее цвет, а потом — ее достоинство. Например, C12 — это фишка цвета C и достоинством 12.

Комбинацией в игре называется набор из как минимум трех фишек, удовлетворяющий любому из следующих условий:

  • Достоинства всех фишек одинаковы, а цвета — попарно различны; или
  • Цвета всех фишек одинаковы, а достоинства являются последовательными натуральными числами.

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

  • C12, A12, B12;
  • C12, A12, B12, D12;
  • C5, C6, C7;
  • A3, A4, A5, A6, A7.

При этом следующие наборы не являются комбинациями:

  • A3, B3 (слишком мало фишек);
  • A3, B3, C3, D3, B3 (цвета повторяются);
  • A3, A4, A4, A5, A6 (достоинства повторяются);
  • A3, A4, A6, A7, A8 (число 5 пропущено).

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

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

В первой строке входного файла находится одно натуральное число \(K\) — количество фишек. Далее следуют \(K\) строк, на каждой из которых находится описание одной фишки — цвет и достоинство.

Гарантируется, что эти фишки являются корректным подмножеством фишек из некоторого комплекта для игры в руммикуб; т.е. гарантируется, что каждый цвет — это латинская заглавная буква от A до D, что каждое достоинство — это натуральное число, не превосходящее 13, и что для для каждой пары (цвет, достоинство) в наборе есть не более двух таких фишек.

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

Если данный набор фишек можно разбить на комбинации так, чтобы каждая фишка входила ровно в одну комбинацию, то в первую строку выходного файла выведите одно число \(M\) — количество комбинаций в вашем решении. Далее выведите \(M\) строк, в \(i\)-ой из которых выведите \(i\)-ую комбинацию. А именно, сначала выведите количество фишек в комбинации, а потом сами фишки, разделенные между собой и отделенные от количества фишек пробелами. В пределах каждой комбинации фишки можете выводить в произвольном порядке; комбинации также можете выводить в произвольном порядке.

Если есть несколько решений, выведите любое. Если решений нет, то выведите в выходной файл одно число -1.

Примеры
Входные данные
3
A2
A3
A5
Выходные данные
-1
Входные данные
3
A2
A4
A3
Выходные данные
1
3 A2 A4 A3
Входные данные
7
A12
A13
A13
B13
C13
D13
A11
Выходные данные
2
3 A11 A12 A13
4 A13 B13 C13 D13
#111636
Древние династии
  

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

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

Первая строка выходного файла должна содержать числа P и Q, где P — номер учёного, версии которого соответствует распределение с наименьшим показателем сомнительности, а Q — показатель сомнительности этого распределения.

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

  3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

  4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

  5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

  6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры
Входные данные
3
1 2 3
1
1 1 1 1
Выходные данные
1 1
211
Входные данные
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Выходные данные
0
Входные данные
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Выходные данные
2 0
21212
#111877
Энергичная черепаха
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Дана сетка с \(N\) + 1 рядами и \(M\) + 1 столбцами. Черепаха находится на клетке (0, 0) и хочет попасть в клетку (\(N\), \(M\)). Черепаха может идти только вверх или вправо. На сетке в K клетках находятся ловушки. Если черепаха пойдет в одну из этих клеток, то она перевернется. У черепашки есть силы для того, чтобы встать не более чем \(T\) раз. Посчитайте, сколькими различными путями черепаха может попасть в клетку (\(N\), \(M\)). Так как это число может быть очень большим, выведите остаток от его деления на \(Z\).

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

В первой строке входного файла задается 5 целых чисел: \(N\), \(M\), \(K\), \(T\) и \(Z\) (\(1\) \(\le\) \(N\),\(M\) \(\le\) 300000, 0 \(\le\) \(K\), \(T\) \(\le\) 20, 1 \(\le\) \(Z\) \(\le\) \(10^9\)). В каждой из следующих \(K\) строк расположены координаты соответствующей клетки с ловушкой \(X\), \(Y\) (0 \(\le\) \(X\) \(\le\) \(N\), 0 \(\le\) \(Y\) \(\le\) \(M\)). Гарантируется, что все клетки с ловушками различные и в клетках (0, 0) и (\(N\), \(M\)) ловушек нет.

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

Выведите требуемое число.

Примеры
Входные данные
1 1 1 0 100
0 1
Выходные данные
1
Входные данные
2 2 0 0 10
Выходные данные
6
#111880
Скайлайн
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером \(i\) должно быть ровно \(h[i]\) этажей.

У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.

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

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

Первая строка содержит одно целое число \(N\) (1 \(\le\) \(N\) \(\le\) 300). Вторая строка содержит \(N\) целых чисел h[1], h[2] ..., h[N], 1 \(\le\) h[i] \(\le\) 200.

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

В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.

Примеры
Входные данные
3
2 2 2
Выходные данные
14
Входные данные
4
1 3 1 1
Выходные данные
15
Страница: << 11 12 13 14 15 16 17 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест