Задания очного тура краевой олимпиады по информатике студентов ССУЗОВ (10 марта 2011 г., г. Бийск)

Секция «Программирование»

ЗАДАНИЯ ОЧНОГО ТУРА

КРАЕВОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ

СТУДЕНТОВ ССУЗОВ

(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