Problem A. Integer approximation
Statement
The FORTH programming language does not support floating-point arithmetic
at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow
and most of the time can be emulated by integers with proper scaling. For example, to
calculate the area of the circle with the radius
R he suggests to use formula like
R * R * 355 / 113, which is in fact surprisingly accurate. The value of 355 / 113 =
3.14159... is approximating the value of π with the absolute error of only about 10
-7.
You are to find the best integer approximation of a given floating-point number
A
within a given integer limit
L. That is, to find such two integers
N and
D
(1 ≤ N, D ≤ L) that the value of absolute error
|A - N / D| is minimal.
Input file format
The first line of input file contains a floating-point number
A with the precision of up to
15 decimal digits. The second line contains the integer limit
L.
Output file format
Output file must contain two integers,
N and
D, separated by space.
Constraints
0.1 ≤ A < 10,
1 ≤ L ≤ 100000
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3.14159265358979
10000
|
355 113
|
Задача B. Выражение
Условие
Пусть задана конечная последовательность целых чисел. Если между всеми соседними числами поставить по одному знаку арифметической операции сложения,
вычитания или умножения, получится арифметическое выражение, значение которого можно посчитать. При этом, согласно общепринятым правилам, сначала выполняются
операции умножения, как более приоритетные. И только затем - сложения и вычитания. Напишите программу, которая по заданному набору чисел найдет такую
расстановку знаков арифметических операций, что соответствующее выражение окажется равным нулю.
Формат входного файла
Первая строка входного файла содержит число
N — количество элементов последовательности.
Вторая строка содержит
N целых чисел
Ai — элементы последовательности.
Формат выходного файла
Выведите в выходной файл текстовую строку, состоящую из знаков арифметических операций, не разделяя их пробелами. При этом '+' должен соответствовать
сложению, '-' - вычитанию, '*' - умножению. Если искомой последовательности не существует, выведите 'No solution'. Если существует несколько решений,
выведите любое из них.
Ограничения
2 ≤ N ≤ 8, −10 ≤ Ai ≤ 10
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3
5 10 15
|
+-
|
| 2 |
4
4 5 15 5
|
*--
|
| 3 |
4
4 5 16 5
|
No solution
|
Problem C. Network Saboteur
Statement
A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts.
A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.
Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.
The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum of all Cij, where i belongs to A, and j belongs to B.
Input file format
The first line of input file contains a number of nodes N. The following N lines, containing N space-separated integers each, represent the traffic matrix C.
Output file format
Output file must contain a single integer - the maximum traffic between the subnetworks.
Constraints
2 ≤ N ≤ 20; 0 ≤ C
ij ≤ 10000.
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
3
0 50 30
50 0 40
30 40 0
|
90
|
