Доброго времени суток!

Задача А.

Реализация.

Задача B.

Ладей можно было расставлять по диагоналям.

Задача С.

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

• Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано x_i людей в лучшем ответе.
• Города лучше всего захватывать в порядке a_i - x_i (очевидно).
• В одном из лучших ответов города надо захватывать в порядке a_i. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и a_i > a_j, то x_j = 0 (зачем нам кого-то нанимать, если можно весь город захватить бесплатно). "Перекинем" часть закупок из i-того города в j-тый. Противоречие. (см. пункт 5))
• Пусть теперь в последнем городе мы закупили солдат больше, чем надо для победы (а в каком-то меньше (иначе мы уже потратили не меньше денег, чем в построенном ответе)). Перекинем одного из закупленных солдат в какой-то город, в котором не закупили всех. Тогда мы всё равно присоединим последний город.
• Каждая операция, описанная в решении не увеличивает число потраченных денег и перекидывает покупки в более дешёвые города, то есть проблем с зацикливанием нет.

Решение.

Задача D.

Решение от heavenly_phoenix.

Будем обрабатывать запросы в оффлайн. Для каждого участка будем за O(n) обновлять его высоту. Если номер этого участка - начало порыва ветра чётное число то добавляем соответствующую высоту к этому участку, иначе отнимаем.

Задача Е.

Решение от Anuar.

Обозначения:

• А — множество столбиков на которые Петя может закинуть кольца
• B — множество столбиков на которые Петя может закинуть кольца
• C — множество столбиков на которые и Петя и Вася могут закинуть кольца

|x| -> размер некоторого множества x Так как они играют оптимально оба вначале кидают по очереди кольца в множество С. После этого они кидают в свои множества (т.е Петя в А, Вася в В).

Их очки можно выразить такой формулой:

• Очки Пети: min( |A| — |C| + ceil(|C| / 2) , ceil(m / 2) )
• Очки Васи: min( |B| — |C| + floor(|C| / 2) , floor(m / 2) )

Код решения

Задача F.

Решение от Na2a.

Перебираем делителей a * b и ищем такие x, y что x * y = a * b && gcd(x, y) == gcd(a, b) обновляем ответ. Делитель a * b = делитель a * делитель b. Работает за (количество делителей a) * (количество делителей b). Решение.

Задача G.

Решение от Zharaskhan.

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

int ans = 0;
for (int i = n; i >= 1; i--) {
    if (double(sum / double(i)) >= double(a[i])) {
        break;
    }
    ans++;
}

Задача H.

Решение от Zharaskhan.

Посчитаем сколько раз встречается первое и второе слово каждой строки через map Если первое слово встречается больше одного раза тогда это слово Имя, значить упорядочим строку. После этого отсортируем массив.

pair <string, pair <string, string> > a[n];
map <string, int> cnt;
for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second.first >> a[i].second.second;
    cnt[a[i].first]++;
    cnt[a[i].second.first]++; 
}
for (int i = 1; i <= n; i++) {
    if (cnt[a[i].first] > 1) {
      swap(a[i].first, a[i].second.second);
      swap(a[i].second.first, a[i].second.second);
    }
}
sort(a + 1, a + 1 + n);

Задача I.

Решение от Alex_2oo8.

Сведем задачу к кратчайшему пути в графе. Вершинами графа будут состояния (l1, l2, dir), означающие, что мы находимся на перекрестке прямых l1 и l2 и смотрим в данный момент либо по направлению прямой l1 (dir = 0), либо против него (dir = 1). Также добавим две вершины — старт и финиш.

Ребра будут трех типов:

• Мы можем продолжить движение по прямой до следующего перекрестка. То есть из состояния (l1, l2, dir) в (l1, l3, dir), если пересечение прямых l1 и l3 находится в нужном направлении от пересечения l1 и l2 (или они совпадают). Стоимость таких ребер — 0, так как поворачивать нам не нужно

• Либо на как-то перекрестке мы можем повернуть — то есть добавляем ребро из (l1, l2, dir) в (l2, l1, new_dir), стоимость такого ребра — угол между данными векторами.

• И последний вид ребер — это ребра из старта (достаточно добавить два ребра с ценой 0) и аналогично два ребра в финиш.

Как и во всех геометрических задачах, реализация всего этого куда сложнее идеи (по крайней мере для нас). Стоит не забыть, что прямые могут быть параллельными, некоторые из данных точек могут совпадать. Геометрическая составляющая — это нахождение точки пересечения двух прямых и угла между двумя векторами. Для последнего мы использовали скалярное произведение и арккосинус.

Задача J.

Решение от SEFI2.

Решение.

Задача K.

Решение от Na2a.

Добавляем по несколько клеток слева, справа, сверху и снизу (я добавил 20 клеток) и отмечаем их '.'. Напишем функцию win(ch) => количество позиций что если в них поставить ch (X или 0), то можно выиграть.

• Если win('X') > 0 то первый игрок может выиграть сразу, следовательно ответ равен win('X').

• Иначе, смотрим win('0'). Если позиций, где второй игрок выиграет, больше одного, то мы проиграем в любом случае. (Мы закроем одну позицию, но следующий ход он выиграет).

• Если win('0') равен одному, то мы закрываем эту позицию, а следующий ход второй игрок не может выиграть. Ему будет оптимальнее закрыть один наш выигрышный ход, следовательно ответ win('X') — 1.

• Иначе, перебираем клетку куда мы ставим 'X'. Если после того, как мы поставили Х на эту клетку, на поле выигрышных клеток стало больше одного, то увеличиваем ответ.

Функию win(ch) надо реализовать не на всем поле, а на каком то подпрямоугольнике. Решение.

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