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

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

А. Задача Бендера.

 

Будем говорить, что мы крепим j-ый прут к i-ому гвоздю, если мы крепим j-ый прут местом сгиба к i -ому гвоздю.

 

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

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

Если мы крепим j-ый прут к i-ому гвоздю, то len[j] = dist(i, i - 1) + dist(i, i + 1), где len[j] - длина j-ого прута, а dist(i, k) - расстояние между гвоздями с номерами i и k.

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

 

B. pSort.

 

Понятно, что мы можем поменять содержимое ячеек i и j, если |i-j|=dили |i-j|=dj.

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

Построим граф, вершинами в котором являются ячейки массива, а ребро существует между вершинами i и j, если возможен обмен между ними. Граф получаем неориентированный. То есть, если из вершины i в полученном графе достижима вершина j, то возможна такая серия обменов, что содержимое ячейки i поменяется с содержимым ячейки j.

Перестановку возможно отсортировать, если для всех i верно, что из вершины i достижима вершина p[i], где p - исходная перестановка.

 

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

14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
В условии написано, что n - четное.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А:
Почему нельзя крепить прут к 2 гвоздю, когда мы какой то другой прут прикрепили к 1 ??? тоесть когда пруты пересекаются на отрезке (1..2),в условии об етом ничего не сказано
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    Бендер может взять подходящий прут, согнуть его ровно один раз в любом месте под углом 90 градусов и прикрепить местом сгиба к еще не занятому гвоздю, а два конца прикрепить к двум соседним. Гвоздь считается незанятым, если к нему не прикреплен ни один прут (ни конец, ни место сгиба).
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    и прикрепить местом сгиба к еще не занятому гвоздю, а два конца прикрепить к двум соседним. Гвоздь считается незанятым, если к нему не прикреплен ни один прут (ни конец, ни место сгиба).
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    понял... спасибо !)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Разбор остальных задач будет?

14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Please, write in English. thanks