Задача A. Свинья-копилка

Автор:А. Кленин, краевая олимпиада 2001 г.
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

Друг подсказал Васе, что можно оценить минимальное количество денег в копилке, зная вес пустой копилки и вес копилки с монетами.

Дано 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. Переворот бокалов

Автор:Кленин А.С.
Входной файл: input.txt   Ограничение времени:10 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

На столе стоят в ряд N бокалов, пронумерованных слева направо от 1 до N. Первоначально все бокалы стоят дном вниз. Над бокалами можно выполнить операцию переворот. За один переворот ровно M любых бокалов переворачиваются так, что те бокалы, которые стояли дном вниз, оказываются перевернутыми вверх дном, а остальные из M бокалов ставятся вниз дном. Требуется за минимальное количество переворотов добиться того, чтобы все бокалы оказались перевернутыми вверх дном, или определить, что это невозможно.

Формат входного файла

Входной файл содержит числа N и M.

Формат выходного файла

Выходной файл должен в первой строке содержать число переворотов K, а в последующих K строках - разделенные пробелами номера бокалов, которые нужно перевернуть при очередном перевороте. Если перевернуть все бокалы невозможно, то выходной файл должен содержать единственное число 0 (ноль).

Ограничения

1 < N < 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 3
3
1 2 3
3 4 5
3 6 7

Задача C. Неполное решение

Автор:И. Олейников, И. Туфанов, И. Бураго, А. Жуплев
Входной файл: input.txt   Ограничение времени:2 сек
Выходной файл: output.txt   Ограничение памяти:64 Мб

Условие

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

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

Помимо вышеперечисленного известно, что:

  1. Количество операндов равно N.
  2. Операции в примере выполняются слева направо, т.е. 1+2/3*4 означает ((1+2)/3)*4.
  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
/

0.026s 0.003s 13