Azret's blog

By Azret, 10 years ago, In Russian

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

Задача А.

Реализация.

Задача B.

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

Задача С.

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

  • Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано xi людей в лучшем ответе.
  • Города лучше всего захватывать в порядке ai - xi (очевидно).
  • В одном из лучших ответов города надо захватывать в порядке ai. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и ai > aj, то xj = 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. Код решения может не совпадать с идеей, так как был взят от другого пользователя.

  • Vote: I like it
  • +32
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it
int main ()
{
    freopen ("gcm.in","r",stdin);
    freopen ("gcm.out","w",stdout);
    long long int a,b,c,i,d,a1,b1;
    cin>>a>>b;
    d=__gcd(a,b);
    a1=a/d;
    b1=b/d;
    for (i=sqrt(a1*b1); i>=1; i--)
    {
        if ((a1*b1)%i==0)
        {
            if (__gcd(i,(a1*b1)/i)==1){c=i;break;}
        }
    }
    cout<<c*d<<" "<<(a1*b1*d)/c;
    return 0;
}
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Эх.
    d = 1.
    a, b — большие.
    (a / d) * (b / d) — до 10^18.
    sqrt(10^18) = 10^9 — многовато.

  • »
    »
    10 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Надо по-другому искать делители.