Задача 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. Неполное решение
Условие
Отличник Вася очень любит решать задачи по математике, однако большинство одноклассников
не разделяют его любовь и поэтому списывают решения у Васи.
При решении задач Вася пишет операнды и ответ в своей тетради,
но часто торопится и пропускает арифметические операции.
Васины одноклассники при списывании вынуждены подставлять в выражение знаки операций.
Самим им это делать не хочется, а так как задачи по программированию они тоже не любят,
то попросили вас написать программу, которая делала бы это за них.
Помимо вышеперечисленного известно, что:
- Количество операндов равно N.
- Операции в примере выполняются слева направо, т.е. 1+2/3*4 означает ((1+2)/3)*4.
- При решении Вася использовал четыре операции: сложение ('+'),
вычитание ('-'), умножение ('*') и деление нацело — ('/').
- На любом этапе вычислений промежуточный результат по модулю не превосходит 1000
Формат входного файла
Во входном файле содержится целые числа
a1 a2… aN — операнды.
За которыми следует ответ
R.
Формат выходного файла
В выходном файле должна содержатся строка из
N − 1 символа — знаки операций,
которые следует подставить в решение, чтобы получить ответ
R.
Если решений несколько, выведите любое из них, если решений не существует,
выведите
IMPOSSIBLE.
Ограничения
2 ≤ N ≤ 1000, |ai| ≤ 1000, |R| ≤ 1000.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1
1
2
|
+
|
| 2 |
1
2
2
1
|
+-
|
| 3 |
10
7
1
|
/
|
Задача C. Домой на электричках
Условие
Одна из команд-участниц олимпиады решила вернуться домой на электричках.
При этом ребята хотят попасть домой как можно раньше.
К сожалению, не все электрички идут от города, где проводится олимпиада, до станции,
на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции,
останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях,
мимо которых они идут).
Все станции на линии пронумерованы числами от 1 до N.
При этом станция номер 1 находится в городе, где проводится олимпиада,
и в момент времени 0 ребята приходят на станцию.
Станция, на которую нужно попасть ребятам, имеет номер E.
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время,
за которое ребятам удастся добраться домой.
Формат входного файла
Во входном файле записаны сначала числа
N и
E.
Затем записано число M, обозначающее число рейсов электричек.
Далее идет описание M рейсов электрички.
Описание каждого рейса электрички начинается с числа
Ki — количества станций,
на которых она останавливается, а далее следует
Ki пар чисел,
первое число каждой пары задает номер станции, второе — время
(время выражается целым числом из диапазона от 0 до 10
9).
Станции внутри одного рейса упорядочены в порядке возрастания времени.
В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
Формат выходного файла
В выходной файл выведите одно число - минимальное время,
когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они
добраться не смогут, выведите -1.
Ограничения
2 ≤ E ≤ N ≤ 1000,
1 ≤ M ≤ 100,
2 ≤ Ki ≤ N.
Примеры тестов
| № |
Входной файл (a.in) |
Выходной файл (a.out) |
|---|
| 1 |
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
|
20
|
