Темы --> Информатика --> Алгоритмы --> Динамическое программирование
    Рекуррентные последовательности(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 задач)
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
#1150
Таблица
  

Рассмотрим прямоугольную таблицу размером n m. Занумеруем строки таблицы числами от 1 до n, а столбцы – числами от 1 до m. Будем такую таблицу последовательно заполнять числами следующим образом.

Обозначим через aij число, стоящее на пересечении i-ой строки и j-ого столбца. Первая строка таблицы заполняется заданными числами – a11, a12, …, a1m. Затем заполняются строки с номерами от 2 до n. Число aij вычисляется как сумма всех чисел таблицы, находящихся в «треугольнике» над элементом aij. Все вычисления при этом выполняются по модулю r.






























 

 

ai,j

















Более точно, значение aij вычисляется по следующей формуле:

 

Например, если таблица состоит из трех строк и четырех столбцов, и первая строка состоит из чисел 2,3,4,5, а r = 40 то для этих исходных данных таблица будет выглядеть следующим образом (взятие по модулю показано только там, где оно приводит к изменению числа):

2

3

4

5

5 = 2 + 3

9 = 2 + 3 + 4

12 = 3 + 4 + 5

9 = 4 + 5

23 = 2 + 3 + 4 + 5 + 9

0 = (2 + 3 + 4 + 5 + 5 + 9 + 12) mod 40 = 40 mod 40

4 = (2 + 3 + 4 + 5 + 9 + 12 + 9) mod 40 = 44 mod 40

33 = 3 + 4 + 5 + 12 + 9

Требуется написать программу, которая по заданной первой строке таблицы (a11, a12, …, a1m), вычисляет последнюю строку, как описано выше.

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

Первая строка входного файла содержит числа n, m и r (2 ≤ n, m ≤ 2000, 2 ≤ r ≤ 109) – число строк и столбцов таблицы соответственно, а так же число, по модулю которого надо посчитать ответ. Следующая строка содержит m целых чисел – первую строку таблицы: a11, a12, …, a1m. Все a1i неотрицательны и не превосходят 109.

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

В первой строке выходного файла необходимо вывести m чисел – последнюю строку таблицы: an1, an2, …, anm.

Примеры
Входные данные
2 3 10
1 2 3
Выходные данные
3 6 5
Входные данные
3 3 10
1 1 1
Выходные данные
8 0 8
Входные данные
3 4 40
2 3 4 5
Выходные данные
23 0 4 33
#1211
Числа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
Задана последовательность чисел. Требуется подсчитать количество вариантов разбиения этой последовательности на неотрицательные числа, не превосходящие заданного числа.

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

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

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

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

Первая строка входного файла содержит три целых числа — n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 108, 1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

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

В выходной файл выведите последние k цифр искомого количества последовательностей (без ведущих нулей).

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

Тесты 1-8 — \(n \le 7\) Оценивается в 30 баллов.

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

Примеры
Входные данные
3 11 2
111
Выходные данные
3
Входные данные
19 9 1
0123456789876543210
Выходные данные
1
Входные данные
1 8 3
9
Выходные данные
0
#1212
Перестановки
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
K-перестановкой чисел называется такая перестановка, в которой НОД соседних чисел не меньше K. Заданы числа из которых необходимо построить N-ую перестановку в лексикографическом порядке.

Задано множество из n различных натуральных чисел. Перестановку элементов этого множества назовем k-перестановкой, если для любых двух соседних элементов этой перестановки их наибольший общий делитель не менее k. Например, если задано множество элементов S = {6, 3, 9, 8}, то перестановка {8, 6, 3, 9} является 2-перестановкой, а перестановка {6, 8, 3, 9} – нет.

Перестановка {p1, p2, …, pn} будет лексикографически меньше перестановки {q1, q2, …, qn}, если существует такое натуральное число i (1 ≤ i ≤ n), для которого pj = qj при j < i и pi < qi.

В качестве примера упорядочим все k-перестановки заданного выше множества в лексикографическом порядке. Например, существует ровно четыре 2-перестановки множества S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3} и {9, 3, 6, 8}. Соответственно, первой 2-перестановкой в лексикографическом порядке является множество {3, 9, 6, 8}, а четвертой – множество {9, 3, 6, 8}.

Требуется написать программу, позволяющую найти m-ую k-перестановку в этом порядке.

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

Входной файл в первой строке содержит три натуральных числа – n (1 ≤ n ≤ 16), m и k (1 ≤ m, k ≤ 109). Вторая строка содержит n различных натуральных чисел, не превосходящих 109. Все числа в строках разделены пробелом.

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

В выходной файл необходимо вывести m-ую k-перестановку заданного множества или –1, если такой нет.

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

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

Тесты 4-17 — \(n\le 4\). Группа тестов оценивается в 28 баллов.

Тесты 18-28 — \(n\le 10\). Группа тестов оценивается в 22 балла (вместе с предыдущей группой — 50 баллов).

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

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

Примеры
Входные данные
4 1 2
6 8 3 9
Выходные данные
3 9 6 8
Входные данные
4 4 2
6 8 3 9
Выходные данные
9 3 6 8
Входные данные
4 5 2
6 8 3 9
Выходные данные
-1
#1216
Школа танцев
  

В школу бальных танцев профессора Падеграса записались n учеников — мальчиков и девочек. Профессор построил их в один ряд, и хочет отобрать из них для первого занятия группу стоящих подряд учеников, в которой количество мальчиков и девочек одинаково. Сколько вариантов выбора есть у профессора?

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

В первой строке задано число n (1 ≤ n ≤ 106). Во второй строке задается описание построенного ряда из мальчиков и девочек — строка из n символов a и b (символ a соответствует девочке, а символ b — мальчику).

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

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

Система оценки

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

  1. Тест 1. Тест из условия, оценивается в 0 баллов.
  2. Тесты 2–8. \(N \le 101\), оцениваются в 30 баллов.
  3. Тесты 9–14. \(N \le 6\,000\), оцениваются в 30 баллов.
  4. Тесты 15–20. Дополнительных ограничений нет, оцениваются в 40 баллов.

Примеры
Входные данные
8
aabbaabb
Выходные данные
10
#1225
Склад
  

На роботизированном складе имеется N отсеков, в которые робот может размещать грузы. Отсек с номером i имеет вместимость ci. Груз с номером i имеет размер si, поступает на склад в момент времени ai и забирается со склада в момент времени di.

Когда груз с номером i поступает на склад, робот сначала пытается найти отсек, в котором достаточно свободного места для размещения этого груза. Свободное место в пустом отсеке совпадает с его вместимостью. Если в отсеке с вместимостью c находится несколько грузов с суммарным размером d, то свободное место в этом отсеке равно c – d.

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

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

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

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

Первая строка содержит два целых числа: N — количество отсеков, и M — количество грузов (1 ≤ N ≤ 10, 1 ≤ M ≤100). Вторая строка содержит N целых чисел ci, определяющих вместимости отсеков (1 ≤ ci ≤ 109). Последующие M строк описывают грузы: каждый груз описывается тремя целыми числами: своим размером si, временем поступления на склад ai и временем, когда его забирают со склада di (1 ≤ si ≤ 109, 1 ≤ ai < di ≤ 1000, все времена во входном файле различны, грузы упорядочены по возрастанию времени поступления на склад). Все числа в строках разделены пробелом.

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

Выведите последовательность действий робота в том порядке, в котором они выполняются. Следуйте формату, приведенному в примере.

Возможны следующие сообщения:

put cargo X to cell Y — положить груз с номером X в отсек с номером Y;

move cargo X from cell Y to cell Z — переложить груз с номером X из отсека с номером Y в отсек с номером Z;

take cargo X from cell Y — достать груз с номером X из отсека с номером Y.

cargo X cannot be stored — если груз с номером X разместить невозможно.

Примеры
Входные данные
1 2
3
2 1 2
4 3 4
Выходные данные
put cargo 1 to cell 1
take cargo 1 from cell 1
cargo 2 cannot be stored
Страница: << 4 5 6 7 8 9 10 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест