Задача A. Свинья-копилка
Условие
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано
E — вес пустой копилки,
F — вес копилки с монетами,
N — количество достоинств монет,
Ci и
Wi — достоинство и вес каждого вида монет (
1 ≤ i ≤ N).
Требуется определить минимальную сумму, которая может содержаться в копилке.
Формат входного файла
В первой строке входного файла содержатся числа E F N.
В следующих N строках находятся по два числа — Ci Wi.
Все числа во входном файле — целые.
Формат выходного файла
В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке.
Если заданный вес копилки F не может быть достигнут с монетами заданного типа,
то в выходной файл следует записать число −1.
Ограничения
1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100
1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
10 110 2
1 1
30 50
|
60
|
| 2 |
10 110 2
1 1
50 30
|
100
|
| 3 |
1 6 2
10 3
20 4
|
-1
|
Задача B. Замена скобок: минимизация шагов
Условие
Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок.
Назовём такую последовательность скобочной. Скобочная последовательность
называется правильной, если она может быть построена
по следующим законам:
- пустая строка является правильной скобочной последовательностью;
- если S — правильная скобочная последовательность, то (S) —
тоже правильная скобочная последовательность.
- если A и B — правильные скобочные последовательности, то AB —
тоже правильная скобочная последовательность.
Примеры правильных скобочных последовательностей —
"()", "((()))", "()()()", "((()())())(())".
Неформально говоря, правильная скобочная последовательность — это
последовательность скобок, которая может быть получена из некоторого
арифметического выражения удалением из него всего, кроме скобок.
Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной
последовательности и скобки в ней меняются на противоположные, то есть все символы '('
в этой подстроке заменяются на ')', а все символы ')' — на '('.
Требуется написать программу, которая по скобочной последовательности рассчитает
минимальное количество шагов N, необходимое для превращения её в правильную.
Формат входного файла
Во входном файле содержится скобочная последовательность.
Формат выходного файла
В выходном файле должно содержаться число N, за которым следуют N
пар чисел li ri, задающих позиции первого и последнего символа подстроки,
в которой на i-ом шаге меняются скобки.
Если существует несколько оптимальных решений, выведите любое из них.
Если решения не существует, выведите единственное число −1.
Ограничения
Длина исходной последовательности находится в диапазоне от 1 до 3000 символов
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
()
|
0
|
| 2 |
))((()
|
1
1 4
|
| 3 |
)((()((()((()(((
|
2
1 16
2 7
|
Задача C. Плотность населения
Условие
После проведения переписи населения Флатландии все данные были нанесены на карту.
Прямоугольная карта Флатландии была разделена на клетки единичного размера.
Число жителей в каждой клетке изменяется от 0 до 9.
Напишите программу, которая находит прямоугольную область наибольшей площади,
средняя плотность населения в которой не менее заданной величины K.
Формат входного файла
В первой строке входного файла содержится три целых числа,
разделенных пробелами — размеры Флатландии
N,
M и заданная плотность населения
K.
Далее следует
N строк, каждая из которых содержит
M цифр от 0 до 9 —
карта распределения населения Флатландии.
Формат выходного файла
В первой строке выходного файла вывести четыре целых числа,
разделяя их пробелами — номер строки и столбца для левого верхнего угла искомого прямоугольника,
его высота и ширина.
Если существует несколько областей максимальной площади, то вывести любой вариант.
Если такой области не существует, вывести строку "0 0 0 0" (без кавычек).
Ограничения
1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 9
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 3 1
020
102
020
|
1 2 3 2
|
