Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд.
Блюдо с номером i стоит ci рублей. Для каждого блюда известен
также коэффициент сытости блюда — ai.
Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы
сумма коэффициентов сытости съеденных блюд была не меньше A.
Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно
меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более
одной порции блюда (любое целое неотрицательное число порций).
Формат входного файла
Входной файл содержит целые числа NA.
Далее следуют N пар целых чисел ciai.
Формат выходного файла
Выходной файл должен содержать минимальную сумму денег,
которую нужно потратить, чтобы наесться.
Школьник Петя собрал собственный цветной дисплей с разрешением 2 пикселя по вертикали и N пикселей по горизонтали.
Каждый пиксель определяется координатами (a, b), где a — номер строки от 1 до 2,
а b — номер столбца от 1 до N.
На дисплее с таким разрешением уже можно играть и Петя разрабатывает одну из игр — "Бег по коридору".
По правилам игры, каждый пиксель может быть либо свободен, либо занят препятствием, либо занят игроком, либо занят эликсиром.
Игрок может перемещаться в один из смежных пикселей, не занятых препятствием
(смежными называются пиксели, соседствующие либо в строке, либо в столбце).
В начале у игрока нулевой уровень усталости. Каждое перемещение добавляет к текущему уровню усталости единицу.
Как только игрок перемещается на пиксель, занятый эликсиром, он выпивает эликсир,
и уровень усталости уменьшается на единицу.
Таким образом, перемещение на пиксель с эликсиром не увеличивает уровня усталости.
Когда игрок покидает клетку, на которой был эликсир, она становится свободной.
Изначально игрок находится в пикселе с координатами (1, 1).
Цель игры — добраться до N-ого столбца, минимизировав конечный уровень усталости.
Вам необходимо написать программу, которая по заданному плану коридора определит минимальный уровень усталости,
с которым можно пройти игру.
Формат входного файла
В первой строке входного файла содержится число N — горизонтальное разрешение дисплея.
Далее следует описание игрового поля — пара строк длиной N каждая. Символ "." (точка) соответствует свободному пикселю,
символ "#" (решетка) — занятому препятствием, символ "X" (прописная латинская X) — пикселю с эликсиром.
Гарантируется, что первый символ первой строки равен ".", кроме того, последний символ хотя бы одной из двух строк не равен "#".
Гарантируется, что можно добраться до N-ого столбца.
Формат выходного файла
В выходной файл выведите единственное число — минимальный уровень усталости, которого можно достичь, пройдя игру.
Группа туристов, состоящая из B мальчиков и G девочек, подошла ночью к речке.
Переправиться на противоположную сторону можно только по перекинутому на другой берег бревну.
По бревну может идти либо один человек, либо двое одновременно, держась за руки.
Переходить по бревну в темноте опасно, а фонарик, к сожалению, у всей группы только один.
Поэтому его придется носить по бревну с одного берега на другой таким образом,
чтобы каждый переход был освещен.
Известно время TB, за которое перейдет по бревну мальчик и время
TG, за которое перейдет девочка.
Требуется найти минимальное время T, за которое может переправиться вся группа.
Формат входного файла
Входной файл содержит целые числа B, G, TB, TG, разделенные пробелами.
Формат выходного файла
Выходной файл должен содержать единственное число — минимальное время T.
Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок.
Назовём такую последовательность скобочной. Скобочная последовательность
называется правильной, если она может быть построена
по следующим законам:
пустая строка является правильной скобочной последовательностью;
если S — правильная скобочная последовательность, то (S) —
тоже правильная скобочная последовательность.
если A и B — правильные скобочные последовательности, то AB —
тоже правильная скобочная последовательность.
Примеры правильных скобочных последовательностей —
"()", "((()))", "()()()", "((()())())(())".
Неформально говоря, правильная скобочная последовательность — это
последовательность скобок, которая может быть получена из некоторого
арифметического выражения удалением из него всего, кроме скобок.
Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной
последовательности и скобки в ней меняются на противоположные, то есть все символы '('
в этой подстроке заменяются на ')', а все символы ')' — на '('.
Требуется написать программу, которая по скобочной последовательности рассчитает
минимальное количество шагов N, необходимое для превращения её в правильную.
Формат входного файла
Во входном файле содержится скобочная последовательность.
Формат выходного файла
В выходном файле должно содержаться число N, за которым следуют N
пар чисел liri, задающих позиции первого и последнего символа подстроки,
в которой на i-ом шаге меняются скобки.
Если существует несколько оптимальных решений, выведите любое из них.
Если решения не существует, выведите единственное число −1.
Ограничения
Длина исходной последовательности находится в диапазоне от 1 до 3000 символов
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано E — вес пустой копилки, F — вес копилки с монетами,
N — количество достоинств монет,
Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа EFN.
В следующих N строках находятся по два числа — CiWi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число −1.
