Темы --> Информатика --> Алгоритмы --> Динамическое программирование --> Динамическое программирование: два параметра
    Динамическое программирование: последовательности(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 >> Отображать по:
#1982
Петино путешествие
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Завтра Петя уезжает в кругосветное путешествие, в процессе которого собирается посетить N разных городов. Вспомнив о старинной традиции бросать монетки в фонтаны для того, чтобы когда-нибудь вернуться в это место, он решил запастись монетами заранее. Поскольку это всего лишь традиция, подумал Петя, то с него хватит оставить в каждом городе по одной копеечной монете – зачем тратиться зря?

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

С этими мыслями Петя решил прогуляться до продуктового магазина – купить в дорогу немного еды. Из всего ассортимента ему подходило M видов товара (количество товаров каждого вида неограниченно), стоимость i-го равна ai рублей bi копеек. И тут его осенило. Если покупать товары в правильной последовательности, то он довольно быстро сможет скопить так нужные ему N копеечных монет!

Процесс покупки в магазине устроен следующим образом. Петя может заказать любой набор из подходящих ему товаров (каждого товара Петя может взять сколько угодно единиц). После чего он платит за них и получает сдачу минимальным числом купюр и монет (любых монет и купюр в кассе также с избытком). Это означает, например, что если ему должны сдать 11 рублей и 98 копеек сдачи, то он получит купюру в 10 рублей, монеты в 1 рубль, 50 копеек, 4 монеты в 10 копеек, одну монету в 5 копеек и три копеечных монеты. При этом он волен вносить любую сумму (лишь бы она была не меньше требуемой для оплаты) и платить любым набором купюр и монет, имеющихся у него в распоряжении.

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

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

Комментарий для нероссийских участников олимпиады.

В России используются монеты и купюры достоинством 1, 5, 10, 50 копеек и 1, 2, 5, 10, 50, 100, 500, 1000 и 5000 рублей. 1 рубль равен 100 копейкам.

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

Сначала вводятся целые числа N и M (0 ≤ N ≤ 108, 0 ≤ M ≤ 100) — количество городов, которые собирается посетить Петя, и количество подходящих ему видов товара. Далее идут M пар чисел ai, bi, обозначающих стоимость товара соответствующего типа (0 ≤ ai ≤ 100, 0 ≤ bi ≤ 99). Стоимость товара всегда больше нуля.

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

Если требуемое количество копеечных монет получить невозможно, выведите –1. Иначе выведите минимальную сумму, которую должен потратить Петя на покупку товаров, чтобы получить N однокопеечных монет.  Сумма должна быть выведена как два целых числа, задающих рубли и копейки (второе число обязано быть от 0 до 99).

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

Примеры
Входные данные
3 1
0 2
Выходные данные
0 2
Входные данные
4 2
1 2
0 4
Выходные данные
0 16
Входные данные
1 3
0 1
0 4
0 6
Выходные данные
0 1
#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
#3296
Поход (6-9)
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Группа школьников решила сходить в поход вдоль Москвы-реки. У Москвы-реки существует множество притоков, которые могут впадать в нее как с правого, так и с левого берега.

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

Школьники заранее изучили карту и записали, в какой последовательности в Москву-реку впадают притоки на всем их маршруте.

Помогите школьникам по данному описанию притоков определить минимальное количество переправ, которое им придется совершить во время похода.

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

Единственная строка содержит описание Москвы-реки между начальной и конечной точкой похода. Длина строки не превосходит \(200\) символов.

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

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

Выведите одно целое число - минимальное количество переправ.

Примечание

Рисунок к приведенному выше примеру.

Примеры
Входные данные
LLBLRRBRL
Выходные данные
5
#3789
Сохранить энергию
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Одна Фруктовая Компания, производящая электронику, решила озаботиться длительностью работы своих смартфонов от аккумулятора.

Выяснилось, что процессор, который они закупают у азиатского поставщика, поддерживает m различных режимов работы, при этом каждая из k операций языка программирования (который Фруктовая Компания использует для написания всех своих программ) может быть выполнена в каждом из режимов. Одновременно процессор может работать только в одном режиме, но перед выполнением каждой из операций можно один раз переключиться в любой другой режим работы.

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

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

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

Первая строка содержит три целых числа: число k (1 ≤ k ≤ 100) — количество операций в языке программирования, число m (1 ≤ m ≤ 100) — количество режимов работы, которое поддерживает процессор, и число n (1 ≤ n ≤ 10000) — количество операций в исследуемой программе.

Следующие k строчек содержат по m целых неотрицательных чисел, не превышающих 100. j-е число в i-ой строчке обозначает, сколько энергии тратится на выполнение i-ой операции в j-ом режиме команд.

Далее следует m строчек, содержащих по m целых неотрицательных чисел, не превышающих 100. j-ое число в i-ой строчке обозначает, сколько единиц энергии тратится на переключение процессора с режима i на режим j. Гарантируется, что в i-ой строке i-ое число равно 0.

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

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

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

Подзадачи и система оценки

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

  • Тесты из условия, оцениваются в ноль баллов.
  • В тестах этой группы \(n\), \(m\), \(k\) не превосходят 10. Эта группа оценивается в 50 баллов, баллы ставятся только при прохождении всех тестов группы.
  • В тестах этой группы \(m\) не превосходит 10. Эта группа оценивается в 30 баллов, баллы ставятся только при прохождении всех тестов группы и предыдущих групп.
  • В тестах этой группы дополнительные ограничения отсутствуют. Группа оценивается в 20 баллов, баллы ставятся только при прохождении всех тестов этой и предыдущих групп.

Примеры
Входные данные
2 1 4
60
93
0
1 2 1 1
Выходные данные
273
Входные данные
2 2 4
1 10
10 1
0 1
2 0
1 1 2 2
Выходные данные
5
#3892
Шифр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Жюри N-ской олимпиады по информатике решило зашифровать свои материалы подстановочным шифром. Для шифрования таким шифром задаётся взаимно-однозначное соответствие между буквами алфавита в открытом (т.е. до шифрования) тексте и буквами алфавита в закрытом (т.е. после шифрования) тексте, это соответствие и является ключом шифра. В процессе шифрования каждая буква в открытом тексте заменяется на соответствующую ей букву в закрытом тексте, порядок букв в слове при этом не меняется.

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

Чтобы разрешить свои проблемы, они обратились к вам. Для облегчения вашей задачи они выписали на бумажку все возможные варианты зашифрования букв, которые они могли применять, в виде набора пар «открытая буква» — «зашифрованная буква». Также вам известны все пары букв N-ского алфавита, которые могут следовать одна за другой в открытом тексте. Ваша задача состоит в том, чтобы по заданному зашифрованному слову сказать, соответствует ли ему хоть одно расшифрованное слово, единственен ли вариант расшифровки, и привести пример вариантов расшифровки слова. Слово \(\mathcal{A}\) считается возможной расшифровкой слова \(\mathcal{B}\), если, во-первых, его можно «зашифровать» (заменяя каждую букву на одну из соответствующих ей «зашифрованных» букв), получив слово \(\mathcal{B}\), и, во-вторых, каждая пара букв слова \(\mathcal{A}\), стоящих рядом, является допустимой для N-ского языка.

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

N-ский язык пользуется латинским алфавитом из 26 букв, регистр букв N-ское жюри не интересует, поэтому везде в открытом тексте используются большие буквы, а в закрытом — маленькие.

На первой строке входного файла находится одно целое число \(M\) (\(0 \leq M \leq 676\)) — число пар открытых — «зашифрованных» букв, указанных на бумажке, переданной N-ским жюри. Далее следуют \(M\) строк, на каждой находятся два символа — сначала открытая буква, потом вариант её «зашифрования». Пары не повторяются.

На следующей строке находится одно целое число \(K\) (\(0\leq K\leq 676\)) — число пар открытых букв, которые могут идти одна за другой. Далее следуют \(K\) строк, на каждой из которых по две открытые буквы, образующие такую пару. Пары не повторяются. Заметим, что возможна ситуация, когда последовательность букв “AB” в слове допустима, а “BA” — нет, в этом случае списке будет дана только пара “AB”, а пары “BA” не будет.

На следующей строке расположено одно целое число \(N\) (\(1 \leq N \leq 500\)) — длина зашифрованного слова, а на следующей строке — само слово (\(N\) маленьких латинских букв).

Может оказаться так, что какой-то открытой букве не соответствует ни одна «зашифрованная»; это означает, что эта буква в открытом тексте не использовалась.

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

Если вариантов дешифрования нет ни одного, в первую строку выходного файла выведите “no”.

Если вариант дешифрования ровно один, в первую строку выходного файла выведите “only”, а во вторую — дешифрованное слово.

Если вариантов дешифрования больше одного, в первую строку выходного файла выведите “many”, а во вторую и третью — любые два различных варианта дешифрования слова.

Примеры
Входные данные
1
Uz
0
2
zz
Выходные данные
no
Входные данные
1
Uz
0
1
z
Выходные данные
only
U
Входные данные
2
Uz
Xz
3
UU
XX
XU
2
zz
Выходные данные
many
UU
XU
Входные данные
7
Aa
Az
Ax
Cz
Dv
Bx
Bz
5
AB
CA
BC
CB
DE
4
zzxx
Выходные данные
only
BCAB
Страница: << 3 4 5 6 7 8 9 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест