IT-CON 2012(Фотоотчет)

Начало разбора

IT-CON 2012 (Олимпиада для студентов 3-5 курсов) Разбор + Материалы + Монитор

Условия задач

Разбор:
A. Трехзначные числа
Задачу можно решать перебором всех чисел в интервале [100,999], что дает генерацию чисел в порядке возрастания. Для каждого числа находим сумму цифр и сравниваем ее с заданной. Удовлетворяющие числа будем хранить в динамическом массиве.

Решение 1(конвертация числа в строку)
Решение 2(откусывание последней цифры числа)
Решение 3(перебор цифр)

B. Электронная почта
Задача ну умение переводить буквы латинского алфавита в нижний регистр. Пожалуй самая легкая задача олимпиады.

Решение 1(с использованием функции tolower())
Решение 2(сопоставление заглавных и прописных букв)
Решение 3(с использованием смещения)

C. Римские числа
Решение задачи описано в самом условии. На каждом шаге рассмотрим текущую цифру и последующую. Если текущая цифра меньше последующей, то к результирующему ответу прибавляем разницу последующей цифры и текущей и пропускаем эти две римские цифры. Если сложилась ситуация, что текущая цифра не меньше последующей, то к ответу прибавляется только значение текущей цифры и переходим к последующей цифре. Если на каком то этапе можно рассмотреть только текущую цифру, то прибавляем ее значение к ответу.

Решение

D. Уникальные элементы
Самым простым решением было “загнать” все элементы в set и вывести количество элементов получившегося set’a.
В рамках другого решения можно было отсортировать массив любым известным алгоритмом сортировки, алгоритмическая сложность которого не превышала бы квадратичную. В результате можно было перебрать все пары соседних элементов и найти те из них, где текущий элемент не равен последующему. Количество таких пар + 1 является ответом на задачу.

Решение 1 (с использованием set’a)
Решение 2 (с использованием sort’a)
 
E. Сапер
Чисто техническая задача. Жизнь существенно упростит массив движений, в котором нужно записать смещения в 8 направлений:

1. ...
2. int moveX[8] = {-1,-1,-1, 0, 0, 1,1,1};
3. int moveY[8] = {-1, 0, 1,-1, 1,-1,0,1};
4. bool correct(int x, int y) {
5.   if (x < 1 || y < 1) return false;
6.   if (x > n || y > m) return false;
7.   return true;
8. }
9. ...
10. for (int p=0;p<8;++p){
11.   int x = i + moveX[p];
12.   int y = j + moveY[p];
13.   if (correct(x,y) && mas[x][y] !=-1)
14.     ++mas[x][y];
15. ...

* This source code was highlighted with Source Code Highlighter.

Решение

F. Генерация подмножеств
Классическая задача по комбинаторике.
Рассмотрим первое решение. Пусть N = 3. Рассмотрим все числа от 0 до 2^n – 1.
           123
      0 –> 000 = {}
      1 –> 001 = {3}
      2 –> 010 = {2}
      3 –> 011 = {2,3}
      4 –> 100 = {1}
      5 –> 101 = {1,3}
      6 –> 110 = {1,2}
      7 –> 111 = {1,2,3}

Решение 1 (через двоичное представление)
Решение 2 (рекурсивное с построением дерева состояний)

G. Количество нулей у факториала
Стоит заметить, что количество нулей, на которые заканчивается факториал равно количеству десяток в разложении этого факториала на множители. Десятка состоит из двух простых сомножителей. При этом множитель 5 в разложении факториала на простые множители будет встречаться намного реже, чем множитель 2. Поэтому количество нулей у факториала на конце будет равно количеству пятерок в разложении его на простые множители.

Решение 1
Решение 2

H. Язык разметки RHTML 1.0.
Можно применить один из двух подходов: конечный автомат и механизм “откусывания”.
Первый пишется дольше, но работает всегда быстрее и легко масштабируется. Второй способ пишется проще и работает чуть медленнее. Главное аккуратность и обильное тестирование.

Решение 1 (конечный автомат)
Решение 2 (с помощью “откусывания”)
Решение 3 (конечный автомат + С-строка) [Автор: Сагунов Данил]

I. Объединение прямоугольников
Единственная задача, для которой я не писал тесты, а взял оригинальные с задачника Федора Меньшикова.
Я ее уже рассматривал ранее(6D. Площадь прямоугольников)

Решение

J. Путь в матрице
Оригинальное условие задачи находится здесь: http://projecteuler.net/problem=83
Я предполагал решение задачи через алгоритм Дейкстры, но ограничения были подобраны так, что и реализация алгоритма Флойда также укладывались в отведенные лимиты. При таком подходе представляет исходную матрицу в виде графа, где каждая вершина имеет до 4 соседей. Ребро между (i,j) и (i+1,j) вершиной будет иметь вес a[i][j], где a – исходная матрица. После того как граф построен можно запускать вышеописанные алгоритмы.
Участники, сдавшие решения предложили обычный BFS на матрице. Это решение пишется намного проще.

Решение 1(алгоритм Флойда)
Решение 2(алгоритм Дейкстры)
Решение 3(BFS)


Тесты и условия задач: http://goo.gl/DvISB
Авторские решения:     http://goo.gl/lyEjn
Размороженный монитор: http://goo.gl/QOTRa