Секция «Программирование»
ЗАДАНИЯ ОЧНОГО ТУРА
КРАЕВОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ
СТУДЕНТОВ ССУЗОВ
(10 марта 2011 г., г. Бийск)
Секция «Программирование»
Памятка участникам
Решенные задачи должны представлять собой скомпилированные программы с именем, соответствующим номеру задачи (например, 1.exe, 2.exe и т. д.), находящиеся в папке на Рабочем столе, наименованной фамилией участника. По желанию могут быть вложены файлы исходных текстов программ (рекомендуется).
Программы не должны требовать каких-либо действий со стороны пользователя (например, ввода с клавиатуры и т. п.), содержимое выходного файла должно строго соответствовать условию задачи и приведенным примерам, не должно содержаться посторонних символов, не оговоренных в условии (например, лишних пробелов), поскольку используется автоматическая проверка.
Имя входного файла: input. txt
Имя выходного файла: output. txt
Задача №1
Максимальный балл: 10
Вход — два множества натуральных чисел.
Выход — их пересечение (перечисление элементов через пробел, отсортированных по возрастанию, без повторений) или слово empty, если пересечение пусто.
Множества A={a1, a2, ..., an} и B={b1, b2, ..., bk} на входе представлены как последовательности натуральных чисел, разделенных пробелом. Возможны повторения элементов, которые надо исключить. Размеры множеств меньше 100. Сами числа меньше 256.
Пример:
Вход#1
6 7 8 1 2 3
4 3 2 1 1
Выход#1
1 2 3
Задача №2
Максимальный балл: 10
Вам нужно просто раскрыть скобки В выражении встречаются переменные величины (однобуквенные, от «a» до «z»), знак плюс («+») и скобочки «(» «)». Для умножения не используется никакого знака. Например:
(a+b)(c+d)e+f
Считайте, что
1) умножение некоммутативно, то есть ab ≠ ba.
2) произведение нескольких скобок следует раскрывать, начиная с самой левой, то есть
(a+b)(c+d) = ac + ad + bc + bd,
но
(a+b)(c+d) ≠ ac + bc + ad + bd
Вход — Выражение менее чем из 200 букв.
Выход — Если в выражении есть ошибка, то выведите «#error». Иначе выведите результат раскрывания скобок.
Пример:
Вход#1
(a+b+c)(a+b+f)
Выход#1
aa+ab+af+ba+bb+bf+ca+cb+cf
Вход#2
(+a)
Выход#2
#error
Вход#3
((a)
Выход#3
#error
Задача №3
Максимальный балл: 5
Вавилонцы решили построить удивительную башню — расширяющуюся к верху и содержащую бесконечное число этажей и комнат. Она устроена следующим образом — на первом этаже одна комната, затем идет два этажа на каждом из которых по две комнаты, затем идёт три этажа, на каждом из которых по три комнаты и так далее.
Эту башню решили оборудовать лифтом — и вот задача: нужно научиться по номеру комнаты определять, на каком этаже она находится и какая она по счету слева на этом этаже.
Вход — В первой строчке задан номер комнаты N, 1 ≤ N ≤ 65535.
Выход — Два целых числа — номер этажа и порядковый номер слева на этаже.
Пример:
Вход#1
1
Выход#1
1 1
Вход#2
5
Выход#2
3 2
Задача №4
Максимальный балл: 25
Найти количество расстановок N ферзей на доске N x N. Ни один ферзь не должен бить другого, т. е. не должно существовать ни одной пары ферзей, стоящих на одной вертикали, горизонтали или диагонали.
Вход — Число 1 ≤ N ≤ 15.
Выход — Число допустимых расстановок ферзей.
Пример:
Вход#1
8
Выход#1
92
Задача №5
Максимальный балл: 10
Во входном файле множество натуральных чисел. Причем каждое число встречается четное число раз. Только одно из чисел во входе встречается нечетное число раз. Найдите его.
Вход — В первой строчке количество чисел N < 65535. Затем идут N натуральных чисел меньше 65535.
Выход — Натуральное число, которое встречается нечетное число раз.
Пример:
Вход#1
9
3 1 2 2 17 1 3 17 3
Выход#1
3
Вход#2
5
12 13 14 13 12
Выход#2
14
Задача №6
Максимальный балл: 20
В трехмерном пространстве дано несколько замкнутых шаров. Нужно проверить есть ли точка, которая принадлежит всем шарам.
Вход — В первой строчке дано число шаров N, 1 < N < 20. Затем идут N строчек, каждая из которых содержит 4 натуральных числа X, Y, Z, R соответствующие координатам центров шаров и их радиусам, |X|, |Y|, |Z| < 10000, 1 ≤ R < 10000,
Выход — Строчка со словом NO, если общей точки нет, или YES, если такая точка есть.
Пример:
Вход#1
2
0 0 0 1
0 0 2 1
Выход#1
yes
Задача №7
Максимальный балл: 20
Найдите число частей, на которые разбили плоскость данные отрезки.
Вход — В первой строке записано число отрезков N, натуральное число, не превосходящее 1000. Затем идут N строк с описание отрезков — декартовы координаты концов отрезков, а именно, целые числа Х1, Y1, Х2, Y2, не превосходящие по модулю 65535.
Выход — Количество частей, на которые эти отрезки разбили плоскость (включая «внешнюю» часть).
Пример:
Вход#1
1
1 1 2 2
Выход#1
1
Вход#2
4
0 0 0 1
0 1 1 1
1 1 1 0
1 0 0 0
Выход#2
2
