На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (62) « Первая ... 59 60 [61] 62   ( Перейти к последнему сообщению )  
> Интересные задачки
    Цитата OpenGL @
    если вместо обруча будет канат, то на какую высоту после увеличения на метр его можно будет приподнять?


    Скрытый текст
    R - радиус окружности.
    С - центр окружности.
    с - угол у центра окружности.
    Возьмём участок каната от вершины поднятого участка "А" до касания окружности "В".
    В прямоугольном треугольнике АВС катет СВ=R, а гипотенуза равна R/Cos(с).
    Высота "h" точки "А" над окружностью:
    ExpandedWrap disabled
      h=R/Cos(с)-R


    Фрагмент каната от вершины до касания (катет АВ=R*Tan(с)) на 0.5 м. длиннее дуги под ним (половина удлинения каната):
    ExpandedWrap disabled
      R*Tan(с)-R*с=0.5


    Как решить это уравнение в общем виде я не представляю. Численно - без проблем.
    Решив его, подставляем "с" в первое уравнение и находим "h".
      Цитата ya2500 @
      Кто из них прав?

      Математически в самом деле оба неправы, физически прав второй - обруч длиной экватор+1м сожмется гравитацией, если экватор предполагать математическим. Не говоря уже про овраги, которые формально делают правым первого. Так что правы оба, а эйчар должен был взять обоих на работу, первого мидлом, так как умеет находить edge cases, второго системным или QA, так как ему легко даются мелкие прикладные задачи. ;)
        Цитата Vesper @
        экватор+1м сожмется гравитацией, если экватор предполагать математическим
        Если математическим, то никакой гравитации не предполагается. Как и веса и упругости (и толщины) верёвки. И никаких оврагов и гор на экваторе.
          Цитата amk @
          Если математическим, то


          Цитата Vesper @
          Математически в самом деле оба неправы



          Цитата Mikle @
          Как решить это уравнение в общем виде я не представляю

          Идея только одна - разложить тангенс в ряд Тейлора и воспользоваться малостью угла при вершине, потому что R>>0.5, отбросив члены с c^5 и далее, останется нечто от с^3 (коэффициент не помню, 1/3 что ли - проверил, да), т.е. R*c^3=0.5, c=(0.5/R)^(1/3), h=R*(sec©-1), если опять взять первый член ряда Тейлора, там +1*с^2, получается h=R^(1/3)*0.5^(2/3). Неожиданно, хм. Т.е. для Земли h~=116 метров (плюс-минус лапоть).

          Добавлено
          Поправка - вдвое меньше, там в ряде Тейлора для секанса я знаменатель (2n)! потерял. То есть 58 метров.
            Блин, встрял в сокобане, по-моему этот уровень непроходим:

            ExpandedWrap disabled
              ##############
              ## . . . . .####
              ## .## .##[] .##
              ## + .[]{} . .##
              ##@@ . .## . +##
              ################
               
              ## - стена
               .  - проход
               +  - место, где должен стоять сундук
              [] - сундук, стоящий в проходе
              {} - сундук, стоящий на месте
              @@ - герой игры
            Сообщение отредактировано: ya2500 -
              Цитата ya2500 @
              Блин, встрял в сокобане, по-моему этот уровень непроходим

              Скрытый текст
              По-моему так: сначала левый сундук вверх, потом правый вниз и сразу вверх, вредний с центра 2 влево, поставить правый в угол (проход появился), потом левый (бывший центральный) влево и на 1 веерх, потом средний вниз, влево и 2 вправо, потом левый 1 вниз. Или RRULLUURRRRDRDDLULLDLLUUURRRRDULLLLDDDRRURRURDLLLLDLURRRRUULLDURRDDLLDLLURRUULLD.
                1Vesper, по словесному описанию пройти получилось

                Скрытый текст
                сам не мог дотумкать до этого:
                Цитата Vesper @
                и на 1 веерх


                Спасибо! +1

                Скрытый текст
                можно бы написать проходилку сокобана)
                  Цитата ya2500 @
                  можно бы написать проходилку сокобана)

                  Вперёд :) За всё время только 9 человек сдали. Причём, судя по статистике - двое в этом году, т.е. резкий взлёт популярности задачи, можно сказать :D
                    Там сложность растёт катастрофическими темпами!
                    В SokoMind есть установка одного ящика. Где-то или видел или читал про возможность сделать установку двух ящиков.
                    На современном железе (1 ПК) наверное можно сделать 3...4 ящика.
                    На каком-то суперкомпьютере можно попробовать выйти на 5...7 штук.
                    Но задача довольно быстро становится сложнее шахмат, так что для реальных лабиринтов (10...100 ящиков) совершенно неактуально, увы. :yes-sad:
                      OpenGL ну я записал себе в очередь задач.

                      Скрытый текст
                      Цитата Славян @
                      задача довольно быстро становится сложнее шахмат,


                      Допустим, есть N ящиков. Перемещения без сдвигания ящиков особо не важны и в каждой ситуации важно только, какие ящики и в какую сторону возможно сдвинуть, это - ключевые моменты. А если подумать, то наверняка можно ещё уменьшить кол-во ключевых моментов для перебора; что приходит в голову сразу: запретить двигать ящик обратно и вообще, запретить повторение ситуации. Тогда перебор точно до шахмат не дотянется и близко.

                      Цитата Славян @
                      для реальных лабиринтов (10...100 ящиков) совершенно неактуально


                      Ну я не знаю - выше был "реальный" лабиринт с тремя ящиками. Лабиринтов на 100 ящиков я ещё не видел(если не считать старой игрухи, где много сокобанов были как бы объединены, но и там, ЕМНИП, нельзя было выкатывать ящики за экран)


                      Добавлено
                      Оу, там же указаны возможные пределы:

                      Цитата
                      На входе задана схема склада — прямоугольная сетка размером n × m (3 ≤ n, m ≤ 8).


                      - n не меньше трёх, вместо не больше! То есть, получается, предел возможного перебора определяется длиной строки:

                      Цитата
                      Длина строки не должна превышать 10000 символов.


                      - но каждый раз следующий символ выбирается не более чем из 4 вариантов.
                      Сообщение отредактировано: ya2500 -
                        OpenGL, спасибо! Я иногда порешиваю задачки codeforces, но теперь присмотрюсь и к этому Тимусу.
                          Цитата ya2500 @
                          запретить двигать ящик обратно
                          Крайне туманная формулировка, а в строгом соответствии с вашими словами вообще ошибочная! Ибо есть куча лабиринтов, где ящик двигается, давая проход челу, а потом возвращается назад. Так что надо аккуратнее с этой фразой.

                          Цитата ya2500 @
                          и вообще, запретить повторение ситуации.
                          Тоже чутка размытая формулировка. Если ситуация - с положением грузов и человека, то да, можно и запретить. А если только с положением грузов, то ошибочный запрет. (см. выше).

                          Но все эти запретики - крохотное количество в образующихся вариантах, так что спасения не несут никакого. Так что не:
                          Цитата ya2500 @
                          перебор точно до шахмат не дотянется и близко.
                          , а перебор переплюнет шахматы на раз-два. ;)
                            Цитата
                            На входе задана схема склада — прямоугольная сетка размером n × m (3 ≤ n, m ≤ 8)


                            Думаю, здесь имелось ввиду, что обе стороны - в пределах от 3 до 8 включительно )) в таком случае, нет смысла слишком углубляться в хитрые методы сокращения перебора; но остаётся крайне критичным быстрое распознание повторения позиции. Потому как иначе наш "грузчик" может по 10000 ходов ящики туда-сюда кантовать. А хотелось бы почаще находить решение уровня до достижения конца строки. И у меня, вроде бы, есть годные идеи по этому поводу.

                            Добавлено
                            Однако, пока что есть другие проекты в очереди. Условное полное название текущего проекта: "7 мастей пустыни Руб-Эль-Хали" - и, да, это текстовая игра ))
                              Цитата ya2500 @
                              в таком случае, нет смысла слишком углубляться в хитрые методы сокращения перебора

                              В этой задаче вердикт TLE - очень частый. Несложно же даже на таком мелком лабиринте придумать конфигурацию с большим числом ящиков, которые ты можешь разместить на поле очень большим количеством способов. Так что нет, тут не просто перебор по всем позициям надо юзать, а как-то ещё отличать осмысленную позицию от бесмыссленной (ящик в углу, и не на точке, например).

                              Цитата ya2500 @
                              но остаётся крайне критичным быстрое распознание повторения позиции

                              Я бы zobrist hashing заюзал.
                                Цитата OpenGL @
                                а как-то ещё отличать осмысленную позицию от бесмыссленной (ящик в углу, и не на точке, например).


                                Проверяем, приведёт ли сдвиг ящика к позиции: "(ящики и стены образуют блок 2х2) и (хотя бы один из ящиков не на точке)" - это просто.

                                А вот отследить все варианты "бессмысленной позиции в коридоре", уже сложнее(с учётом того, что в этом коридоре могут находиться и точки и другие ящики). И правило "ящик залип у стены"(вдоль которой его можно двигать, а отодвинуть от неё - нет) - ещё чуть сложнее.

                                Добавлено
                                Цитата OpenGL @
                                Я бы zobrist hashing заюзал


                                Да, но ещё, в деле отслеживания повторений хорошо бы избегать сравнения с каждой предыдущей позицией. То есть, если у нас забито 5000 ходов, то даже хэш сверить 5000 раз - уже потеря времени.

                                Добавлено
                                Цитата Славян @
                                Если ситуация - с положением грузов и человека, то да, можно и запретить. А если только с положением грузов, то


                                В положении человека важно только в какой области(доступной без перемещения ящиков) он находится. То есть, если позиция ящиков совпадает, то нужно проверить, есть ли путь между положениями грузчика.
                                Сообщение отредактировано: ya2500 -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:
                                Страницы: (62) « Первая ... 59 60 [61] 62 


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0899 ]   [ 16 queries used ]   [ Generated: 4.08.21, 03:18 GMT ]