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

Автор natalia, 14 лет назад, По-русски
Задачи A и B не представляли идейной сложности, поэтому начнем сразу с C.

Задача C

Положим β = α / 10. Тогда заданные числа - это a1 = [β], a2 = [2β], a3 = [3β], ... an = [nβ] и нужно определить [(n + 1)β] ([x] - целая часть числа). Данные равенства эквивалентны системе неравеств: an ≤ nβ < an + 1, . Выбирая максимум по левым частям и минимум по правым, получим неравество вида A ≤ n < B. Теперь осталось сравнить целую часть числа A / (n + 1) и B / (n + 1). В случае если B поделилось нацело, нужно вычесть из правой части единичку, т.к. справа неравенство строгое.

Задача D

Создадим векторы vi, в первый из которых v1 будем складывать позиции единичек, в v2 - двоек, в v3 - троек, и т.д. Их можно заполнить за один проход по данной последовательности. Количество перестановок - это количество единичек, или размер первого вектора. Мысленно определим первую единичку в первую перестановку, вторую - во вторую и т.д. Теперь перейдем к двойкам. Если их больше, чем единичек - решения нет. Иначе определим первую двойку в первую перестановку, вторую - во вторую и т.д. Возможно, несколько последних перестановок останутся без двоек. Дальше рассуждаем также для троек (которых должно быть не меньше, чем двоек) и т.д. Получаем решение за O(n). 
 
Задача E

Расскажу два решения. Первое решение разбирает отдельно три возможных случая. Построим граф, вершинами которого являются пары (h, t) - текущие количества голов и хвостов у Змея Горыныча. Ребра определяются возможными ударами Иванушки. Сначала при помощи обхода в ширину определим, можно ли из стартового состояния добраться до (0, 0) и за сколько шагов. Затем проверим, возможна ли ничья. Она возможна, если в графе есть циклы. Иначе граф ациклический и при помощи динамики на ациклическом графе можно определить самый длинный путь до состояния победы Змея.

Второе решение - реализовать алгоритм, который часто пишут для игр на циклических графах. По сути описанный процесс и является игрой на циклическом графе, только ходы Горыныча детерминированы. Начнем с тех состояний, для которых мы знаем ответ, т.е. (0, 0) и h + t >= R, и будем двигаться от них в обратном направлении по ребрам, помечая остальные состояния выигрышнsми или проигрышными. Непомеченные состояния останутся ничейными.

Задача F

Для каждого из n дней необходимо решать так называемую "непрерывную задачу о рюкзаке". Она решается жадно: отсортируем фирмы по цене производимого ими снега и будем брать снег с минимальной цене, пока не наберем нужный объем. Решение с сортировкой при каждом n не проходило по времени. Авторское решение работает за O(nm) и основано на идеях быстрой сортировки (QuickSort). Выберем случайный элемент r на имеющемся отрезке. Как в QuickSort,   переупорядочим остальные элементы, чтобы элементы, меньшие r, шли раньше него, и элементы, большие r - позже. Посчитаем суммарный объем снега с ценами, меньшими r. Если его достаточно - решаем задачу на левом подотрезке. Если нет - покупаем весь левый подотрезок и рекурсивно переходим к правому.

Отмечу еще одну неприятную особенность этой задачи. С одной стороны, ответ может быть достаточно большим. С другой стороны, требуется большая точность. Поэтому нужно вычислять целую и дробную части ответа отдельно.

Задача G

Заданный граф представляет собой связный граф с одним циклом. Сначала научимся решать задачу для дерева. Подвесим дерево за произвольную вершину и стандартной динамикой вычислим для каждого поддерева
1) количество вершин в нем;
2) сумму расстояний от корня до всех вершин поддерева.
После этого мы получим ответ на задачу для корня. Чтобы определить ответ для остальных вершин, совершим еще один обход по дереву. Рассмотрим переход от вершины u к ее потомку v. Чтобы добраться до v из вершни ее поддерева, нужно будет проделать тот же путь, что и до u, только не проходя последнее ребро. Наоборот, для всех остальных вершин путь увеличится на длину этого ребра. Таким образом,  d[v] = d[u] - L(u, v) * c[v] + L(u, v) * (n - c[v]), где c[v] - количество вершин в поддереве с вершиной v.

Теперь перейдем к графу с одним циклом, к которому возможно крепятся деревья. Корнями деревьев будем считать вершины цикла. Посчитаем ответ внутри каждого дерева. Общий же ответ складывается для каждой вершины из:
1) суммы длин путей внутри ее дерева;
2) суммы для всех остальных деревьев путей от их корней до всех вершин в дереве (потому что чтобы добраться до некоторой вершины из другого дерева, нужно пройти через его корень);
3) длины пути от вершины до корня ее дерева, умноженной на общее количество вершин в других поддеревьях;
4) сумма вида <длина кратчайшего пути по циклу от корня до дерева t> * <количество вершин в дереве t>.

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

Задача H

Представим сначала, что у нас ровно m черно-белых плиток. Тогда можно поступить следующим образом. Будем перебирать клетки по порядку сверху-вниз слева-направо. Сначала положим a черны плиток, потом - c = m черно-белых, затем - b белых. В итоге образуется граница из черно-белых плиток, разделяющая черные и белые. Эти плитки можно повернуть так, чтобы замощение стало корректным. Например: n = m = 4,
a = b = 6, c = 4.

########
########
#####/\#
####/..\
\##/....
.\/.....
........
........

В общей ситуации заменим c - m черно-белых плиток, например, на белые и построим замощение. Затем заменим белые плитки обратно на черно-белые, начиная с правого-нижнего угла, например: n = m = 4, a = 6, b = 3, c = 7.

########
########
#####/\#
####/..\
\##/....
.\/.....
.../\../
../##\/#

Решение в задаче всегда существует.
  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Решал E первым способом... дошел до неправильного ответа в 25 тесте... Что я делаю не так? =)
То есть, 25 тест -- это просто какой-то рандом или что-то конкретнее?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вообще это случайный тест, там побеждает Иван. Я уже выложила этот тест здесь.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня выдает

      Ivan
      26

      А какой правильный ответ, в той ветке не нашел?...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Правильный ответ 
        Ivan
        8
        Для получения правильного ответа по тесту удобно скачать любое правильное решение.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
14 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится
As regards problem E, I think that you must exclude from graph vertices which sum is > R.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кстати , если написать перебор на С, с некоторой точностью. то тоже пройдет.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Решал С таким образом. Пусть у нас есть отрезок amin и amax-соответственно минимальные и максимальные значения альфа которые подходят. Вычисляются они пошагово следующим образом: пусть мы были до этой заправки на m предыдущих, тогда минимальный обьем бензобака который нам нужен для того, чтобы доехать до текущей заправки: amin[m]=10*S/m, где 10-расход, S расстояние от А до заправки. Максимальный обьем, который нам позволен чтобы остановится именно на этой заправке а не на следующей amax[m]=10*(S+1)/m; понятно что amax-минимум из всех максимумов, amin-максимум из всех минимумов. Далее хоть одну остановку от последней заправки до 2*последнюю+1 он сделает(и, если следующий выбор неоднозначен-то не только одну, это легко доказать). Аналогичным образом вычисляем отрезок, если пересечение двух отрезков непусто, значит, гонщик имел теоретическую возможность остановиться на этой заправке.
»
12 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

nice structure for problem h