Разбор заданий "I-общеуниверситетской олимпиады."
27 ноября - 4 декабря 2006г.

Задание 1. "Письмена".
Аналогичное задание можно найти в сборниках по теме "структуры данных". Но, как показала олимпиада, это задание являлось самым сложным. Основным методом его решения является полный перебор всех вариантов, подставляя слову из n букв в предложении все слова из n букв из словаря и заменяя соответствующие символы в нем и во всем предложении. Если же было найдено нарушение - то откат замены, если же замена прошла без ошибок - то заменяются буквы следующего слова. В этом задании стоило обратить внимание на то, что диапазон входных данных 10Кбайт и что существует однозначное решение. Это означает соответственно что:
а) словарь не может состоять только из слов с 1ой буквой, так как таких слов будет максимум 26 и так далее;
б) словарь и предложения могут быть различной длины в каждом тесте, и поэтому будет не рационально резервировать под них предварительно память (int a[10*1024]).
Ввиду использования этого задания как примерочного на тренировках, решению Жюри может быть отправлено только при согласовании по почте.

Задание 2. "Решетка".
Это задание является репликацией исторического факта кодирования писем. Предполагаемый метод решения этого задания - моделирование процесса. Т.е. требовалось брать исходную решетку и обратным процессом записывать те символы, которые были "видны" сквозь решетку. Потом решетка снималась и дописывались символы, которые не были выписаны до этого. Порядок считывания - слева - направо сверху - вниз, как и принято в русском языке.
Одно из решений участников: Avers.

Задание 3. "Штриховка"
Снова типичное задание на полный перебор с отсечением неверных комбинаций. При переборе следовало учесть что всего различных состояний одного символа - 4 (может быть и меньше.) - это все повороты этого символа - на 0 , 90 , 180 , 270 градусов соответственно. Все поле представляется матрицей из 0. Символы - +1. Если при наложении символов на поле (a[i][j]++) какая-либо ячейка имеет значение больше чем 1, значит - в этой ячейки произошло наложение одного символа на другой.
Одно из решений участников: Igoryk.

Задание 4. "Вопросы"
Самое простое задание этой олимпиады. 2 консультанта - два ключа, к которым прибавлялось новое значение из входного массива по правилу: если у 1го консультанта ключ меньше - прибавляем ему, иначе - ко второму. Ответ = максимальный ключ + 1.
В качестве примера - решение Igoryk.

Задание 5. "Карты"
Геометрическая задача. Одной из основных идей ее решения является следующая:
Все поле делится на квадраты размером 1х1. В центре каждого квадрата есть точка (0.5*x , 0.5*y). Перебирая значения для x и y мы пройдем все квадраты на поле. Далее для каждого квадрата мы перебираем все прямоугольники, которые есть на карте. Если точка - внутри прямоугольника то счетчику вложенности inside++ , для это рациональнее всего использовать функцию isinside(plot_x, plot_y, ax,ay,bx,by). Если inside превышает 2 - то это - Mad Zone. Количество этих Mad Zone и требовалось посчитать.
Одно из решений участников: kp-it4 .

На сервере в банк задач на дорешивание выложены задания "Письмена" и "Решетка".