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

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

Задача D. "Архитектор Вася"

Эта задача вызвала большие затруднения.
В этой задаче достаточно было всего лишь вспомнить физическую статику. Для тех, кто затрудняется припомнить школьную программу, могу порекомендовать Википедию.

Как известно, существует 2 условия равновесия тела (здесь и далее будем считать устойчивое и неустойчивое равновесие неразличимыми, и называть общим словом "равновесие" или "устойчивость", так как в данной задаче нет никакого внешнего воздействия на конструкцию, кроме естесственной силы тяжести и силы взаимодействия кубиков с друг другом), но нам в этой задаче надо будет рассмотреть второй закон равновесия, который мы переформулируем в критерий устойчивости для нашей задачи:

Система кубиков устойчива тогда и только тогда, когда для любой ее точки сумма моментов всех сил, приложенных к этой точке равна нулю. Несложно понять, что это утверждение эквивалентно тому, что система кубиков устойчива тогда и только тогда, когда проекция центра масс этой системы лежит внутри или на границе проекции опоры, на которой расположена эта система кубиков.

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

Приведем формулы для координат центра масс некоторых n кубиков:

где:
,
mi = |xi, 1 - xi, 2|3 = |yi, 1 - yi, 2|3
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Что особенного в 30 тесте? Прошло его только после того как переписал полностью целочисленно. Думал так и задумывалось, но потом увидел людей и у которых проходило по точности и double, а у меня в long double падало.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Этот тест - примерно, когда центр тяжести одной из коробок лежит на границе другой. Видимо, ты упустил этот случай, потому что координаты там небольшие, проблем с точностью не должно было быть
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Нашел ошибку. Кстати она в другом. У меня масса кубика мгла быть <0. Забавно что это до 30 теста доходило. И еще забавнее что переписывая целочисленно я это учел.
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
А можно 40 тест? Два часа над ним бился, потом написал решение через центр масс и оно прошло с первой попытки >_<
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А 33 тест можно?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    7
    -9 9 9 -9
    10 -5 8 -7
    7 -6 9 -8
    20 5 -2 -17
    8 -15 10 -17
    50 25 3 -22
    50 28 7 -15

    ответ: 5
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно и 34-й, у меня на нем что только не падало?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    7
    -9 -9 9 9
    -8 3 0 -5
    -16 -8 6 14
    14 -11 -6 9
    5 -5 1 -9
    -11 -21 13 3
    -10 5 10 -15

    ответ: 6