[The Godfather]

Олимпиада по информатике НГТУ 2007 год

Прочитать:

1 Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.
Требуется определить, существует ли у них общая точка. Ограничения: координаты целые и по модулю не превосходят 10 000.
Требования к программе:
Ввод из файла segments.in. В первой строке содержатся координаты первого конца первого отрезка, во второй— второго конца первого отрезка, в третьей и четвертой — координаты концов второго отрезка. Вывод в файл segments.out. Выводится слово «Yes», если общая точка есть, слово «No» — в противном случае.
ПРИМЕР :
Ввод 1 Ввод 2
00 00
10 10
10 20
11 30
Вывод 1 Вывод 2
Yes No


2. Заданы вес Е пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов; известны ценность Рi каждого вида монет и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 < Е< F< 10 000,1 < N < 500,1 < Рi < 50 000,
1 < Wi < 10 000, все числа целые, время 2 с.
Требования к программе:
Ввод из файла piggy.in. В первой строке числа Е и F, во второй -число N, в следующих N строках — по два числа, Р, и Wi. Вывод в файл piggy.out. Выводятся два числа через пробел- минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, — вывести "This is impossible".
ПРИМЕР:

Ввод 1 Ввод 2 Ввод 3
1000 1100 1000 1010 1000 2000
2 2 1
1 1 6 3 10 3
5 2 2 2
Вывод 1 Вывод 2 Вывод 3
100 250 10 16 This is impossible


3 Два круга заданы координатами центров в прямоугольной декартовой системе координат и радиусами. Найти площадь их пересечения. Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000.
Требования к программе:
Ввод из файла circarea.in. В первой строке находятся шесть вещественных чисел через пробел— координаты центров и радиусы двух кругов: х1, у1, г1, х2, у2, г2.
Вывод в файл circarea.out. Вывести вещественное число
с двумя знаками после запятой— площадь пересечения.
ПРИМЕР:
Ввод
20.0 30.0 15.0 40.0 30.0 30.0
Вывод
608.37


4. Определим правильные скобочные выражения так:
1. Пустое выражение - правильное.
2. Если выражение S правильнее , то (S) и [s] также правильные.
3. Если выражения А и В правильные, то АВ также правильное.
Дана последовательность скобок (, ), [ и ]. Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, т.е. такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность не меняя порядок оставшихся.Ограничения: исходная последовательность содержит не более 100 скобок.
Требования к программе;
Ввод из файла bracket3.in. В первой строке символы (,), [ и ] без пробелов.
Вывод в файл bracket3.oui: Выводится искомая последовательность скобок без пробелов.

Пример 1