Блог пользователя Azret

Автор Azret, 12 лет назад, По-русски

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

Задача А.

Реализация.

Задача 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. Код решения может не совпадать с идеей, так как был взят от другого пользователя.

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
12 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

Вот задача A :))))

for(cin >> n; n; n--) {
    cin >> a;
    if(((a / 100) * (a / 100) + (a % 100) * (a % 100)) % 7 == 1)
        cout << "YES\n";
    else
        cout << "NO\n";
}
»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

Задача J. Пусть b[i] = i — a[i], для каждого 1 <= i <= n. Строим по новому массиву дерево отрезков. Затем для каждого <= i <= n — h + 1, находим минимум в дереве отрезков в отрезке от i до i + h — 1. Если этот минимум больше либо равен i — 1, тогда мы можем использрвать этот отрезок. Обновляем ответ за О(1). Итогое решение за O(N * logN). К сожалению сейчас не имею доступа к коду.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

B. Шахматы

Можно было ставить ладьи по диагоналям, т.е в точки (1,1) (2,2) (3,3) и так далее, пока это возможно.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Есть ли решения для F полегче этого?

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +35 Проголосовать: не нравится

Задача I:

Сведем задачу к кратчайшему пути в графе. Вершинами графа будут состояния (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) и аналогично два ребра в финиш.

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

  • »
    »
    12 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +16 Проголосовать: не нравится

    Можно взять все точки и считать вершиной графа последнюю пару посещенных точек. Дополнительно для каждой точки посчитаем, куда из нее можно переходить (из какими из точек она соединена). Тогда не нужно разбирать никаких случаев — из вершины (a,b) есть ребра во все вершины вида (b,c), где с — допустимый сосед b. А для угла я использовал atan2(), для него не надо знать никаких формул:)

    • »
      »
      »
      12 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Действительно, построение графа получается немного проще. Но у Вас граф из O(n3) вершин, что при заданных ограничениях  > 105 — Дейкстру нужно писать за . У нас же граф содержит O(n2) вершин и дейкстру можно писать за квадрат.

      А для угла я использовал atan2(), для него не надо знать никаких формул:)

      Тут не буду отрицать своей неопытности. Увы, но часто не вижу очевидного способа реализовать геометрические рутины :(

      • »
        »
        »
        »
        12 лет назад, скрыть # ^ |
        ← Rev. 2  
        Проголосовать: нравится 0 Проголосовать: не нравится

        Для ускорения можно выбросить "плохие" ребра — запретить переходить из точки a в точку b, если между ними есть еще какая-то точка. Тогда число достижимых вершин уменьшится до O(N2) — ведь теперь почти каждая достижимая вершина фактически будет соответствовать вершине из модели "перекресток-направление" (за исключением небольшого числа вершин вида "старт-перекресток" или "перекресток-финиш" или "старт-финиш").

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится
»
12 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

А кто нибудь добавит в тренировки Интернет-Тур? Буду признателен.

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Разбор задач )))

Задача G:

Сначала отсортируем массив.

Берем самую максимальную сосуду и переливаем, разбиваем пока средний средняя арифметическая сумма будет меньше чем максимальный элемент
int ans = 0;
for (int i = n; i >= 1; i--) {
    if (double(sum / double(i)) >= double(a[i])) {
        break;
    }
    ans++;
}

Задача H:

Посчитаем сколько раз встречается первое и второе слово каждой строки через 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);
»
12 лет назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

Задача Е:

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

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

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

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

Очки Пети: min( |A| — floor(|C| / 2) , ceil(m / 2) )

Очки Васи: min( |B| — ceil(|C| / 2) , floor(m / 2) )

Код решения

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

А, жадность на C кто нибудь может доказать?

  • »
    »
    12 лет назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +1 Проголосовать: не нравится

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

    1) Можно считать, что сперва мы вербуем людей, а потом завоёвываем города. Пусть из i-того города завербовано xi людей в лучшем ответе.

    2) Города лучше всего захватывать в порядке ai - xi (очевидно).

    3) В одном из лучшиз ответов города надо захватывать в порядке ai. Пусть это не так. Тогда если мы сперва захватили i, прямо следуюшим j и ai > aj, то xj = 0 (зачем нам кого-то нанимать, если можно весь город захватить бесплатно). "Перекинем" часть закупок из i-того города в j-тый. Противоречие. (см. пункт 5))

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

    5) Каждая операция, описанная в решении не увеличивает число потраченных денег и перекидывает покупки в более дешёвые города, то есть проблем с зацикливанием нет.

»
12 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Ребята в Кз со скольки задач будут принимать на Евразийскую) Просто наша команда решила 6 задача сейчас на 36 месте. Остается только надежда)

»
12 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится -27 Проголосовать: не нравится

Ребята подскажите почемуна задаче F tl 20 test 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; }

»
12 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
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;
}