21 марта 2013 Соловьёв Виктор [администратор] в 22:53
Разбор задач

Разбор задач внутривузовского тура олимпиады по программированию среди студентов 1-2 курса 2013 года вы можете найти внутри этой новости. Задачи олимпиады можно сдать на нашем сайте - открыта дорешка.

1 : Бактерии

Решение в лоб не сработает, так как число шагов N слишком велико.

В основе авторского решения лежит следующая формула:

Однако N операций перемножения матриц займут даже больше времени, чем решение влоб. Чтобы успешно решить задачу этим методом, нужно использовать алгоритм быстрого возведения в степень, реализовав операцию умножения для матриц. Такое решение работает с асимптотикой O(log N), то есть очень быстро.

2 : Простая задача

При решении удобно продлить массив вдвое, продублировав его элементы в том же порядке, но можно просто запукать 2 цикла один за другим.

3 : Дренажная система

В основе решение алгоритм DFS. Запуская его от каждой ячейки двумерного массива, которую мы ещё не пометили, будем переходить в соседние клетки с равным значением высоты, помечая их. Если при этом хотя бы в одной соседней клетке высота ниже, то переходить мы в неё не будем, но запомним, что вся вода с выделенной нами группы клеток утекает туда, а значит в текущей группе клеток не нужен водоотвод. Если же среди соседей клеток с меньшей высотой нет, то нужно добавить в текущую группу клеток водосток - увеличиваем ответ на 1.

4 : Собеседование

Требуется сделать именно то, что описано в условии.

5 : Королевство

Нетрудно заметить, что числа x2+1 и x2+2 никогда не делятся на 7.

Если число B имеет остаток b при делении на 7, то оно представимо в виде B = 7k + b, а его квадрат B2 = 49k2 + 14kb + b2 имеет остаток b2 mod 7. Таблица возвожных остатков для чисел x, x2, x2+1 и x2+2 представлена ниже.

x x2 x2+1 x2+2
0 0 1 2
1 1 2 3
2 4 5 6
3 9 mod 7 = 2 3 4
4 16 bod 7 = 2 3 4
5 25 mod 7 = 4 5 6
6 36 mod 7 = 1 2 3

Если число делится на 7, то его остаток при делении равен 0. Таких остатков нет в последних двух столбцах таблицы.

Входные данные считываем строкой, если её длина превышает 3, то x превышает значение 999 > 100, а значит ответ - "NO". В противном случае, строку преоразуем в число и решаем зачаду влоб.

6 : Линии

Разбор задачи будет опубликован в ближайшее время.

7 : Сольфеджио

Чтобы успешно решить эту задачу, достаточно просто преодолеть природное отвращение к длинным условиям.

Придётся считать расстояние между нотами. Для этого удобно завести массив на 8 элементов - расстояния в полутонах между 9-тью входными строками. Начальные значения этих расстояний описаны в условии, их придётся единожды скоректировать на основе знаков альтерации (первый символ каждой входной строки).

8 : Шахта

Для решения задачи идеально подойдёт структура данных стэк (stack). Символы входной строки будем обрабатывать по одному, двигаясь слева направо. Встречая символ '<' мы просто добавляем его в стек. Если мы встретили символ '>', и в стэке есть символ '<', то вместе они образуют рубин, а значит мы можем удалить последний элемент стека, а к количеству рубинов прибавить 1. Если же мы встретили '>', но стек не оканчивается символом '<', то новопрочтённый символ никогда не станет частью рубина (символы, прочтённые позже, не образуют рубин вместе с ним, а прочтённые ранее - уже не образовали, а теперь "заблокированы" им). Символ в этом случае просто вносим в стек.

9 : Базар

Пусть ai - плата i-той палатки. Заведём массив S, такой что Si равен сумме плат всех палаток с первой по i-тую включительно. Чтобы быстро найти значение Si, следует использовать равенство Si+1 = Si + ai+1.

Очевидно, что потери раджи при закрытии палаток с i-той по j-тую включительно составляют Sj - Si-1.

10 : Танки

Решение СЛАУ методом Гаусса с выбором опорного элемента (в качестве опорного подойдёт элемент с максимальным модулем в столбце). Если в какой-то момент такой элемент оказывается равным 0, то или решения нет, или их бесконечное множество - выводим "ERROR".

11 : Треугольная таблица

Пусть i и j - номер строки и номер ячейки в ней, соответственно. В отличие от случая с квадратными ячейками таблицы, у ячейки треугольной формы есть либо сосед снизу, либо сосед сверху, но не оба сразу. Ориентация ячейки изменяется как при изменении i, так и при изменении j, из чего следует, что ориентация определяется чётностью суммы индексов ячейки i+j (если эта сумма чётна, то ячейка имеет соседа снизу, иначе - сверху).

Следует так же учитывать, что элементы на краях таблицы не имееют некоторых соседей.

12 : Квадратный корень

Грубое приближение корня A (целую часть корня) найдём при помощи стандартной функции sqrt(x), отбросив дробную часть результата. Возведя a в квадрат, получим грубое приближение числа N, которое будем использовать для сравнения.

Далее 1000 раз применим алгоритм, продлевающий найденное значение корня на 1 цифру. Алгоритм поможет нам быстро находить квадрат продлённого числа, его мы будем сравнивать с N, чтобы подобрать эту цифру правильно (a2 должно быть меньше или равно N и быть максимальным). В основе упомянутого алгоритма известная всем формула:

(A + B)2 = A2 + 2AB + B2

Где A будет текущим приближением корня, а B - добавляемой цифрой. Если быть точнее, то B = b * 10-i, где b - цифра, а i - номер дробного разряда, в который мы хотим её поставить. То есть B, как и A - длинное дробное число (до 1000 знаков). A2 нам уже известно, оно является прошлым приблежением числа N, а вот AB нам нужно найти. Произведение двух длинных чисел ищется очень долго, мы не можем себе этого позволить. Вместо этого, перепишем нашу формулу в следующем виде:

(A + B)2 = A2 + 2b * A * 10-i + b2 * 10-2i

произведение A * 10-i находится очень просто: нужно сдвинуть цифры числа A на i позиций вправо. Это быстрая операция. 10-2i найдём, сдвинув длинное число 1 на 2i позиций. Числа 2b и b2 малы, умножить на них длинные числа так же не составит труда. Получается, что вычисление квадрата продлённого числа мы свели к двум операциям сдвига большого числа, двум операциям умножения большого числа на обычное и двум операциям сложения больших чисел. В таком виде алгоритм будет работать за число операций, сравнимое с длиной используемых длинных чисел. Применить его придётся в худшем случае 10 * 1000 раз - подобрать 1000 цифр, каждая из которых может принимать значение от 0 до 9.

Таким образом, чтобы сдать задачу, понадобится:

  1. Написать функцию для сдвига цифр большого числа;
  2. Написать функцию для сложения двух больших чисел;
  3. Написать функцию умножения большого числа на обыное;
  4. Решить основную задачу.