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

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

Условие

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

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

Дано 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 B. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

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

Задача C. Knapsack problem

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

Условие

Дана последовательность из 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

Задача D. Вторая задача для СММ

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

Условие

Скрытая модель Маркова предназначена для описания стохастически эволюционирующих во времени процессов. Она представляет из себя ориентированный граф состояний, ребрам которого приписаны веса aij, равные вероятностям перехода из состояния i в j, причем диагональным элементам соответствует вероятность того, что система останется в том же состоянии.

Кроме того, для каждого состояния известна вероятность bi того, что оно окажется начальным.

Для стороннего наблюдателя состояние не является доступной напрямую информацией — оно скрыто. Зато он может видеть некоторый производимый системой сигнал, распределение вероятностей которого зависит от состояния. Таким образом, задание модели завершается указанием матрицы cij — вероятности наблюдать сигнал j при том, что система находится в состоянии i.

Вторая задача для СММ состоит в том, чтобы по данной модели aij bi cij установить последовательность состояний w1, ..., wk, которая бы являлось наиболее вероятной для данной последовательности сигналов s1, ... , sk. Напишите программу, которая решает эту задачу.

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

Первая строка входного файла содержит числа N, M, K — количество состояний, уровней сигнала и длину последовательности наблюдений соответственно.

Вторая строка содержит N чисел bi.

Следующие N строк содержат по N действительных чисел от 0 до 1 и задают матрицу aij, где i — номер строки, а j — столбца. Сумма элементов каждой строки равна единице.

Следующие N строк содержат по M чисел от 0 до 1 и задают матрицу cij.

Последняя строка содержит K целых чисел от 1 до M и задает последовательность наблюдений si

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

В выходной файл выведите K целых чисел wi.

Ограничения

1 ≤ N, M, K ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 8
0 0 1
0.4 0.3 0.3
0.2 0.6 0.2
0.1 0.1 0.8
1 0 0
0 1 0
0 0 1
3 3 3 1 1 3 2 3
3 3 3 1 1 3 2 3

0.136s 0.006s 21