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

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

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

Задача А.

Реализация.

Задача 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
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится -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";
}
  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
    while(n--){
        cin>>a;
        if(((a/100)*(a/100)+(a%100)*(a%100))%7==1)cout<<"YES";else cout<<"NO";
    }
    

    Так красивей на мой взгляд, хотя рассматривать такую задачу бессмысленно.

»
10 лет назад, # |
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). К сожалению сейчас не имею доступа к коду.

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

    Когда у вас прошёл интернет-тур? Не могу найти ни одной команды из KZ в таблице результатов.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      Сегодня, часа 3 назад закончился. Если интересно тут результаты.

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

        Совсем другой уровень.

        Наша команда первая (в KG) с 6ю решенными, а у вас таких 33 команды.

        Интерес вызывает метод подготовки ваш к олимпиадам. Расскажите, если не секрет. ;)

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

          Как писал один великий человек "Сначала решай, потом бухай". А если серьозно, то лично я просто прорешивал КФ соревнования, писал виртуально. Или еще один хак в жизни, все мы знаем что красные тащят, следовательно надо стать красным. Еще один великий человек писал "Я открою вам маленький секрет, который хотят знать все некрасные участники. Секрет заключается в том, что чтобы стать красным, надо решить 1513 задач из архива Codeforces.". В общем решаешь 1513 задач из архива, становишься красным, тащишь. Как бы сказал мой сокомандник "Изи катка".

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

            Все великие цитаты великих людей в одном сообщении:)

            Azret, в самом деле, если коротко, то чем больше тренировок — тем лучше.

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

              О, один из программистов кем я восхищаюсь ответил на мое сообщение. На одну жизненную цель меньше, или как бы написал истинный программист: --жизненные_цели;

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

              Deleted.

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

          Секрет в том, что его нету. Надо очень много решать

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

    За (N * H) можно было код

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

      Там же 200000 * 200000.

      Или же у вас жесткие отсечения, либо гж авторам тестов.

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

        У них решение не за O(N * H), а за O(N + H).

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

          нет за O(N * H), там внутри for после if еще один for

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

            Нет, они if — ом жестко отсекают. Можешь протестить на макс тестах, работает очень быстро.

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

              Нет, это таки квадрат. Решение с генератором на ideone.

              Тест:

              200000 100000
              0 0 0 0 ... 0 1 2 3 4 ... 100000
              
              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

                Таки да.

                Возможно следовало добавить следующее отсечение — для i-того ответа можно использовать i + 1 ответ.

                Что-то вроде

                if(ans[i + 1]) ans[i] = ans[i + 1] — (h — a[i + h — 1]) + h — a[i];

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

                Точно, извиняюсь. Сегодня я осознал одну важную вещь, сначала думай, потом пиши.

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

    Можно очередь (два стека) и O(N).

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

B. Шахматы

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

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

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

  • »
    »
    10 лет назад, # ^ |
    Rev. 7   Проголосовать: нравится +13 Проголосовать: не нравится

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

    Делитель a * b = делитель a * делитель b. Работает за (количество делителей a) * (количество делителей b).

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

      мне кажется или вариант (количество делителей а) × (количество делителей б) правильнее?

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

        Ну да, просто у меня проблемы с редактированием.

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

    Можно через факторизацию чисел делать, но я не думаю что это легче.

»
10 лет назад, # |
  Проголосовать: нравится +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) и аналогично два ребра в финиш.

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

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

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

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

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

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

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

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

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

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

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

»
10 лет назад, # |
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);
»
10 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Задача Е:

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

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

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

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

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

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

Код решения

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

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

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

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

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

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

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

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

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

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

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

»
10 лет назад, # |
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; }

»
10 лет назад, # |
  Проголосовать: нравится 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;
}
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

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

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

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