Задача A. Knapsack problem
Условие
Дана последовательность из
N целых чисел. Найдите любую из ее подпоследовательностей,
сумма элементов которой равна
w, либо установите,
что искомой подпоследовательности не существует.
Формат входного файла
Во входном файле находятся числа
N и
w, а за ними следует последовательность
из
N целых чисел
ai.
Формат выходного файла
Если искомая подпоследовательность существует, выведите
N чисел 0 или 1, разделенных пробелами.
Единица на позиции
i означает, что элемент последовательности
ai принадлежит найденной
подпоследовательности, 0 означает обратное. В противном случае выведите
−1.
Ограничения
1 ≤ N ≤ 40,
0 ≤ ai,w ≤ 10000000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 7
1 5 6
|
1 0 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. Свинья-копилка
Условие
Начинающий бизнесмен Вася копит в свинье-копилке деньги на открытие собственного дела.
Как известно, количество денег в копилке можно определить, только разбив ее.
Однако Вася не хочет разбивать копилку раньше, чем будет накоплена требуемая сумма.
Друг подсказал Васе, что можно оценить минимальное количество денег в копилке,
зная вес пустой копилки и вес копилки с монетами.
Дано
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
|
Problem D. Ford-Bellman
Statement
You are to write a program that finds shortest distances from vertex S
to all other vertices in a given directed weighted graph.
Graph consists of
N vertices, numbered from 1 to
N, and
M edges.
Input file format
Input file contains two integers
N M S, followed my
M triplets of integers
ui vi wi — starting vertex, ending vertex and weight or the edge.
There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.
Output file format
Output file must contain a vector of
N integers — distances from vertex
S to other vertices.
The distance from any vertex to itself is considered to be 0.
If some vertex is not reachable from
S, corresponding cell of the vector must contain empty space.
Constraints
0 ≤
N,
M ≤ 1000.
All weights are less than 1000 by absolute value.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3 3 1
1 2 5
1 3 10
2 3 2
|
0 5 7
|
