Vladislav_133 26 фев 2011, 13:48
Начало олимпиады!
Участникам предлагается 5 задач, за верное решение которых можно набрать максимум 32 балла.
Задача 1. Прямоугольники (8 очков).
Рассмотрим множество прямоугольников на плоскости. Будем рассматривать только такие прямоугольники, стороны которых параллельны осям координат. Тогда любой из прямоугольников можно задать двумя координатами левого нижнего угла (x,y) и длинами сторон (dx,dy), где dx - длина сторон, параллельной оси 0X, dy - длина стороны, параллельной оси 0Y. Для простоты будем считать, что все прямоугольники находятся в первом квадранте т.е. все координаты x>=0 и y>=0.
Входной файл (input.txt) содержит параметры нескольких прямоугольников: в каждой строке - четыре числа x y dx dy, отделенных друг от друга пробелами. Количество прямоугольников произвольно.
Получить множество координат точек пересечения прямоугольников. Выходной файл (output.txt) должен содержать множество координат точек: x y - пара координат, отделенных друг от друга пробелами. В одной строке - одна пара координат. Если точек пересечения нет, то выходной файл должен содержать одно слово Empty.
Пример.
Файл input.txt
4 2 4 3
6 3 6 4
14 3 5 4
Файл output.txt
8 3
5 6
Задача 2. Директор школы принимает решение (8 очков).
Директор сельской школы решил отправить своих учеников на представление приехавшего в город цирка. Для отправки можно использовать автобус и маршрутное такси. Количество человек, которое может перевести автобус равно N, количество человек, которое может перевезти маршрутное такси - M. Стоимость автобуса составляет X рублей, стоимость маршрутного такси - Y рублей. Школьников надо увезти и доставить в цирк одновременно. Написать программу, которая бы определила количество автобусов и маршрутных такси для перевозки школьников, чтобы сумма оплаты проезда была бы минимальной.
Входной файл input.txt содержит стоимость заказа автобуса (X) и маршрутного такси (Y), количество посадочных мест (N и M), а также количество школьников, пожелавших ехать в цирк (K). Числа записываются через пробел
X Y N M K .
Выходной файл должен содержать количество автобусов и такси, которые должен заказать директор, чтобы сумма оплаты была минимальной.
Пример.
Файл input.txt
700 200 30 8 41
Файл output.txt
1 2
Т.е. в этом случае придется заказать один автобус и два такси.
Не исключено, что при некоторых входных значениях, возможно не одно решение, приводящее к одной и той-же сумме. В решении должен присутствовать только один вариант - все равно какой. Для простоты примем, что все входные параметры могут принимать значения от 1 до 30000.
Задача 3. Найти все подчисла (4 очка).
Пусть имеется строка, состоящая из N цифр (0-9). Значение N может быть довольно велико, но примем что N>0 и N<250. Необходимо найти все подстроки, количество разрядов в которых от 1 до 4, представляющие запись числа, неравного нулю и кратного 3.
Входной файл input.txt содержит строку, состоящую из цифр.
Выходной файл output.txt содержит все подчисла, делящиеся на 3 (по одному в строке).
Например.
Файл input.txt
1136
Файл output.txt
3
36
Важное замечание.
Если в начале подчисла идут нули, то они игнорируются.
Т.е., например, считается, что подстрока 0000100 содержит всего три разряда.
Задача 4. Две строки (4 очка).
Даны две строки a и b. Можно ли получить строку b из строки a, путем вычеркивания символов из строки a.
Входной файл input.txt содержит строки a и b.
Выходной файл содержит в первой строке слов Yes или слово No.
Например.
Файл input.txt.
abcdef
acd
Файл output.txt
Yes
Задача 5. Ваш ход, маэстро (8 очков).
Все хорошо знают игру, крестики-нолики. Задача состоит в следующем. Пусть дана некоторая позиция. Ход делает программа. Пусть программа ставит крестики. Нужно определить, может ли выиграть программа в один ход.
Входной файл input.txt содержит позицию в игре крестики-нолики.
Выходной файл содержит все возможные ходы (координаты клетки), приводящие к победе.
Пример.
Файл input.txt
1 0 -1
0 1 1
0 0 -1
Файл output.txt
0 2
Пояснения.
1 - обознаает "крестик".
0 - "нолик".
-1 - пустую клетку.
Каждая клетка имеет координаты. Система координат: начало в левом нижнем углу. Левая нижняя клетка имеет координаты 0 0.