Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра
    Динамическое программирование: последовательности(46 задач)
    Динамическое программирование на таблицах(46 задач)
    Динамическое программирование по подстрокам(21 задач)
    Задача о рюкзаке(34 задач)
---> 7 задач <---
Источники --> Личные олимпиады --> Всероссийская олимпиада школьников --> Региональный этап
    2009(8 задач)
    2010(8 задач)
    2011(8 задач)
    2012(8 задач)
    2013(8 задач)
    2014(8 задач)
    2015(8 задач)
    2016(8 задач)
    2017(8 задач)
    Московская областная олимпиада(13 задач)
    Кировская открытая областная олимпиада(21 задач)
    Санкт-Петербург(3 задач)
Страница: 1 2 >> Отображать по:
#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
#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
#1226
Игра с шашками
  

Поле для игры с шашками – длинная горизонтальная полоска, размеченная на клетки. Клетки пронумерованы от 1 до N (2 < N < 10000). На поле стоят две шашки. Позиция каждой из шашек определяется номером клетки, в которой она стоит.

Играют двое. Каждый игрок при своем ходе должен переместить любую шашку на одну, две или три клетки в сторону клетки 1 (сделать 1, 2 или 3 шага). Перепрыгивать через стоящую впереди шашку нельзя, но можно сдваивать шашки. На сдваивание шашек   тратится два шага из трех доступных игроку (то есть сдваивать можно либо шашки, стоящие  вплотную друг к другу, либо шашки, между которыми есть только одна пустая клетка). Если произошло сдваивание – ход передается другому игроку, который делает ход  одной шашкой , оставив другую на месте.

Выигрывает тот, кто сдвоит шашку на клетке с номером 1.

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

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

В первой строке содержится число K (0 < K < 10) – количество начальных позиций. В последующих K строках содержится по два целых числа от 3 до 10000, разделенных пробелом – номера начальных позиций шашек на игровом поле.

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

Выводится K строчек – ответ на каждую начальную позицию.

Если при заданной начальной позиции шашек в игре не достигается выигрыш (при правильной игре противника) выводится слово NO.

Если выигрыш достижим, то выводится первый ход начинающего игру, который приводит к его выигрышу независимо от того, как играет соперник. Ход описывается парой чисел  i, j через пробел, означающих, что выигрышный ход игрока – это перемещение шашки из клетки с номером i в клетку с номером  j. Например, «4 3» означает, что игрок двигает шашку, стоящую в клетке 4, на одну клетку в сторону клетки 1.

Примечание
Ответ на тест из примера:
NO
11 10
12 11
NO
15 12
12 10
Примеры
Входные данные
6
3 10
3 11
4 12
5 8
9 15
3 12
Выходные данные
YES
NO
#1924
Булева функция
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция \(f\) сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции \(f\).

Если задана булева функция \(f\) и набор из \(N\) булевых значений \(a_1,a_2,\ldots,a_N\), то результат цепного вычисления этой булевой функции определяется следующим образом:

* если \(N=1\), то он равен \(a_1\);

* если \(N>1\), то он равен результату цепного вычисления булевой функции \(f\) для набора из \((N-1)\) булевого значения \(f(a_1,a_2),a_3,\ldots,a_N\), который получается путём замены первых двух булевых значений в наборе из \(N\) булевых значений на единственное булево значение — результат вычисления функции \(f\) от \(a_1\) и \(a_2\).

Например, если изначально задано три булевых значения: \(a_1=0\), \(a_2=1\), \(a_3=0\), а функция \(f\) — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию \(f\) и попросила одного из учеников выбрать такие \(N\) булевых значений \(a_i\), чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно бо́льшим.

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

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

Первая строка входного файла содержит одно натуральное число \(N\) (\(2\le N\le100\,000\)).

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

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

В выходной файл необходимо вывести строку из \(N\) символов, определяющих искомый набор булевых \(a_i\) с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу «No solution».

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

В первом примере процесс вычисления цепного значения булевой функции \(f\) происходит следующим образом: \(1011\to111\to01\to1\)

Во втором примере вычисление цепного значения булевой функции \(f\) происходит следующим образом: \(11111\to0111\to111\to01\to1\)

В третьем примере получить цепное значение булевой функции \(f\), равное 1, невозможно.

Примеры
Входные данные
4
0110
Выходные данные
1011
Входные данные
5
0100
Выходные данные
11111
Входные данные
6
0000
Выходные данные
No solution
#3143
Перевес багажа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

У Пети в чемодане лежат N предметов, каждый предмет имеет свой вес Wi килограмм и ценность Ai рублей, причем оказалось так, что для любого предмета выполняется следующее неравенство:

W1 + W2 + … + Wi-1 ≤ Wi

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

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

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

В первой строке задаётся количество предметов в багаже у Пети N (1 ≤ N ≤ 50) и какой у Пети перевес чемодана в килограммах M (1 ≤ M ≤ 1018). Во второй строке задаются N целых неотрицательных чисел – вес всех вещей Wi, сумма чисел не превышает 1018. В третьей строке заданы N целых неотрицательных чисел – ценность всех вещей Ai , все числа не превышают 109.

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

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

Ввод
Вывод
4 15
5 10 15 30
1 5 3 6
3
3 2
1 2 4
7 6 5
5
Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест