Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра
    Динамическое программирование: последовательности(46 задач)
    Динамическое программирование на таблицах(46 задач)
    Динамическое программирование по подстрокам(21 задач)
    Задача о рюкзаке(34 задач)
---> 45 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(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 задач)
Страница: << 3 4 5 6 7 8 9 Отображать по:
#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
#111882
K-й путь
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

У вас есть таблица c \(N\) строками и \(M\) столбцами. В каждой ячейке таблицы записана одна строчная буква английского алфавита. Рассмотрим все возможные пути от левого верхнего угла до правого нижнего угла, если вам разрешено идти только вправо и вниз. Конкатенация букв в порядке обхода составляют строку. Скажем, что эта строка  значение пути. Теперь рассмотрим все такие пути и отсортируем их значения в алфавитном порядке. Ваша задача найти значение \(K\)-го пути в этом отсортированном листе.

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

В первой строке задается два целых числа \(N\)  количество рядов и \(M\)  количество столбцов заданной таблицы (1 \(\le\) \(N\), \(M\) \(\le\) 30). Каждая из следующих \(N\) строк содержит ровно \(M\) строчных букв английского алфавита. Последняя строка входного файла содержит целое число \(K\) (1 \(\le\) \(K\) \(\le\) 1018). Гарантируется, что для \(K\) ответ всегда существует.

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

Первая и последняя строка выходного файла должна содержат одну строку - ответ к задаче.

Пояснения к примеру

abcdgk, abcdgk, abcdjk, abfdgk, abfdjk, abfijk, aefdgk, aefdjk, aefijk, aehijk

Примеры
Входные данные
3 4
abcd
efdg
hijk
4
Выходные данные
abfdgk
#112091
Шустрая черепашка
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Пафнутий и его друзья — большие любители разнообразных настольных игр. Особенно им нравятся игры, требующие как можно быстрее производить в уме непростые вычисления, поэтому абсолютным хитом их вечерних посиделок в аудиториях НУОП (Неизвестного университета олимпиадного программирования) стала игра «Шустрая черепашка». В комплект игры входят:

* Клетчатое поле из \(N\) рядов по \(M\) клеток. Каждая клетка поля либо свободна, либо блокирована для перемещения.

* Q игровых карточек. Каждая карточка содержит описание множества стартовых клеток A, множества дополнительно блокируемых клеток B и множества конечных клеток C. Множества A, B и C непусты, попарно не пересекаются и состоят из свободных клеток.

* Маленькая фишка в форме черепашки.

Правила игры очень просты. Игроки последовательно разыгрывают игровые карточки. Как только открывается очередная карточка, игрокам необходимо вычислить, сколько существует хороших троек клеток (\(a_i b_j c_k)\), где \(a_i \in A\), \(b_j \in B\), \(c_k \in C\). Тройка клеток называется хорошей, если можно провести черепашку из стартовой клетки ai в конечную клетку \(c_k\), не посещая при этом клетку \(b_j\). На перемещение черепашки наложено три условия:

1. Черепашка имеет право перемещаться только вниз и вправо в пределах поля.

2. Находиться на блокированных клетках запрещено

3. Клетка \(b_j\) также блокируется для перемещения

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

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

Первая строка входного файла содержит два целых числа \(N\) и \(M\) (1 ≤ \(N\), \(M\) ≤ 150) — количество строк и столбцов игрового поля.

Следующие \(N\) строк по \(M\) символов описывают игровое поле в порядке следования сверху вниз, слева направо. Символ ‘.’ соответствует свободной клетке, а ‘#’ — занятой. Строки нумеруются от 1 до \(N\), столбцы — от 1 до \(M\)

Следующая строка содержит целое число \(Q\) (1 ≤ \(Q\) ≤ 100 000) — количество игровых карточек.

Далее следуют \(Q\) блоков, описывающих карточки. Каждый блок состоит из трех строк, описывающих множества \(A\), \(B\) и \(C\) соответственно. Первое число описания определяет размер соответствующего множества, после чего перечисляются его клетки. Каждая клетка задается двумя числами — номером строки и номером столбца. Все клетки в описании различны. Смотрите комментарии к примеру для лучшего понимания формата входных данных.

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

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

В выходной файл выведите ровно \(Q\) чисел по одному на строке — правильные ответы на карточки в порядке их следования во входном файле.

Комментарии

В приведенном примере игровой комплект содержит две карточки

Во всех тройках первой карточки черепашка стартует в верхнем левом углу и финиширует в правом нижнем. Несложно видеть, что это возможно сделать, только если из трех элементов множества \(B\) блокируется первая клетка второй строки, то есть хорошей тройкой является \((1, 1) - (2, 1) - (5, 6)\).

На второй карточке хорошими являются тройки: \((1, 2) - (3, 1) - (5, 6)\), \((2, 1) - (3, 1) - (5, 6)\), \((2, 1) - (3, 3) - (5, 1)\).

Система оценивания

Тесты к этой задаче состоят из четырех групп

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

1. Тесты 2–18. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы.

2. Тесты 19–32. В тестах этой группы \(N\) ≤ 100, \(Q\)total ≤ 1 000 000. Эта группа оценивается в 30 баллов. Баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов из первой группы.

3. В тестах этой группы дополнительные ограничения отсутствуют, однако гарантируется, что \(N\) и \(Q\)total будут равномерно возрастать с номером теста. Эта группа оценивается в 40 баллов. Решение будет тестироваться на тестах этой группы offline, т. е. после окончания тура, причем только в случае прохождения всех тестов из первой и второй групп. Тесты в этой группе оцениваются независимо.

Примеры
Входные данные
5 6
..##..
....#.
.#.#..
.#...#
..#...
2
1 1 1
3 2 1 2 3 4 3
1 5 6
2 1 2 2 1
2 3 1 3 3
2 5 1 5 6
Выходные данные
1
3
#112559
Up and Down
  
ограничение по времени на тест
0.5 second;
ограничение по памяти на тест
64 megabytes

Дана последовательность попарно различных чисел A = [ A 1 , A 2 , ..., A N ] , требуется переставить числа так, чтобы было верно A 1 < A 2 < ... < A m > A m + 1 > ... > A N (где m лежит между 1 и N включительно) Переставлять можно только пары соседних чисел, требуется минимизировать количество обменов.

1 ≤ A i ≤ 10 9 1 ≤ N ≤ 1000 A i попарно различны.

В задаче есть две группы тестов:

1. 1 ≤ N ≤ 10 - оценивается в 35 баллов

2. 1 ≤ N ≤ 1000 - оценивается в 65 баллов

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

В первой строке число N . Вторая строка содержит N чисел: A 1 , ..., A N .

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

Выведите одно число - минимальное количество обменов

Примеры
Входные данные
3
1 2 3
Выходные данные
0
Входные данные
5
1 8 10 3 7
Выходные данные
1
#113539
Продажа картин
  
Источники: [ Личные олимпиады, COCI, COCI 2015-2016, Раунд 1, Продажа картин ]
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
32 megabytes

Лука - торговец картинами. У него есть N клиентов, каждому из которых он продает произведения искусства. Каждый клиент может купить либо цветные картины, либо черно-белые, но не те и другие вместе. При этом клиент под номером i готов купить не более a i цветных картин и не более b i черно-белых картин. При этом каждый клиент хочет купить хотя бы одну картину.

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

В силу нестабильной экономической ситуации в стране клиенты постоянно изменяют свои запросы, иными словами количество цветных и черно-белых картин, которые они готовы купить. Из-за этого Лука постоянно задается вопросом: "Сколько у меня есть вариантов, как продать клиентам картины, чтобы хотя бы C человек купили цветные картины?". Помогите Луке и защитите его от излишнего беспокойства.

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

Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 105, 1 ≤ C ≤ 20 ). Вторая строка содержит N целых чисел a i ( 1 ≤ a i ≤ 109 ). Третья строка содержит N целых чисел b i ( 1 ≤ b i ≤ 109 ). Четвертая строка содержит одно целое число Q ( 1 ≤ Q ≤ 105 ) - количество изменений требований клиентов. Каждая из следующих Q строк содержит три числа: номер клиента, меняющего требования P ( 1 ≤ P ≤ N ), новое максимальное количество цветных картин, которое он готов купить A p ( 1 ≤ A p ≤ 109 ) и новое максимальное количество черно-белых картин, которое он готов купить B p ( 1 ≤ B p ≤ 109 ).

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

Выведите Q строк, где в q -й строке записано единственное число - количество вариантов продать картины клиентам, чтобы хотя бы C человек купили цветные картины, по модулю 10007 после первых q изменений требований.

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

Тесты 4-6 — числа n, q не превосходят 1000. Группа тестов оценивается в 30 баллов.

Тесты 7-13 — Полные ограничения. Группа тестов оценивается в 70 баллов.

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